广度优先遍历（BFS）

BFS(Breadth-First-Search)，参考对树的层序遍历

对上面的图从①出发进行BFS得到序列：

①②⑤ ⑥ ③⑦ ④⑧

若采用不同的储存结构，可能会得到不同的遍历结果（这个差异主要来自寻找邻接点的过程），对于邻接矩阵存储的图，由于邻接矩阵是唯一的，所以BFS序列也是唯一的；同理，邻接表存储的图BFS序列不唯一。

BFS算法

与树的层序遍历不同的是，由于图中存在回路，遍历过程中会出现重复访问的问题，故可构造visited数组，用来标记已访问过的数组。

此外，还应针对非连通图做额外的判断，遍历完一个连通分量（极大连通子图）后，遍历查找visited数组中是否还存在未遍历的，如果有即为另一连通分量，继续调用BFS即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void BFS(Graph G,int v);

bool visited[MAX_VERTEX_NUM];

SqQueue Q;//辅助队列
void BFSTraverse(Graph G){
    //初始化visited数组
    for (int i = 0; i < G.vexnum; ++i) {//使下标从1开始
        visited[i]=false;
    }
    //对非连通图的处理
    for (int v = 0; v < G.vexnum; ++v) {
        if (!visited[v])
            BFS(G,v);
    }
}

//从顶点v出发广度优先遍历图G
void BFS(Graph G,int v){
    visit(v);
    visited[v]=true;
    EnQueue(Q,v);//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);//顶点v出队列Q
        for (w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//处理v的所有邻接点
            if (!visited[w]) {
                visit(w);
                visited[w]=true;
                EnQueue(Q,w);
            }//if
    }//while
}

需要借助辅助队列存储v的所有邻接结点

复杂度

（一）空间

空间复杂度主要来自辅助队列，在访问v的邻接结点时会入队，因此最坏的情况下

复杂度为：$O(|V|)$

（二）时间

对时间复杂度的分析，不必纠结于算法中的具体循环，只需宏观地分析：

①访问|V|个结点需要的时间复杂度？

②访问各个结点的邻接结点需要的时间？

邻接矩阵型 邻接表型
① $O(V)$ $O(V)$
② $O(V^2)$ $O(2E)=O(E)$
时间复杂度 $O(V^2)$ $O(V+E)$

时间复杂度=访问各结点所需时间+探索各条边所需时间

广度优先生成树

简而言之，就是 $\text{连通图}\overset{BFS}{\rightarrow}\text{树}$

即 仅保留每个节点第一次被访问的那条通路

此外还有广度优先生产森林，即 $\text{非连通图}\overset{BFS}{\rightarrow}\text{森林}$

深度优先遍历（DFS）

BFS(Depth-First-Search)，参考对树的先序遍历

对上面的图从②出发进行DFS得到序列：

② ① ⑤ ⑥ ③ ④⑦ ⑧

同样的，邻接矩阵存储得到序列唯一，邻接表则不唯一。

DFS算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void DFS(Graph G,int v);

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    //初始化visited数组
    for (int i = 0; i < G.vexnum; ++i)
        visited[i]=false;
    //对非连通图的处理
    for (int v = 0; v < G.vexnum; ++v) 
        if (!visited[v])
            DFS(G,v);
}

//从顶点v出发广度优先遍历图G
void DFS(Graph G,int v){
    visit(v);
    visited[v]=true;
    for (w=FirstNeighbor(G,v);w>=0;w=FirstNeighbor(G,v))//始终遍历v的第一个邻接点，往“深”处走
        if (!visited[w]) {
            DFS(G,w);
        }//if
}

复杂度

（一）空间

主要来自函数调用栈，因此最坏的情况与最好的情况分别是

因此，空间复杂度为$O(|V|)$

（二）时间

邻接矩阵型 邻接表型
① $O(V)$ $O(V)$
② $O(V^2)$ $O(E)$
时间复杂度 $O(V^2)$ $O(V+E)$

深度优先生成树

同BFS

思考：图的遍历与图的连通性

根据上述算法可知，对于无向图，调用BFS/DFS的次数与连通分量的数量有关，即 $\text{BFS|DFS调用次数}\propto \text{连通分量数}$

对于有向图：

1.若从①出发，需要调用几次DFS?

答：4次。

2.若从⑦出发，需要调用几次DFS?

答：1次。

因此，有

图的分类 调用BFS|DFS次数
无向图 连通：1次
非连通：连通分量数
有向图 普通有向图：具体分析（与出发点的选择有关）
强连通图：1次

🖋