图的遍历1.广度优先遍历（BFS）2.深度优先遍历（DFS）

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
来源：掘金