考研数据结构之图的遍历：深度优先搜索（DFS）与广度优先搜索（BFS）（包含真题及解析）

考研数据结构之图的遍历：深度优先搜索（DFS）与广度优先搜索（BFS）

图的遍历是图论中的核心操作之一，主要包括深度优先搜索（DFS）和广度优先搜索（BFS）。本文将详细讲解这两种算法的实现方式、应用场景及与图连通性的关系。

---

一、图的遍历定义

图的遍历是指从某个顶点出发访问图中所有顶点，且每个顶点仅被访问一次的过程。根据图是否连通，可能需要多次遍历才能访问所有顶点。

---

二、深度优先搜索（DFS）

1. 基本思想

• 递归或栈实现：从起始顶点开始，沿着一条路径深入访问，直到无法继续为止；然后回溯到上一个顶点，继续探索未访问的邻接点。
• 特点：
  • 类似于树的先序遍历。
  • 可用于寻找路径、拓扑排序等场景。

2. 算法步骤

1. 访问起始顶点v，标记为已访问。
2. 遍历v的所有邻接点w，若w未访问，则递归访问w。
3. 若所有邻接点均已访问，则回溯至上一层。

3. 代码实现

（1）递归实现

void DFS(Graph G, int v, bool visited[]) {visited[v] = true; // 标记当前顶点已访问printf("%d ", v);  // 输出顶点for (int w = 0; w < G.V; w++) { // 遍历邻接点if (G.adjMatrix[v][w] && !visited[w]) DFS(G, w, visited); // 递归访问}
}

（2）非递归实现（栈）

void DFS_NonRecursive(Graph G, int start) {Stack S;InitStack(S);bool visited[G.V];memset(visited, false, sizeof(visited));Push(S, start);while (!IsEmpty(S)) {int v = Pop(S);if (!visited[v]) {visited[v] = true;printf("%d ", v);for (int w = G.V - 1; w >= 0; w--) { // 倒序压栈保证顺序if (G.adjMatrix[v][w] && !visited[w])Push(S, w);}}}
}

---

三、广度优先搜索（BFS）

1. 基本思想

• 队列实现：从起始顶点开始，逐层访问其所有邻接点，再依次访问这些邻接点的邻接点。
• 特点：
  • 类似于树的层次遍历。
  • 可用于求解最短路径（无权图）、连通分量等问题。

2. 算法步骤

1. 访问起始顶点v，将其加入队列并标记为已访问。
2. 从队列中取出顶点u，访问其所有未访问的邻接点，并将其加入队列。
3. 重复上述过程直至队列为空。

3. 代码实现

void BFS(Graph G, int start) {Queue Q;InitQueue(Q);bool visited[G.V];memset(visited, false, sizeof(visited));EnQueue(Q, start);visited[start] = true;while (!IsEmpty(Q)) {int v = DeQueue(Q);printf("%d ", v);for (int w = 0; w < G.V; w++) { // 遍历邻接点if (G.adjMatrix[v][w] && !visited[w]) {visited[w] = true;EnQueue(Q, w);}}}
}

---

四、图的遍历与连通性

1. 连通图的遍历

• 连通图：通过一次DFS或BFS即可访问所有顶点。
• 应用：判断图是否连通。若某次遍历未能访问所有顶点，则说明图不连通。

2. 非连通图的遍历

• 非连通图：需对每个未访问的顶点分别调用DFS或BFS。
• 连通分量：每次调用DFS或BFS可得到一个连通分量。

---

五、真题解析

1. 图的遍历实现

题目（2023年真题，）：

给定一个无向图的邻接矩阵，请写出其DFS和BFS算法。

答案：
见上述代码实现部分。

---

2. 图的连通性判断

题目（经典真题，）：

如何利用DFS判断一个图是否连通？

解析：

1. 从任意顶点开始进行DFS。
2. 遍历结束后，检查是否所有顶点均被访问。
3. 若有顶点未被访问，则图不连通。

---

六、总结

• DFS适合递归实现，常用于路径搜索、拓扑排序等。
• BFS基于队列实现，适用于最短路径问题。
• 连通性判断：通过DFS或BFS遍历结果判断图是否连通。

掌握这两种遍历算法及其与连通性的关系，可高效解决图相关的实际问题。后续文章将探讨图的最小生成树与最短路径算法。