1.广度优先遍历（BFS）
基本思想：首先从图的某个顶点0出发，访问0之后，依次访问与0相邻接的未被访问的顶点，然后从这些顶点出发继续访问与之相邻接的未被访问的顶点，以此类推，直到所有顶点都被访问完。
广度优先遍历（BFS）代码
bool visited[Max_Vex]; //访问标记数组
void BFSTraverse(Graph G){
for(i=0;i<G.vexnum;++i)
visited[i]=false; //初始化标记数组
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
if(!visited[v]) //如果v未被访问，那么从v起，开始做广度优先遍历
BFS(G,v);
}
void BFS(Graph G,int v){
visit(v); visited[v]=true; Enqueue(Q,v); //访问结点并将结点入队
while(!isEmpty(Q)){
DeQueue(Q,v); for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
visit(w); visited[w]=true; EnQueue(Q,w)
}
}
}
性能分析
- 当图采用邻接表存储时，每个顶点均需搜索一次（或入队一次），此操作对应时间复杂度为O(|V|),在搜索到某一顶点时需要访问每一条与 此邻接的边，此操作需遍历邻接表中所有边表结点，故时间复杂度为 O(|E|),故此时总的时间复杂度为O(|V|+|E|)
- 当图采用邻接矩阵存储时，查找每个顶点的邻接点需遍历一行，此操 作对应时间复杂度为O(|V|),而所有顶点都需要执行一次查找，故总的 时间复杂度为O( ||^2)
- 空间方面需要引入队列，最坏时所有顶点均入队，空间复杂度为O(|V|)
广度优先生成树
在广度优先遍历过程中，我们可以得到一颗遍历树，称为广度优先生成树
注意：
- 若图是非连通的，则会产生广度优先生成森林
- 图的邻接矩阵表示是唯一的，故广度优先生成树也唯一
2.深度优先遍历（DFS）
基本思想：首先从图的某个顶点0出发，访问0之后，访问与0相邻接 的未被访问的顶点1，然后从1顶点出发继续访问与之相邻接的未被访问 的顶点2，以此类推，若不能再继续向下访问时，依次回退最近一次访问 的顶点，每次回退查看当前顶点还有没有未被访问的邻接顶点，若有就访 问，直到所有顶点都被访问完。
bool visited[Max_Vex]; //访问标记数组
void DFSTraverse(Graph G){
for(i=0;i<G.vexnum;++i)
visited[i]=false; //初始化标记数组
for(v=0;v<G.vexnum;++v)
if(!visited[v]) //如果v未被访问，那么从v起，开始做深度优先遍历
DFS(G,v);
}
void DFS(Graph G,int v){
visit(v); visited[v]=true; //访问结点并更改标记
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){
DFS(G,w);
}
}
性能分析
- 当图采用邻接表存储时，每个顶点均需搜索一次（或入栈一次），此操作对应时间复杂度为O(|V|),在搜索到某一顶点时需要访问每一条与 此邻接的边，此操作需遍历邻接表中所有边表结点，故时间复杂度为 O(|E|),故此时总的时间复杂度为O(|V|+|E|)
- 当图采用邻接矩阵存储时，查找每个顶点的邻接点需遍历一行，此操 作对应时间复杂度为O(|V|),而所有顶点都需要执行一次查找，故总的 时间复杂度为O( ||^2)
- 空间方面需要引入递归工作栈，最坏时所有顶点均入栈，空间复杂度为O(|V|)
深度优先生成树
在深度优先遍历过程中，我们可以得到一颗遍历树，称为深度优先生成树
注意：
- 若图是非连通的，则会产生深度优先生成森林
- 图的邻接矩阵表示是唯一的，故深度优先生成树也唯一
作者：有出路
链接：https://juejin.cn/post/6999560010879483917
来源：掘金
网友评论