从零实现图的DFS与BFS遍历：C语言实战指南
当你第一次接触图论算法时，那些抽象的概念和复杂的数学符号可能会让你望而却步。但别担心，今天我们将用最接地气的方式，手把手带你用C语言实现图的两种基础遍历算法——深度优先搜索(DFS)和广度优先搜索(BFS)。这不是一篇充斥着理论推导的学术论文，而是一份能让你真正动手实践的编程指南。
1. 图的基础与存储结构
在开始编码之前，我们需要明确几个基本概念。图由**顶点(Vertex)和边(Edge)**组成，可以表示各种现实关系，比如社交网络中的好友关系、城市间的交通路线等。在C语言中，我们通常用两种方式存储图结构：
1.1 邻接矩阵表示法
邻接矩阵用一个二维数组来表示图中顶点之间的连接关系。对于有n个顶点的图，我们创建一个n×n的矩阵，如果顶点i到顶点j有边相连，则matrix[i][j]设为1，否则为0。
#define MAX 100 typedef struct { char vexs[MAX]; // 顶点集合 int vexnum; // 顶点数 int edgnum; // 边数 int matrix[MAX][MAX]; // 邻接矩阵 } Graph;这种表示法的优点是查找任意两个顶点之间是否有边非常高效(O(1)时间复杂度)，缺点是当图比较稀疏时会浪费大量空间。
1.2 邻接表表示法
邻接表为每个顶点维护一个链表，链表中存储该顶点直接相连的其他顶点。这种表示法特别适合稀疏图。
typedef struct _ENode { int ivex; // 该边所指向的顶点的位置 struct _ENode *next_edge; // 指向下一条弧的指针 } ENode; typedef struct _VNode { char data; // 顶点信息 ENode *first_edge; // 指向第一条依附该顶点的弧 } VNode; typedef struct { int vexnum; // 图的顶点的数目 int edgnum; // 图的边的数目 VNode vexs[MAX]; // 顶点数组 } LGraph;邻接表的空间效率更高，但查找两个顶点是否相邻需要遍历链表，时间复杂度为O(V)。
2. 深度优先搜索(DFS)实现
深度优先搜索就像走迷宫时选择一条路走到底，直到走不通再回溯。这种"不撞南墙不回头"的策略非常适合用递归实现。
2.1 邻接矩阵版的DFS
// 返回顶点v的第一个邻接顶点的索引 static int first_vertex(Graph G, int v) { for (int i = 0; i < G.vexnum; i++) if (G.matrix[v][i] == 1) return i; return -1; } // 返回顶点v相对于w的下一个邻接顶点索引 static int next_vertix(Graph G, int v, int w) { for (int i = w + 1; i < G.vexnum; i++) if (G.matrix[v][i] == 1) return i; return -1; } // DFS递归实现 static void DFS(Graph G, int i, int *visited) { visited[i] = 1; printf("%c ", G.vexs[i]); for (int w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w)) { if (!visited[w]) DFS(G, w, visited); } } // DFS遍历入口 void DFSTraverse(Graph G) { int visited[MAX] = {0}; // 初始化访问标记数组 printf("DFS: "); for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) DFS(G, i, visited); } printf("\n"); }2.2 邻接表版的DFS
static void DFS(LGraph G, int i, int *visited) { ENode *node; visited[i] = 1; printf("%c ", G.vexs[i].data); node = G.vexs[i].first_edge; while (node != NULL) { if (!visited[node->ivex]) DFS(G, node->ivex, visited); node = node->next_edge; } } void DFSTraverse(LGraph G) { int visited[MAX] = {0}; printf("DFS: "); for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) DFS(G, i, visited); } printf("\n"); }实际项目中，递归实现的DFS可能会因为递归深度过大导致栈溢出。对于大规模图，可以使用显式栈来模拟递归过程。
3. 广度优先搜索(BFS)实现
广度优先搜索像水波纹一样层层扩展，先访问离起点最近的顶点，再逐渐向外扩展。这种特性使得BFS非常适合寻找最短路径问题。
3.1 邻接矩阵版的BFS
void BFS(Graph G) { int queue[MAX]; // 辅助队列 int head = 0, rear = 0; // 队首和队尾指针 int visited[MAX] = {0}; // 访问标记数组 printf("BFS: "); for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { visited[i] = 1; printf("%c ", G.vexs[i]); queue[rear++] = i; // 入队 while (head != rear) { int j = queue[head++]; // 出队 for (int k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) { if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k]); queue[rear++] = k; } } } } } printf("\n"); }3.2 邻接表版的BFS
void BFS(LGraph G) { int queue[MAX]; int head = 0, rear = 0; int visited[MAX] = {0}; ENode *node; printf("BFS: "); for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { visited[i] = 1; printf("%c ", G.vexs[i].data); queue[rear++] = i; while (head != rear) { int j = queue[head++]; node = G.vexs[j].first_edge; while (node != NULL) { int k = node->ivex; if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k].data); queue[rear++] = k; } node = node->next_edge; } } } } printf("\n"); }4. 完整示例与测试
让我们用一个具体的图来测试我们的实现。考虑以下无向图：
A —— B —— E | \ | | | \ | | C —— D F —— G4.1 创建图并测试
Graph* create_example_graph() { char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'A', 'C'}, {'A', 'D'}, {'B', 'C'}, {'B', 'D'}, {'B', 'E'}, {'C', 'D'}, {'E', 'F'}, {'F', 'G'} }; Graph* pG = (Graph*)malloc(sizeof(Graph)); pG->vexnum = 7; pG->edgnum = 9; // 初始化顶点 for (int i = 0; i < pG->vexnum; i++) pG->vexs[i] = vexs[i]; // 初始化边 for (int i = 0; i < pG->edgnum; i++) { int p1 = get_position(*pG, edges[i][0]); int p2 = get_position(*pG, edges[i][1]); pG->matrix[p1][p2] = pG->matrix[p2][p1] = 1; } return pG; } int main() { Graph* pG = create_example_graph(); print_graph(*pG); DFSTraverse(*pG); // 输出: DFS: A B C D E F G BFS(*pG); // 输出: BFS: A B C D E F G free(pG); return 0; }4.2 性能对比与选择建议
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V+E) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(1) | O(E) |
| 检查邻接关系 | O(1) | O(V) |
| 适用场景 | 稠密图 | 稀疏图 |
选择建议：
- 当图比较密集(E接近V²)时，邻接矩阵更合适
- 当图比较稀疏时，邻接表能节省大量空间
- 如果需要频繁检查两个顶点是否相邻，邻接矩阵更有优势
- 如果需要频繁遍历某个顶点的所有邻居，邻接表效率更高
5. 常见问题与调试技巧
在实现图算法时，新手常会遇到一些典型问题。以下是几个常见陷阱及解决方法：
顶点访问标记忘记重置：在每次遍历前，确保visited数组被正确初始化为0。
内存泄漏：使用邻接表时，记得在程序结束时释放所有动态分配的节点内存。
重复访问：特别是在BFS中，顶点入队后应立即标记为已访问，而不是出队时才标记，否则可能导致同一顶点多次入队。
非连通图处理：外层循环确保访问所有连通分量，而不仅是从第一个顶点开始的连通分量。
调试时可以添加一些打印语句，比如：
printf("Visiting vertex %c\n", G.vexs[i]);或者在递归DFS中添加深度信息：
static void DFS(Graph G, int i, int *visited, int depth) { for (int s = 0; s < depth; s++) printf(" "); printf("Entering %c\n", G.vexs[i]); // ...其余代码... }6. 实际应用场景
理解DFS和BFS不能仅停留在理论层面，更重要的是知道它们能解决什么问题：
DFS的典型应用：
- 拓扑排序（课程安排、任务调度）
- 检测图中的环
- 寻找连通分量
- 解决迷宫问题
- 生成迷宫或随机地图
BFS的典型应用：
- 最短路径问题（无权图）
- 社交网络中查找关系链
- 网络爬虫的页面抓取策略
- 广播网络中的信息传播
- 图像处理中的区域填充
例如，假设我们要在社交网络中找出两个人之间的最短联系链，BFS就是最合适的算法。而从某个起点出发探索所有可能路径（如解决数独），DFS则更为适用。
7. 进阶优化与变体
掌握了基础实现后，我们可以考虑一些优化和变体：
- 迭代式DFS：用显式栈替代递归，避免栈溢出风险。
void DFS_iterative(Graph G, int start, int *visited) { int stack[MAX]; int top = -1; stack[++top] = start; visited[start] = 1; while (top >= 0) { int v = stack[top--]; printf("%c ", G.vexs[v]); // 为了保持与递归相同的访问顺序，需要逆序压栈 for (int w = G.vexnum - 1; w >= 0; w--) { if (G.matrix[v][w] && !visited[w]) { visited[w] = 1; stack[++top] = w; } } } }双向BFS：当起点和终点都已知时，从两端同时进行BFS，可以显著提高搜索效率。
加权图处理：对于带权图，DFS和BFS需要调整以适应权重考虑，或者使用更高级的算法如Dijkstra。
并行化实现：对于大规模图，可以考虑将BFS的每一层或DFS的不同分支并行处理。
8. 从理论到实践的思考
学习算法最有效的方式就是自己动手实现。在完成这些代码后，建议尝试以下练习：
- 修改代码，统计每个顶点的度（相邻顶点数量）
- 实现检测图中是否存在环的功能
- 添加功能找出图中的所有连通分量
- 尝试将邻接矩阵和邻接表相互转换
- 实现一个简单的社交网络关系分析工具
记住，理解算法的最好方式不是背诵代码，而是明白每个步骤为什么这样设计。当你能向别人清楚地解释DFS的"回溯"和BFS的"层级扩展"概念时，你才真正掌握了它们。
