> For the complete documentation index, see [llms.txt](https://xiuxin.gitbook.io/datastructre/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xiuxin.gitbook.io/datastructre/tu/tu-de-bian-li.md).

# 图的遍历

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

## 广度优先搜索（BFS）

  广度优先搜索类似于二叉树的层次遍历，其基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，，，wi 的所有未访问过的顶点；再从这些访问过的顶点出发，访问它们所有未被访问的邻接顶点，，，直至所有顶点全部被访问。Dijkstra 单源最短路径算法 和 Prim 最小生成树算法也应用了类似的思想。

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

```cpp
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算法求解单源最短路径问题的算法如下：

```cpp
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、广度优先生成树

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

![](https://xiuxin-1304803037.cos.ap-shanghai.myqcloud.com/广度优先生成树.png)

## 深度优先搜索（DFS）

  深度优先搜索类似于树的先序遍历。基本思想是：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，，，重复上述过程，当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有的顶点均被访问过为止。

```cpp
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才能产生深度优先生成树，否则产生的将是深度优先生成森林。基于邻接表存储的深度优先生成树是不唯一的。

## 图的遍历与图的连通性

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

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