C语言实现图的深度优先与广度优先遍历：从邻接表到工程实践
1. 从“图”到“遍历”：一个程序员的日常挑战
最近在重构一个老旧的设备管理模块，里面用邻接表存储了设备间的通信拓扑。我需要找出所有能从主控节点访问到的设备，来做一个状态同步。这听起来就是个典型的图遍历问题。我翻出了大学时的《数据结构》课本，找到了图的深度优先和广度优先遍历算法。纸上谈兵总是简单的，但当我准备用C语言把它实现出来，并集成到现有项目里时，才发现从理论到可运行、可调试的代码，中间隔着不少沟壑。比如，如何高效地表示一个图？递归实现的DFS在嵌入式环境里栈溢出怎么办？BFS队列的大小又该如何确定？这些都是在课本例题里不会细讲，但实际编码时必须面对的“魔鬼细节”。今天，我就结合这个实际需求，把手写C语言图遍历代码的整个过程，包括核心思想、代码实现、调试技巧以及我踩过的那些坑，完整地梳理一遍。无论你是正在学习数据结构的学生，还是需要处理类似图论问题的开发者，希望这篇“实战笔记”都能给你带来直接的参考价值。
2. 图的表示：选择邻接矩阵还是邻接表？
在动手写遍历算法之前，第一个要决定的就是图的存储结构。这直接影响了后续算法的效率和实现的复杂度。主流有两种方式：邻接矩阵和邻接表。
2.1 邻接矩阵：直观但可能浪费空间
邻接矩阵用一个二维数组来表示图。假设图有n个顶点，我们就创建一个n x n的矩阵matrix。如果顶点i到顶点j之间存在一条边，那么matrix[i][j]的值就设为1（对于无权图）或边的权重（对于有权图）；如果不存在边，则设为0或一个特定的无穷大值。
它的优点非常明显：
- 直观：检查两个顶点之间是否有边，时间复杂度是 O(1)，直接数组下标访问即可。
- 适合稠密图：当图的边数量接近顶点数的平方时，空间利用率高。
但缺点也同样突出：
- 空间复杂度高：需要 O(n²) 的空间。对于一个有1000个顶点但只有2000条边的稀疏图来说，矩阵里绝大部分空间存储的都是0，是极大的浪费。
- 添加/删除顶点麻烦：需要动态调整二维数组的大小，操作成本高。
在我遇到的设备拓扑场景里，设备数量（顶点）可能上百，但每个设备通常只和少数几个邻居通信（边很稀疏）。用邻接矩阵就像用一个大广场来存放几辆自行车，显然不合适。
2.2 邻接表：灵活且节省空间
邻接表则像是一个“拉链”数组。我们维护一个大小为n的数组（或链表），数组的每个元素对应一个顶点。这个元素本身是一个链表（或其他动态容器），链表中存储了所有与该顶点直接相邻的顶点信息。
它的优缺点几乎和邻接矩阵互补：
- 空间效率高：存储所有顶点和边，空间复杂度是 O(n + e)，其中e是边数。对于稀疏图，这比邻接矩阵节省大量内存。
- 添加边/顶点灵活：在链表尾部添加即可，相对简单。
- 查找某条边稍慢：要判断顶点i到j是否有边，需要遍历i对应的链表，时间复杂度是 O(degree(i))。
对于我的设备管理模块，邻接表是更优的选择。它节省了宝贵的内存资源，并且添加新设备（顶点）或新的通信链路（边）也更加方便。
2.3 我们的C语言实现选择
基于以上分析，我们决定采用邻接表。在C语言中，没有现成的链表容器，我们需要自己构建。一个常见的结构定义如下：
// 定义图的最大顶点数，避免动态内存分配带来的复杂性（可根据项目调整） #define MAX_VERTEX_NUM 100 // 邻接表节点结构体，代表一条边 typedef struct ArcNode { int adjvex; // 该边指向的顶点位置（索引） struct ArcNode *nextarc; // 指向下一条边的指针 // int weight; // 如果是有权图，可以在这里添加权重字段 } ArcNode; // 顶点结构体 typedef struct VNode { char data; // 顶点的数据域，例如设备ID ArcNode *firstarc; // 指向第一条依附于该顶点的边 } VNode, AdjList[MAX_VERTEX_NUM]; // 图的结构体 typedef struct { AdjList vertices; // 邻接表 int vexnum, arcnum; // 图的当前顶点数和边数 } ALGraph;这样，我们就用VNode数组 (vertices) 存储了所有顶点，每个顶点通过firstarc指针串起一个由ArcNode构成的单链表，链表中的每个节点代表从该顶点出发的一条边。这个结构清晰且高效，是很多教科书和实际项目的首选。
注意：这里为了代码清晰，使用了固定大小的数组
AdjList[MAX_VERTEX_NUM]。在产品代码中，如果顶点数不确定，通常会使用动态内存分配（malloc）来创建顶点数组和边节点，但需要仔细管理内存，避免泄漏。本例采用静态数组简化了内存管理，便于我们聚焦于遍历算法本身。
3. 深度优先遍历：一条路走到黑，再回头
深度优先遍历的思想很像走迷宫：选择一条路径尽可能深地探索下去，直到走到尽头（没有未访问的邻接点），然后回溯到上一个分叉点，选择另一条未探索的路径继续深入。
3.1 算法核心思想与递归实现
DFS天然适合用递归来实现，代码非常简洁。其核心步骤是：
- 从某个起始顶点
v开始，访问它，并将其标记为“已访问”。 - 依次检查
v的每一个未被访问过的邻接点w。 - 对每个这样的
w，递归地调用DFS函数。 - 当
v的所有邻接点都被探索完毕，递归返回。
下面是用C语言实现的递归版DFS：
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 假设ALGraph结构体已定义 // 访问标志数组，全局变量，记录顶点是否被访问过 bool visited[MAX_VERTEX_NUM]; // 深度优先遍历递归函数 void DFS(ALGraph *G, int v) { // 访问顶点v，这里简单打印其索引，实际可能是处理设备数据 printf("Visit vertex: %d\n", v); visited[v] = true; // 标记为已访问 // 遍历顶点v的所有邻接点 ArcNode *p = G->vertices[v].firstarc; while (p != NULL) { int w = p->adjvex; // w是v的一个邻接点 if (!visited[w]) { // 如果w未被访问 DFS(G, w); // 递归访问w } p = p->nextarc; // 继续检查v的下一个邻接点 } } // 对外提供的DFS遍历接口，处理非连通图 void DFSTraverse(ALGraph *G) { // 初始化访问数组 for (int i = 0; i < G->vexnum; ++i) { visited[i] = false; } // 对每个未被访问的顶点调用DFS，确保非连通图的所有连通分量都被遍历 for (int i = 0; i < G->vexnum; ++i) { if (!visited[i]) { printf("\nStart DFS from vertex %d:\n", i); DFS(G, i); } } }3.2 递归的隐患与迭代实现方案
递归实现虽然优雅，但在实际项目中要慎用，尤其是在嵌入式系统或对栈空间有限制的环境中。深度很大的图（或退化成链状的图）可能导致递归调用层次过深，引发栈溢出。
因此，掌握用显式栈实现的迭代版DFS是一个重要的工程技能。思路是手动模拟递归调用的过程：
// 使用栈实现DFS（迭代版） void DFS_Iterative(ALGraph *G, int v) { // 创建一个栈（这里用数组简单模拟） int stack[MAX_VERTEX_NUM]; int top = -1; // 初始化访问数组（局部或全局） bool visited[MAX_VERTEX_NUM] = {false}; // 起始顶点入栈并标记 stack[++top] = v; visited[v] = true; while (top >= 0) { // 栈不为空 int current_v = stack[top--]; // 出栈 printf("Visit vertex: %d\n", current_v); // 访问 // 注意：这里需要将邻接点逆序入栈，以保证与递归版顺序一致（先入后出）。 // 如果想保持邻接点正序访问，可以先暂存再逆序入栈，或使用其他数据结构。 ArcNode *p = G->vertices[current_v].firstarc; // 为了简单，我们先正序遍历邻接点，但入栈顺序会导致访问顺序与递归相反。 // 更严谨的做法是先将所有未访问邻接点存入一个临时数组，再逆序压栈。 while (p != NULL) { int w = p->adjvex; if (!visited[w]) { visited[w] = true; // **关键点：入栈前就标记！避免重复入栈** stack[++top] = w; } p = p->nextarc; } } }实操心得：标记时机是坑点。在迭代DFS中，一定要在顶点入栈时就将其标记为已访问 (
visited[w] = true)，而不是在出栈访问时才标记。如果出栈时才标记，同一个顶点可能会被其他路径重复压入栈中多次，导致栈空间浪费和逻辑错误。这与递归版本（调用前隐式入栈，调用时标记）的逻辑是内在统一的。
4. 广度优先遍历：层层递进，稳扎稳打
广度优先遍历的思想更像水波扩散：从起点开始，先访问所有直接相邻的顶点，然后再访问这些相邻顶点的相邻顶点（即下一层），以此类推。BFS通常用于寻找最短路径（在无权图中）。
4.1 算法核心思想与队列实现
BFS的实现必须借助队列（Queue）这个数据结构。步骤清晰：
- 访问起始顶点
v，标记并入队。 - 当队列不为空时，出队一个顶点
u。 - 遍历
u的所有未被访问的邻接点w，依次访问、标记，并将w入队。 - 重复步骤2和3，直到队列为空。
C语言实现如下（用数组模拟循环队列）：
// 广度优先遍历 void BFS(ALGraph *G, int v) { // 初始化访问数组 bool visited[MAX_VERTEX_NUM] = {false}; // 初始化队列（数组模拟循环队列） int queue[MAX_VERTEX_NUM]; int front = 0, rear = 0; // 访问并入队起始顶点 printf("Visit vertex: %d\n", v); visited[v] = true; queue[rear] = v; rear = (rear + 1) % MAX_VERTEX_NUM; while (front != rear) { // 队列不为空 int u = queue[front]; // 出队 front = (front + 1) % MAX_VERTEX_NUM; // 遍历u的所有邻接点 ArcNode *p = G->vertices[u].firstarc; while (p != NULL) { int w = p->adjvex; if (!visited[w]) { printf("Visit vertex: %d\n", w); visited[w] = true; // 入队 queue[rear] = w; rear = (rear + 1) % MAX_VERTEX_NUM; } p = p->nextarc; } } } // 针对非连通图的BFS遍历 void BFSTraverse(ALGraph *G) { bool visited[MAX_VERTEX_NUM] = {false}; for (int i = 0; i < G->vexnum; ++i) { if (!visited[i]) { printf("\nStart BFS from vertex %d:\n", i); // 这里需要重新调用BFS，但BFS函数内会重置visited，所以我们需要一个依赖外部visited数组的版本 // 更清晰的做法是：将BFS改造成接收visited数组参数的形式 BFS_With_Visited(G, i, visited); } } } // 改造后的BFS函数，接收visited数组 void BFS_With_Visited(ALGraph *G, int v, bool *visited) { int queue[MAX_VERTEX_NUM]; int front = 0, rear = 0; printf("Visit vertex: %d\n", v); visited[v] = true; queue[rear] = v; rear = (rear + 1) % MAX_VERTEX_NUM; while (front != rear) { int u = queue[front]; front = (front + 1) % MAX_VERTEX_NUM; ArcNode *p = G->vertices[u].firstarc; while (p != NULL) { int w = p->adjvex; if (!visited[w]) { printf("Visit vertex: %d\n", w); visited[w] = true; queue[rear] = w; rear = (rear + 1) % MAX_VERTEX_NUM; } p = p->nextarc; } } }4.2 队列的实现与选择
上面的代码使用了数组模拟的循环队列，这是嵌入式或无标准库环境中常见的做法。其关键是利用front和rear指针，并通过取模运算实现循环，有效利用数组空间。
#define MAX_QUEUE_SIZE 100 int queue[MAX_QUEUE_SIZE]; int front = 0, rear = 0; // 入队 if ((rear + 1) % MAX_QUEUE_SIZE != front) { // 队列未满 queue[rear] = value; rear = (rear + 1) % MAX_QUEUE_SIZE; } // 出队 if (front != rear) { // 队列非空 value = queue[front]; front = (front + 1) % MAX_QUEUE_SIZE; }如果开发环境允许使用C标准库，那么#include <queue>(C++) 或第三方库是更简单安全的选择。但在纯C环境，或者追求绝对可控性的场景（如我所在的嵌入式设备管理），自己实现一个轻量级队列是必备技能。
踩坑记录：队列大小估算。BFS队列的最大长度理论上可以达到图的最大顶点数（在最坏情况，如星型图，起点在中心）。但在实际中，如果图非常庞大，需要仔细估算内存。在我的项目中，我通过分析设备网络的最大可能直径和分支因子，将队列大小设置为一个合理的上限（如64），并加入了队列满的断言保护，防止内存越界。
5. 完整代码示例与调试实战
理论讲完了，我们来看一个完整的、可编译运行的例子。这个例子会创建一个简单的无向图，并分别用DFS和BFS进行遍历。
5.1 图的创建与初始化函数
首先，我们需要一个函数来创建图并添加边。对于无向图，添加一条边需要在两个顶点的邻接表里都插入节点。
// 查找顶点在顶点数组中的索引（这里假设顶点数据是字符，简单线性查找） int LocateVex(ALGraph *G, char data) { for (int i = 0; i < G->vexnum; ++i) { if (G->vertices[i].data == data) { return i; } } return -1; // 未找到 } // 向图中添加一条无向边 bool AddEdge(ALGraph *G, char v1, char v2) { int i = LocateVex(G, v1); int j = LocateVex(G, v2); if (i == -1 || j == -1) { printf("Error: Vertex not found!\n"); return false; } // 为顶点i的邻接表添加边(i, j) ArcNode *new_node1 = (ArcNode*)malloc(sizeof(ArcNode)); if (!new_node1) return false; new_node1->adjvex = j; new_node1->nextarc = G->vertices[i].firstarc; // 头插法 G->vertices[i].firstarc = new_node1; // 为顶点j的邻接表添加边(j, i) ArcNode *new_node2 = (ArcNode*)malloc(sizeof(ArcNode)); if (!new_node2) { free(new_node1); // 注意内存清理 G->vertices[i].firstarc = new_node1->nextarc; return false; } new_node2->adjvex = i; new_node2->nextarc = G->vertices[j].firstarc; G->vertices[j].firstarc = new_node2; G->arcnum++; return true; } // 初始化一个图，包含若干顶点 void InitGraph(ALGraph *G, char vexs[], int vex_count) { G->vexnum = vex_count; G->arcnum = 0; for (int i = 0; i < vex_count; ++i) { G->vertices[i].data = vexs[i]; G->vertices[i].firstarc = NULL; // 初始时邻接表为空 } }5.2 主函数：构建图并测试遍历
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // ... 将之前所有的结构体定义和函数声明放在这里 ... int main() { ALGraph G; // 初始化顶点：A, B, C, D, E, F char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F'}; int vex_count = sizeof(vexs) / sizeof(vexs[0]); InitGraph(&G, vexs, vex_count); // 添加边，构造一个简单的无向图 // 图结构大致如下： // A // / \ // B C // / \ \ // D E - F AddEdge(&G, 'A', 'B'); AddEdge(&G, 'A', 'C'); AddEdge(&G, 'B', 'D'); AddEdge(&G, 'B', 'E'); AddEdge(&G, 'C', 'F'); AddEdge(&G, 'E', 'F'); printf("Graph created with %d vertices and %d edges.\n", G.vexnum, G.arcnum); printf("\n========== Depth First Search (DFS) ==========\n"); DFSTraverse(&G); // 使用递归DFS printf("\n========== Breadth First Search (BFS) ==========\n"); // 由于BFSTraverse需要改造，这里直接从一个起点演示 bool visited_bfs[MAX_VERTEX_NUM] = {false}; printf("\nStart BFS from vertex A (index 0):\n"); BFS_With_Visited(&G, 0, visited_bfs); // 从'A'(索引0)开始BFS // 注意：这里没有释放邻接表动态分配的内存，实际项目务必添加销毁图的函数 // DestroyGraph(&G); return 0; }5.3 使用GDB进行调试：观察遍历过程
代码写好了，运行结果也符合预期。但作为开发者，我们不仅要看到结果，还要理解过程。GDB是一个强大的工具，可以帮助我们单步跟踪遍历的执行。
假设我们的可执行文件叫graph_traversal，编译时请加上-g选项以包含调试信息：
gcc -g graph_traversal.c -o graph_traversal然后使用GDB进行调试：
gdb ./graph_traversal在GDB中，我们可以：
- 设置断点：在DFS或BFS的关键函数入口处打断点。
(gdb) break DFS (gdb) break BFS_With_Visited - 运行程序：
(gdb) run - 单步执行：使用
next(执行下一行，不进入函数) 或step(进入函数) 来跟踪代码流。(gdb) next - 打印变量：在循环中，打印当前顶点、邻接点、栈或队列的状态，直观理解算法流程。
(gdb) print v (gdb) print visited[0]@6 // 打印visited数组的前6个元素 (gdb) print *p // 查看当前边节点信息 - 观察递归调用栈：在递归DFS中，使用
backtrace命令查看当前的调用层次。(gdb) backtrace
通过GDB，你可以清晰地看到递归如何一层层深入，栈如何变化，以及BFS中队列的入队出队顺序。这对于理解算法本质和排查复杂图结构下的逻辑错误至关重要。
6. 从理论到工程：性能考量与扩展思考
把基础的遍历代码跑通只是第一步。在真实的工程项目中，我们需要考虑更多。
6.1 时间复杂度与空间复杂度分析
- 时间复杂度：对于邻接表表示的图，DFS和BFS都需要检查每个顶点和每条边。每个顶点被访问一次，每条边被检查两次（无向图）。因此，时间复杂度是O(|V| + |E|)，其中|V|是顶点数，|E|是边数。这是非常高效的。
- 空间复杂度：
- 递归DFS：主要消耗在调用栈上，最坏情况（如图是一条链）是 O(|V|)。
- 迭代DFS/BFS：消耗在显式栈或队列上，最坏情况也是 O(|V|)。
6.2 处理大规模图与非连通图
我们的DFSTraverse和BFSTraverse函数已经考虑到了非连通图的情况，通过一个外部循环检查所有顶点是否被访问，从而遍历所有连通分量。这是必须的，因为你不能假设你的设备网络一定是全连通的。
对于大规模图（顶点数成千上万），内存管理变得关键：
- 动态内存分配：将
AdjList从静态数组改为动态分配的指针数组。 - 避免全局
visited数组：对于超大规模图，用一个独立的visited数组可能浪费空间。可以考虑使用位图或者将访问标记嵌入顶点结构体中。 - 迭代法优先：始终使用迭代版的DFS/BFS，避免递归栈溢出风险。
6.3 扩展应用：不仅仅是遍历
图的遍历是许多高级算法的基础：
- 连通性检测：调用一次DFS/BFS，看是否能访问所有顶点。
- 寻找路径：在BFS/DFS过程中，记录每个顶点的“前驱”顶点，就可以在访问到目标点时，反向回溯出完整路径。BFS找到的是无权图的最短路径。
- 拓扑排序：基于DFS，用于有向无环图的任务调度。
- 检测环：在DFS过程中，如果遇到一条指向已访问过的祖先顶点的边（在递归栈中），则说明存在环。
在我的设备管理项目中，基于BFS的遍历，我很容易就能计算出每个设备到主控节点的“跳数”（最短路径长度），这对于评估网络延迟和制定同步策略非常有帮助。
最后，关于代码本身，一个健壮的工程实现还应该包括：图的销毁函数（释放所有动态分配的边节点）、错误处理（如内存分配失败、顶点查找失败）、以及更通用的接口设计（支持带权图、有向图等）。把这些都考虑到，你的图遍历代码才能真正从“实验代码”变为“项目代码”。