从零实现图的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 邻接表版的DFSstatic 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 邻接矩阵版的BFSvoid 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 邻接表版的BFSvoid 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(VE)添加边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的层级扩展概念时你才真正掌握了它们。