别再死记硬背DFS了！用邻接矩阵图解深度优先遍历的每一步（C语言实例）

邻接矩阵DFS可视化：用二维表格拆解深度优先遍历全过程

邻接矩阵是图论中最直观的存储结构之一，但很多学习者在理解DFS递归过程时仍感到抽象。本文将用邻接矩阵的二维表格形式，动态图解DFS算法的每一步状态变化，让你真正"看见"递归如何探索图的每个角落。

1. 邻接矩阵与DFS的核心交互机制

邻接矩阵用一个二维数组G[N][N]表示图中顶点间的连接关系。假设我们有一个包含5个顶点的无向图，其邻接矩阵可能如下所示：

DFS在这个矩阵上的操作可以分解为三个关键动作：

1. 访问顶点V：执行Visit(V)操作
2. 标记已访问：设置Visited[V] = true
3. 查找邻接点：按顺序检查G[V][0]到G[V][N-1]，对未访问的邻接点递归调用DFS

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) { Visited[V] = true; // 标记当前顶点已访问 Visit(V); // 执行访问操作 // 按顺序检查所有可能的邻接点 for (Vertex i = 0; i < Graph->Nv; i++) { if (Graph->G[V][i] == 1 && !Visited[i]) { DFS(Graph, i, Visit); // 递归访问未探索的邻接点 } } }

2. 可视化递归过程：从矩阵视角看DFS

让我们以从顶点0开始的DFS为例，逐步展示邻接矩阵和访问状态的变化。

初始状态：

• 访问标记数组：[false, false, false, false, false]
• 访问顺序：空

步骤1：访问顶点0

• 标记Visited[0] = true
• 访问顺序：0
• 检查邻接点：
  • G[0][1]=1且Visited[1]=false → 递归DFS(1)

步骤2：在DFS(1)中

• 标记Visited[1] = true
• 访问顺序：0 1
• 检查邻接点：
  • G[1][0]=1但Visited[0]=true → 跳过
  • G[1][2]=1且Visited[2]=false → 递归DFS(2)

步骤3：在DFS(2)中

• 标记Visited[2] = true
• 访问顺序：0 1 2
• 检查邻接点：
  • G[2][1]=1但Visited[1]=true → 跳过
  • G[2][3]=1且Visited[3]=false → 递归DFS(3)

我们可以用下面的表格记录每一步的访问状态：

3. 非连通图的遍历策略

上述代码在连通图中工作良好，但对于非连通图会遗漏未连接的组件。改进方法是在主函数中对所有顶点启动DFS：

int main() { MGraph G; Vertex V; G = CreateGraph(); // 对每个未访问的顶点启动DFS for (Vertex i = 0; i < G->Nv; i++) { if (!Visited[i]) { printf("DFS from %d:", i); DFS(G, i, Visit); printf("\n"); } } return 0; }

考虑下面的非连通图邻接矩阵：

遍历过程将分为三个部分：

1. 从顶点0开始：访问顺序0 1
2. 从顶点2开始：访问顺序2 3
3. 从顶点4开始：访问顺序4

4. 调试技巧：打印递归轨迹

为了更好地理解DFS的执行流程，可以在递归函数中添加调试输出：

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) { printf("Entering DFS for vertex %d\n", V); Visited[V] = true; Visit(V); for (Vertex i = 0; i < Graph->Nv; i++) { if (Graph->G[V][i] == 1) { printf("Checking edge %d->%d (visited=%d)\n", V, i, Visited[i]); if (!Visited[i]) { DFS(Graph, i, Visit); } } } printf("Exiting DFS for vertex %d\n", V); }

对于前面的连通图示例，输出可能如下：

Entering DFS for vertex 0 Visiting 0 Checking edge 0->1 (visited=0) Entering DFS for vertex 1 Visiting 1 Checking edge 1->0 (visited=1) Checking edge 1->2 (visited=0) Entering DFS for vertex 2 Visiting 2 Checking edge 2->1 (visited=1) Checking edge 2->3 (visited=0) Entering DFS for vertex 3 Visiting 3 Checking edge 3->0 (visited=1) Checking edge 3->2 (visited=1) Exiting DFS for vertex 3 Checking edge 2->4 (visited=0) Entering DFS for vertex 4 Visiting 4 Checking edge 4->2 (visited=1) Exiting DFS for vertex 4 Exiting DFS for vertex 2 Exiting DFS for vertex 1 Exiting DFS for vertex 0

这种调试方法清晰地展示了递归的进入和退出顺序，以及每次递归调用时的上下文状态。