图的深度优先与广度优先遍历：邻接矩阵与邻接表实现详解

1. 项目概述：图的遍历实战精讲

最近在辅导学生做数据结构课程设计，发现很多同学一碰到“图的遍历”这个头歌平台的习题集就有点发怵。邻接矩阵和邻接表看着简单，真写起代码来，各种指针乱飞、数组越界的问题就都来了。这太正常了，我当年学的时候也在这栽过跟头。图的遍历，像深度优先搜索（DFS）和广度优先搜索（BFS），是图论算法最最基础的骨架，后续的最短路径、拓扑排序、连通分量全得靠它俩。这个合集习题，本质上就是逼着我们把这两种遍历方式，在两种不同的存储结构下，完完整整、稳稳当当地实现出来。它不考你多炫技的算法，考的就是基本功扎不扎实，对图这种非线性结构的理解到不到位。不管是计算机考研复试，还是大厂笔试的编程题，图的遍历都是高频考点，这道坎必须迈过去。今天，我就以一个老码农的身份，带你拆解这套习题，把里面容易踩的坑、必须掌握的技巧，还有从原理到代码的每一步，都掰开揉碎了讲清楚。

2. 核心需求与设计思路拆解

2.1 习题核心目标解析

这套习题的核心目标非常明确：实现图的深度优先遍历（DFS）和广度优先遍历（BFS）算法，并分别适配邻接矩阵和邻接表两种存储结构。这听起来是四个任务（DFS-矩阵、DFS-表、BFS-矩阵、BFS-表），但内在逻辑是相通的。题目通常会提供一个图的顶点和边信息，要求你输出从某个指定顶点出发的一个遍历序列。这里的关键在于，遍历序列可能不唯一（尤其对于非连通图或存在多种选择时），但必须符合DFS“一条路走到黑再回头”和BFS“层层推进”的核心逻辑。平台判题系统往往会有多个测试用例，覆盖连通图、非连通图、有向图、无向图等不同情况，这就要求我们的代码必须具备完备的健壮性。

2.2 存储结构选型与遍历逻辑

为什么一定要掌握两种存储结构？因为它们在空间和时间复杂度上各有优劣，直接影响了遍历算法的实现细节。

• 邻接矩阵：用一个二维数组matrix[v][w]表示顶点v和w之间是否有边（或边的权值）。它的优点是判断任意两顶点间是否有边非常快（O(1)），而且代码直观。缺点是空间开销大（O(V²)），对于稀疏图（边数远小于顶点数平方）极其浪费。在遍历时，我们通常需要一个visited数组来记录顶点访问状态，然后通过循环扫描矩阵的一行来寻找邻接点。
• 邻接表：为每个顶点建立一个单链表，链表中存储与该顶点直接相连的所有邻接点。它完美适配稀疏图，空间复杂度为O(V+E)。但在判断任意两点间是否有边时，需要遍历链表，效率是O(degree(v))。在遍历实现上，寻找邻接点不再需要循环扫描，而是直接遍历该顶点的链表即可。

遍历算法逻辑本身是独立于存储结构的：

• DFS (深度优先搜索)：模仿“走迷宫”策略。从起点出发，任意选择一个未访问的邻接点深入，直到无路可走，再回溯到上一个顶点尝试其他分支。递归实现最直观，也符合其“栈”的本质（递归调用栈）。非递归实现则需要显式使用一个栈。
• BFS (广度优先搜索)：模仿“水波扩散”策略。从起点出发，先访问所有距离为1的邻接点，再访问距离为2的邻接点，以此类推。这天然契合“队列”数据结构（FIFO）。所以BFS通常用队列辅助实现，是非递归的。

设计思路就是将这四种组合（存储 x 遍历）分别实现，核心框架是：初始化访问数组 -> 从起点调用遍历函数 -> 在遍历函数中，根据存储结构的不同方式寻找邻接点，并按照DFS或BFS的策略访问它们。

3. 核心数据结构实现细节

3.1 邻接矩阵的构建与要点

用C语言实现，邻接矩阵通常是一个动态分配的二维数组，或者是一个一维数组模拟二维。

#define MAX_VERTEX_NUM 100 // 根据题目要求设定 typedef struct { int vertices[MAX_VERTEX_NUM]; // 顶点表，有时可省略 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertexNum, edgeNum; // 顶点数和边数 int isDirected; // 标识是否有向图 } MGraph;

构建关键步骤：

1. 初始化矩阵：将所有edges[i][j]初始化为0（无权图）或一个特殊值如INF（有权图），表示无边。
2. 插入边：读取一条边(v, w)，令edges[v][w] = 1（或权值）。如果是无向图，切记要对称赋值：edges[w][v] = 1。这是新手最容易忘记的一点，会导致遍历时“有去无回”。
3. 顶点编号：题目顶点可能是数字或字符。如果是字符（如‘A’， ‘B’），通常需要做一个映射，将其转换为从0开始的整数索引，方便数组操作。

注意：如果题目顶点数很大（比如超过1000），使用静态二维数组可能造成栈溢出（如果矩阵定义在函数内部）。此时应使用动态内存分配（int**+ 循环malloc），或者将矩阵声明为全局变量。

3.2 邻接表的构建与要点

邻接表的实现稍复杂，涉及链表操作。

typedef struct ArcNode { // 边表节点 int adjvex; // 该边所指向的顶点位置（索引） struct ArcNode* nextarc; // 指向下一条边的指针 // int weight; // 若为带权图，可增加权值域 } ArcNode; typedef struct VNode { // 顶点表节点 int data; // 顶点信息（有时可省略） ArcNode* firstarc; // 指向第一条依附该顶点的边的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; // 邻接表 int vertexNum, edgeNum; int isDirected; } ALGraph;

构建关键步骤：

1. 初始化顶点表：将每个顶点的firstarc指针初始化为NULL。
2. 插入边：这是核心，采用头插法效率最高。
   • 为新边(v, w)创建一个ArcNode节点，其adjvex设为w。
   • 将该节点的nextarc指向当前vertices[v].firstarc。
   • 将vertices[v].firstarc更新为该新节点。
   • 如果是无向图，需要再对称地插入一条边(w, v)，即重复上述步骤，创建adjvex为v的节点插入到vertices[w]的链表头部。
3. 内存管理：由于使用了动态分配的边节点，在程序最后（如果必要）应遍历所有顶点，释放每个链表占用的内存，避免泄漏。这在算法题中常被忽略，但却是良好的编程习惯。

头插法与尾插法的选择：头插法（O(1)）比尾插法（需要找到链表尾部，O(n)）更高效。虽然这会导致邻接点顺序与输入顺序相反，但图的遍历通常不关心邻接点的访问顺序（除非题目特殊说明），所以头插法是更通用的选择。

4. 深度优先搜索（DFS）实现详解

4.1 递归实现：最直观的版本

DFS的递归实现简洁优美，完美体现了其“深度优先”的思想。

邻接矩阵版DFS递归函数：

int visited[MAX_VERTEX_NUM] = {0}; // 访问标记数组，通常设为全局 void DFS_Matrix(MGraph* G, int v) { printf("%d ", v); // 访问顶点v，按题目要求输出 visited[v] = 1; for (int w = 0; w < G->vertexNum; w++) { // 找到v的所有未访问的邻接点w if (G->edges[v][w] != 0 && !visited[w]) { DFS_Matrix(G, w); // 递归深入 } } }

邻接表版DFS递归函数：

void DFS_List(ALGraph* G, int v) { printf("%d ", v); visited[v] = 1; ArcNode* p = G->vertices[v].firstarc; while (p != NULL) { int w = p->adjvex; if (!visited[w]) { DFS_List(G, w); } p = p->nextarc; } }

递归实现的要点：

1. 递归终止条件：隐含在for/while循环中。当顶点v的所有邻接点都已访问（或没有邻接点）时，该层递归函数自然返回。
2. 访问标记的位置：必须在递归调用之前标记当前顶点为已访问。如果放在之后，或者在递归函数开头不立即标记，在存在环的图中会导致无限递归。
3. 非连通图的处理：上面的函数只完成了从一个顶点开始的遍历。对于非连通图，需要在主调函数中循环检查所有顶点，如果visited[i]为0，就调用DFS(G, i)。这样才能遍历到所有连通分量。

4.2 非递归实现：显式使用栈

非递归实现有助于理解DFS的栈本质，也是面试常考点。我们需要一个栈来手动模拟递归调用栈。

邻接矩阵版DFS非递归（栈实现）：

void DFS_Matrix_NonRecur(MGraph* G, int v) { int stack[MAX_VERTEX_NUM], top = -1; printf("%d ", v); visited[v] = 1; stack[++top] = v; // 起始顶点入栈 while (top != -1) { int current = stack[top]; // 获取栈顶，但不弹出 int w; for (w = 0; w < G->vertexNum; w++) { if (G->edges[current][w] != 0 && !visited[w]) { break; // 找到一个未访问的邻接点 } } if (w < G->vertexNum) { // 找到了这样的邻接点w printf("%d ", w); visited[w] = 1; stack[++top] = w; // 访问并入栈，相当于递归深入 } else { top--; // 当前顶点所有邻接点都已访问，弹出栈顶，相当于递归返回 } } }

非递归实现的难点：关键在于“获取栈顶元素但不弹出，只有当其所有邻接点都被访问后才弹出”。如果像BFS用队列那样，访问完就出队，那就错了。上面的代码中，current始终是栈顶元素，我们在这个顶点的邻接点中寻找下一个目标。找到就访问并入栈，找不到就将该顶点弹出。

实操心得：非递归DFS的写法有很多变种，另一种常见写法是每次都将一个顶点的一个未访问邻接点入栈并访问，然后break出循环，下次循环继续处理新栈顶。这同样可行。选择一种你理解最透彻的，并保持一致。

5. 广度优先搜索（BFS）实现详解

5.1 队列辅助的标准实现

BFS必须使用队列，这是其“广度”特性的要求。

邻接矩阵版BFS：

void BFS_Matrix(MGraph* G, int v) { int queue[MAX_VERTEX_NUM], front = 0, rear = 0; printf("%d ", v); visited[v] = 1; queue[rear++] = v; // 入队 while (front != rear) { int current = queue[front++]; // 出队 for (int w = 0; w < G->vertexNum; w++) { if (G->edges[current][w] != 0 && !visited[w]) { printf("%d ", w); visited[w] = 1; queue[rear++] = w; // 入队 } } } }

邻接表版BFS：

void BFS_List(ALGraph* G, int v) { int queue[MAX_VERTEX_NUM], front = 0, rear = 0; printf("%d ", v); visited[v] = 1; queue[rear++] = v; while (front != rear) { int current = queue[front++]; ArcNode* p = G->vertices[current].firstarc; while (p != NULL) { int w = p->adjvex; if (!visited[w]) { printf("%d ", w); visited[w] = 1; queue[rear++] = w; } p = p->nextarc; } } }

BFS实现的要点：

1. 访问即入队：与DFS不同，BFS中顶点在被访问的同时就立即入队。这保证了队列中存储的都是已被访问、但其邻接点尚未被探索的顶点，符合“层层推进”的逻辑。
2. 出队操作的意义：从队列中取出一个顶点，意味着我们要开始探索它的所有邻接点了。
3. 层序信息：BFS天然可以计算顶点到起点的最短距离（无权图）。只需在入队时记录距离：distance[w] = distance[current] + 1。这是BFS一个非常重要的扩展应用。

5.2 遍历的初始化与驱动函数

无论是DFS还是BFS，一个健壮的遍历程序都需要一个驱动函数来处理非连通图，并正确初始化访问数组。

void TraverseGraph(MGraph* G) { // 以邻接矩阵为例 // 1. 初始化访问数组 for (int i = 0; i < G->vertexNum; i++) { visited[i] = 0; } // 2. 循环检查所有顶点，驱动遍历 for (int i = 0; i < G->vertexNum; i++) { if (!visited[i]) { // 选择一种遍历方式 // DFS_Matrix(G, i); // BFS_Matrix(G, i); printf("\n"); // 一个连通分量遍历结束，可以换行（根据题目要求） } } }

为什么需要驱动循环？因为图可能不是连通图。仅从指定顶点（比如0）开始一次遍历，可能无法到达所有顶点。这个驱动循环确保了每个顶点都会被检查到，从而遍历整个图的所有连通分量。这也是头歌平台测试用例常考的点。

6. 常见问题与调试技巧实录

在实际编码和调试头歌习题时，以下几个问题是高频雷区：

6.1 数组越界与顶点映射错误

• 问题：Segmentation fault或输出乱码。这通常是因为数组索引超出了[0, vertexNum-1]的范围。
• 排查：
  1. 检查顶点输入处理。如果顶点是字符（‘A’），你将其映射为0，那么输入边（‘A’， ‘B’）就应该转化为（0， 1）。确保映射函数正确。
  2. 在邻接矩阵的循环中，for (int w = 0; w < G->vertexNum; w++)，确保循环条件是w < vertexNum而不是w <= vertexNum。
  3. 在邻接表遍历链表时，确保while (p != NULL)的判断正确，不要访问p->adjvex时p已是NULL。

6.2 忘记处理无向图的对称性

• 问题：遍历序列不完整，或者对于无向图，从A能到B，但从B开始遍历却找不到A。
• 排查：在InsertEdge函数里，如果是无向图，插入边(v, w)后，必须再插入边(w, v)。在邻接矩阵中是给对称位置赋值，在邻接表中是创建两个边节点分别插入两个顶点的链表。这是最经典的错误之一。

6.3 访问标记数组未重置或作用域错误

• 问题：程序第一次运行正确，但同一个图遍历第二次，或者换一个测试用例时，输出为空或错误。
• 排查：
  1. visited数组必须在每次调用TraverseGraph或新的遍历开始前，全部重置为0。
  2. 确保visited数组的作用域和生命周期正确。如果它在遍历函数内部定义为静态数组，那么多次调用之间它的值会保留。通常建议在驱动函数开始处集中重置，或者将其作为全局变量（注意多组测试数据时要重置）。

6.4 非连通图输出格式错误

• 问题：平台判题要求每个连通分量的序列可能要以空格隔开，或者每个序列单独一行。
• 排查：仔细阅读题目输出说明。在驱动函数中，每次调用DFS/BFS开始一个新的连通分量遍历时，可能需要输出一个空格或换行。例如，可以在if (!visited[i])里面，在调用遍历函数前或后，按格式要求输出分隔符。

6.5 递归DFS栈溢出

• 问题：对于顶点数非常多（如数万）的深度很大的图（如一条长链），递归DFS可能导致调用栈溢出。
• 解决方案：在算法题中，顶点数通常可控。如果真遇到，应使用非递归的栈实现。这也是为什么掌握非递归实现有价值的原因。

调试技巧：

1. 小数据测试：用最简单的图（如3个顶点的链或三角形）手动模拟你的代码，用纸笔画出每一步visited数组、栈、队列的变化。
2. 打印调试：在关键位置（如访问顶点时、入栈/入队时、出栈/出队时）打印状态信息，与你的手动模拟对比。
3. 单元测试思维：分别测试：单顶点图、完全图、链状图、环状图、非连通图。确保你的代码在所有基础拓扑结构上都正确。
4. 边界检查：顶点数为0或1的图，你的程序能处理吗？这是平台常见的边界测试用例。

把这两种存储结构和两种遍历算法理解透彻、实现稳健，图论算法的大门才算真正推开。这些代码模板和避坑经验，足够你应对头歌的习题和大部分基础面试题了。剩下的，就是在更多复杂场景中应用和变通。