图的遍历

图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以视为一种特殊的图的遍历。图的遍历就是图的一种最基本的操作，其他许多操作都建立在图的遍历操作基础之上。

广度优先搜索（BFS）

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。如图 9-9 所示，从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

  广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此他不是一个递归算法。为了实现逐层的访问没算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

bool visited[MAX_VERTEX_NUM];                //访问标记数组
void BFSTraverse(Graph G){
    //对图G进行广度优先遍历，设访问函数为visited()
    for(int i = 0; i < G.vexnum; i++){
        visited[i] = False;                     //访问标记数组初始化
    }
    InitQueue(Q);                            //初始化辅助队列Q
    for(int i = 0; i < G.vexnum; i++){        //从0号顶点开始遍历
        if(!visited[i]){                    //对每个连通分量调用一次BFS
            BFS(G,i);                        //Vi未访问过，从Vi开始BFS
        }
    }
}
void BFS(Graph G, int v){
    //从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
    visit(v);                                //访问初始顶点v
    visited[v] = True;                        //对v做已访问标记
    Enqueue(Q,v);                            //顶点v入队列
    while(!isEmpty(Q)){                        
        DeQueue(Q,v);                        //顶点v入队
        for(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)){    //检测v所有邻接点
            if(!visited[w]){                //w为v尚未访问的邻接顶点
                visit(w);                    
                visited[w] = True;
                EnQueue(Q,w);                //顶点w入队
            }
        }
    }
}

  辅助数组visited[]标志顶点是否被访问过，其初始状态为False。在图的遍历过程中，一旦某个顶点 $Vi$被访问，就立即置visited[i]=TRUE，防止它被多次访问。

1、BFS算法的性能分析

  无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需要入队一次，在最坏的情况下，空间复杂度为 $O(|V|)$ 。

  采用邻接矩阵存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为 $O(|V|)$），在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为 $O(|E|)$，算法总的时间复杂度为 $O(|V|+|E|)$ 。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为 $O(|V|)$ ，故算法总的时间复杂度为 $O(|V|^2)$ 。

2、BFS算法求解单源最短路径问题

  若 $G=(V,E)$ 为非带权图，定义从顶点u到顶点v的最短路径 $d(u,v)$ 为从u到v的任何路径中最少的边数；若从u到v没有通路，则 $d(u,v)$设为无穷大。

  使用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质来决定的。

  BFS算法求解单源最短路径问题的算法如下：

void BFS_MIN_Distance(Graph G, int u){
    //d[i]表示从u到i结点的最短路径
    for(int i = 0; i < G.vexnum; i++){
        d[i] = INT_MAX;                    //初始化路径长度
    }
    visited[u] = TRUE; d[u] = 0;
    EnQueue(Q,u);
    while(!isEmpty(Q)){                    //BFS算法主过程
        DeQueue(Q,u);                    //队头元素u出队
        for(w = FirstNeighbor(G,u); w >= 0; w = NextNeighbor(G,u,w)){
            if(!visited[w]){            //w为u的尚未访问的邻接顶点
                visited[w] = TRUE;        //设已访问标记
                d[w] = d[u] + 1;        //路径长度加1
                EnQueue(Q,w);            //顶点w入队
            }
        }
    }
}

3、广度优先生成树

  在广度遍历的过程中，我们可以得到一颗遍历树，称为广度优先生成树。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，但由于邻接表存储表示不唯一，故广度优先生成树也是不唯一的。

深度优先搜索（DFS）

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如下图 所示，从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。

bool visited[MAX_VERTEX_NUM];        //访问标记数组
void DFSTraverse(Graph G){
    //对图G进行深度优先遍历，访问函数为visit()
    for(v = 0; v < G.vexnum; v++){
        visited[v] = FALSE;            //初始化已访问标记数据
    }
    for(v = 0; v < G.vexnum; v++){    //从0开始遍历
        if(!visited[v]){
            DFS(G,v);
        }
    }
}
void DFS(Graph G, int v){
    //从顶点v出发，采用递归思想，深度优先遍历图G
    visit(v);                        //访问顶点v
    visited[v] = TRUE;                //设已访问标记
    foe(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)){
        if(!visited[w]){            //w为u的尚未访问的邻接顶点
            DFS(G,w);
        }
    }
}

  注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

1、DFS算法的性能分析

  DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为 $O(|V|)$。

  遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的事件取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为 $O(|V|)$，故总的时间复杂度为 $O(|V|^2)$ 。以邻接表表示时，查找所有顶点的邻接点所需的时间为 $O(|E|)$ ，访问顶点所需的时间为 $O(|V|)$，此时，总的时间复杂度为 $O(|V|+|E|)$ 。

2、深度优先的生成树和生成森林

  深度优先搜索会产生一棵深度优先生成树。对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林。基于邻接表存储的深度优先生成树是不唯一的。

分步演示:

图的遍历 · 进击的java菜鸟fhfirehuo.github.io

9.3   图的遍历 - Hello 算法www.hello-algo.com

图的遍历与图的连通性

  图的遍历算法可以用来判断图的连通性。

  对于无向图来说，若无向图是连通的，则从任意结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通图，则从某一个顶点出发，一次遍历只能访问该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。