图的遍历

一、深度优先搜索（DFS）

算法思想

从起始顶点出发，访问一个邻接点，再访问该邻接点的邻接点，直到无法继续，回溯到上一个顶点继续。

代码实现（邻接矩阵）

bool visited[MaxVertexNum];

void DFS(MGraph G, int v) {
    visit(v);
    visited[v] = true;
    for (int w = 0; w < G.vexnum; w++)
        if (G.edge[v][w] == 1 && !visited[w])
            DFS(G, w);
}

代码实现（邻接表）

void DFS(ALGraph G, int v) {
    visit(v);
    visited[v] = true;
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex])
            DFS(G, p->adjvex);
        p = p->next;
    }
}

遍历整个图（处理非连通图）

void DFSTraverse(MGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i])
            DFS(G, i);
}

二、广度优先搜索（BFS）

算法思想

从起始顶点出发，先访问所有邻接点，再依次访问邻接点的邻接点。

代码实现（邻接表）

void BFS(ALGraph G, int v) {
    Queue Q; InitQueue(&Q);
    visit(v); visited[v] = true; EnQueue(&Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(&Q, &v);
        ArcNode *p = G.vertices[v].first;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                visit(p->adjvex);
                visited[p->adjvex] = true;
                EnQueue(&Q, p->adjvex);
            }
            p = p->next;
        }
    }
}

三、DFS vs BFS

四、图的连通性

• 无向图：连通图任意两点可达；连通分量是极大连通子图；一次 DFS/BFS 能访问所有结点 ⟹ 连通图；需多次调用 ⟹ 非连通，次数 = 连通分量数
• 有向图：强连通图任意两点互相可达；强连通分量是极大强连通子图

邻接表：

0 → [1] → [2]
1 → [0] → [3]
2 → [0] → [3]
3 → [1] → [2] → [4]
4 → [3]

例 1：DFS（从顶点 0）

访问序列：0 → 1 → 3 → 2 → 4

例 2：BFS（从顶点 0）

访问序列：0 → 1 → 2 → 3 → 4

例 3：连通分量计数

0 --- 1    3 --- 4

2         5

DFS 调用 3 次，分别访问 {0,1,2}、{3,4}、{5} ⟹ 连通分量数 = 3