php网站怎么样,中国最大的软件外包公司,企业网站建设一般要素包括,广电基础设施建设官方网站搜索
一.dfs和bfs简介
深度优先遍历(dfs)
本质#xff1a;
遍历每一个点。
遍历流程#xff1a;
从起点开始#xff0c;在其一条分支上一条路走到黑#xff0c;走不通了就往回走#xff0c;只要当前有分支就继续往下走#xff0c;直到将所有的点遍历一遍。
剪枝
遍历每一个点。
遍历流程
从起点开始在其一条分支上一条路走到黑走不通了就往回走只要当前有分支就继续往下走直到将所有的点遍历一遍。
剪枝
如果已经确定这条路没有我们想要的答案那么就不用继续在这条路上走下去了于是我们就开始走其他的分支或者往回走这样节省时间的方法称之为剪枝。
回溯
当我们一条路走到头往回走时就叫做回溯。
恢复现场
当我们回溯的时候原来这个图是什么样的我们还要变回什么样。这样做的目的 当我们遍历完这条分支去遍历下一条分支的时候我们需要保证当前图其他条件的一致性也就是遍历每一条分支的时候当前图的状态都是一样的。保证遍历每一条分支的时候都是公平的。
广度优先遍历(bfs)
遍历流程 逐层逐层的遍历先遍历第一层再遍历第二层…也就是遍历当前节点所能到达的所有子节点。直到遍历所有的点。不存在剪枝回溯和恢复现场的操作。
对比dfs和bfs
时间复杂度 dfs: 因为我们需要枚举每一个点以及每一条边所示它的时间复杂度为O(n e) 即点的个数边的个数 bfs:跟dfs时间复杂度一样都为O(n e) 不同的是对每个点的访问顺序是不一样的 用到的数据结构 dfs: stack bfs: queue 空间复杂度 dfs: O(h) h为树的深度 bfs: O(2^h) 特性 dfs: 不具有最短性 bfs: 具有最短性 二. 树与图的深度优先遍历(dfs)
树与图的深度优先遍历: 树其实也是图的一种 图: 分为有向图和无向图 图的储存: 第一种邻接矩阵就是一个二维数组缺点当点和边特别多的时候存不下一般用的比较少而且非常浪费空间 第二种邻接表:由n个单链表组成也可以用vector动态数组来实现但vector有很大的缺点当点和边非常大时用vector动态数组的方法很容易超时所以我们常用n个但链表的方式来存储图 邻接表如何存图呢 假设有这样一个图: 那么我们可以给每个节点开一个单链表如下图所示 这样我们就把图用邻接表的方法存了下来 树与图深度优先遍历的大致流程一条路走到黑直到撞到南墙走不通了然后往回走只要有分支就继续往下走
1.树与图的遍历模板
邻接表以h数组为表头使用 e 和 ne 数组分别存储边的终点和下一个节点
#includeiostream
#includecstring
using namespace std;
const int N 1e6 10;
int h[N], e[N], ne[N], idx, n;//这里跟单链表一样只不过这里是N个头节点H[N]
bool vis[N]; //判断是否遍历过
void add(int a, int b) //邻接表存树与图
{e[idx] b, ne[idx] h[a], h[a] idx;
}
void dfs(int cur)
{vis[cur] true;for(int i h[cur]; i ! -1; i ne[i]){ //遍历树int u e[i];if(!vis[u]){dfs(u);}}
}
int main()
{int a, b;cin n;//初始化memset(h, -1, sizeof h);memset(vis, false, sizeof vis);for(int i 0; i n; i){cin a b;//建树双向图add(a, b);add(b, a);}dfs(1);return 0;
}这样我们就遍历了每个点。
2.树的dfs序
一般来讲我们在对树进行深度优先遍历时对于每个节点在刚进入递归以后以及即将回溯前各记录一次该点的编号,最后产生的长度为2N的节点序列被称为树的dfs序
void dfs(int x)
{a[m] x;v[x] 1;for(int i h[x]; i ! -1; i ne[i]){int y e[i];if(v[y])continue;dfs(y);}a[m] x;
}3.树的深度
我们已知根节点的深度为0.若节点x的深度为d[x]则它的子节点的深度为d[y] d[x] 1
void dfs(int x)
{v[x] 1;for(int i h[x]; i ! -1; i ne[i]){int y e[i];if(v[y])continue;d[y] d[x] 1;dfs(y);}
}4.连通图的划分
假设从x点开始一次遍历就会访问x能够到达的所有的点和边因此通过多次深度优先遍历可以划分出一张无向图中的各个连通图。同理对一个森林进行深度优先遍历可以划分森林中每棵树
cnt表示无向图包含的连通块的个数, v数组标记了每一个点属于哪个连通块
void dfs(int x)
{v[x] cnt;for(int i h[x]; i ! -1; i ne[i]){int y e[i];if(v[y])continue;dfs(y);}
}
for(int i 1; i n; i){if(!v[i]){cnt;dfs(i);}
}三.树与图的广度优先遍历
树与图的广度优先遍历需要使用一个队列来实现。起初队列中仅包含一个起点。在广度优先遍历过程中我们不断从队头取出一个节点x对于x面对的多条分支将所有x能够达到的下一个节点插入队尾重复执行上述过程直到队列为空
1.广度优先遍历模板
void dfs()
{memset(d, 0, sizeof d);queueint q;q.push(1);d[1] 1; //d数组表示节点的深度while(q.size()){ //只要队列不为空int x q.front(); //取出队头q.pop();for(int i h[x]; i ! -1; i ne[i]){ //遍历x能够到达的所有下一个节点int y e[i];if(d[y])continue; d[y] d[x] 1; //深度1q.push(y);}}
} 在上面的代码中d数组表示从起点 1 走到点 x 需要经过的最少点数. 广度优先遍历是一种按照层次顺序进行访问的方法, 它具有如下俩个重要的性质 1.在访问完所有的第 i 层节点后才会开始访问第 i 1 层节点
2.广度优先遍历队列中的元素关于层次满足俩段性和单调性, 即队列中至多包含俩个层次的节点, 其中一部分属于第 i 层, 一部分属于 i 1 层,并且所有的第 i 层节点都排在第 i 1 层节点之前
2.拓扑排序
给定你一个无向图若一个由图中所有点构成的序列A满足对于图中的每条边 (x, y)x 在A中都出现在y之前,则称A是该有向图的一个拓扑排序
入度 在有向图中以节点 x 为终点的有向边的条数被称为 x 的入度
出度 在有向图中以节点 x 为起点的有向边的条数被称为 x 的出度
拓扑排序非常简单,我们只需要不断选择图中入度为0的节点 x , 然后把 x 连向的点的入度减1,我们可以结合广度优先遍历的框架来实现:
1.建立空的拓扑排序A。
2.预处理出所有点的入度deg[i]起初把所有入度为0的点入队
3.取出队头节点x把x加入拓扑序列A的末尾
4.对于x出发的每条边(x, y)把 deg[y] 减 1 。若被减为0, 则把y入队
5.重复3~4过程直到队列为空我们便求出了拓扑序列A
void add(int x, int y) //建边
{e[cnt] y, ne[cnt] h[x], h[x] cnt;
}
void topsort()
{queueint q;for(int i 1; i n; i)if(deg[i] 0)q.push(i); //将入度为0的点加入到队列中while(q.size()){int x q.front();q.pop();a[t] x; //将x加入到拓扑序中for(int i h[x]; i ! -1; i ne[i]){int y e[i];deg[y]--; //入度--if(deg[y] 0)q.push(y);//如果入度为0添加到队列中去}}
}
int main()
{cin n m;for(int i 1; i m; i){int x, y;cin x y;add(x, y);}topsort();for(int i 1; i n; i)//输出拓扑序printf(%d , a[i]);cout endl;
}四.迭代加深
深度优先搜索每次选定一个分支不断深入直至到达递归边界才回溯。这种策略带有一定的缺陷。如果搜索树每个节点的分枝数非常多, 而答案在某个较浅的节点上。如果深搜在一开始选错了分支就很可能在不包含答案的深层子树上浪费太多的时间
此时我们可以从小到大限制搜索的深度如果在当前深度限制下找不到答案就把深度限制增加重新进行一次搜索这就是迭代加深的思想。
例题加成序列(poj2248)
满足如下条件的序列X序列中元素被标号为1、2、3…m被称为“加成序列”
1、X[1]1
2、X[m]n
3、X[1]X[2]…X[m-1]X[m]
4、对于每个 k2 ≤ k ≤ m都存在两个整数 i 和 j 1 ≤ i,j ≤ k−1i 和 j 可相等使得 X[k]X[i]X[j]。
你的任务是给定一个整数n找出符合上述条件的长度m最小的“加成序列”。
如果有多个满足要求的答案只需要找出任意一个可行解。
搜索框架依次搜索序列中的每个位置k 枚举 i 和 j 作为分支把 X[i] 和 X[j] 的和填到 X[k] 上然后递归填写下一个位置。
加入以下剪枝
1.优化搜索顺序为了让序列中的数尽快逼近n在枚举 i 和 j 时从大到小枚举
2.排除等效冗余
对于不同的 i 和 j X[i] 和 X[j] 可能是相等的我们可以在枚举是用一个 bool 类型的数组对 X[i] 和 X[j] 进行判重,避免重复搜索同一个和
3.我们可以采用迭代加深的方法进行搜索, 从1开始限制搜索深度若搜索失败就增加深度限制重新搜索,直到找到一组解时即可输出答案
#includeiostream
#includecstring
using namespace std;const int N 110;
int a[N];
bool vis[N];
int n, k;
bool dfs(int u, int k)
{//如果达到搜索限制判断a[u - 1]是否等于nif(u k)return a[u - 1] n;//遍历前边的元素for(int i u - 1; i 0; i--){for(int j i; j 0; j--){int s a[i] a[j];//如果和已经出现过或者不满足要求剪枝掉if(vis[s] || s n || s a[u - 1])continue;a[u] s;if(dfs(u 1, k))return true;}}return false;
}
int main()
{a[0] 1;while(cin n n){int k 1;while(!dfs(1, k)){ //不断增加搜索限制k直到得到正确的答案memset(vis, false, sizeof vis);k;}for(int i 0; i k; i)cout a[i] ;cout endl;}return 0;
}
