别再死记硬背了！用C语言图解DFS和BFS，邻接表与邻接矩阵到底怎么选？-程序员充电站

图解C语言实现DFS与BFS：邻接表与邻接矩阵的黄金选择法则

刚接触图论算法的同学，往往会在实现深度优先搜索（DFS）和广度优先搜索（BFS）时陷入选择困境——该用邻接表还是邻接矩阵？这两种存储结构在代码实现上究竟有何不同？为什么教材和面试官总爱拿它们作比较？今天我们就用最直观的图解方式，配合可运行的C语言代码，彻底解决这个经典难题。

1. 图的遍历基础：理解DFS与BFS的本质差异

1.1 深度优先搜索（DFS）的递归特性

DFS就像走迷宫时坚持"右手法则"的探索者，它的核心特点是深度优先。想象你正在遍历一个社交网络的关系图：

// DFS递归核心代码 void DFS(int v, int visited[], Graph G) { visited[v] = 1; printf("%c ", G.vexs[v]); for (每个v的邻接点w) { if (!visited[w]) { DFS(w, visited, G); // 递归深入 } } }

DFS的典型特征包括：

栈结构：无论是显式栈还是函数调用栈，都遵循LIFO原则
路径探索：适合寻找连通分量、拓扑排序等场景
空间效率：最坏空间复杂度O(h)，h为图的最大深度

1.2 广度优先搜索（BFS）的层次特性

BFS则像水波纹扩散，总是先访问离起点最近的节点。这在寻找最短路径时特别有用：

// BFS队列实现核心代码 void BFS(Graph G, int start) { Queue Q; enqueue(Q, start); visited[start] = 1; while (!isEmpty(Q)) { v = dequeue(Q); for (每个v的邻接点w) { if (!visited[w]) { visited[w] = 1; enqueue(Q, w); // 广度扩展 } } } }

BFS的关键特点：

队列结构：严格遵循FIFO原则
最短路径：非加权图中的单源最短路径问题
空间消耗：最坏需要O(V)空间存储所有顶点

实际应用提示：当需要判断图的连通性或寻找最小跳数时，BFS通常是更好的选择；而需要回溯或探索所有可能路径时，DFS更合适。

2. 存储结构对决：邻接矩阵 vs 邻接表

2.1 邻接矩阵的实现解剖

邻接矩阵用二维数组表示顶点间的连接关系，特别适合稠密图：

typedef struct { char vexs[MAX]; // 顶点集合 int matrix[MAX][MAX]; // 邻接矩阵 int vexnum, edgenum; // 顶点和边数 } MGraph;

性能特征对比表：

操作	时间复杂度	空间复杂度
查询边存在	O(1)	O(V²)
遍历邻接点	O(V)	-
添加顶点	O(V)	-
添加边	O(1)	-

2.2 邻接表的链式结构

邻接表则采用数组+链表的形式，尤其适合稀疏图：

typedef struct ENode { int ivex; // 邻接点索引 struct ENode *next; // 下一条边指针 } EdgeNode; typedef struct { char data; // 顶点数据 EdgeNode *firstEdge; // 首边指针 } VertexNode; typedef struct { VertexNode vexs[MAX]; // 顶点数组 int vexnum, edgenum; // 顶点和边数 } LGraph;

操作效率对比：

操作	时间复杂度	空间复杂度
查询边存在	O(k)	O(V+E)
遍历邻接点	O(k)	-
添加顶点	O(1)	-
添加边	O(1)	-

注：k为顶点平均度数，在稀疏图中k≪V

3. 代码实战：不同存储结构下的遍历实现差异

3.1 邻接矩阵的DFS/BFS实现要点

在邻接矩阵中查找邻接点需要遍历整行：

// 邻接矩阵的邻接点查找 int firstAdjacent(MGraph G, int v) { for (int i = 0; i < G.vexnum; i++) if (G.matrix[v][i] == 1) return i; return -1; } int nextAdjacent(MGraph 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递归深度大时容易栈溢出
BFS需要额外空间存储队列
适合边密集的场景（边数接近V²）

3.2 邻接表的DFS/BFS实现优势

邻接表通过链表直接访问邻接点：

// 邻接表的DFS递归实现 void DFS(LGraph G, int v, int visited[]) { EdgeNode *p = G.vexs[v].firstEdge; visited[v] = 1; printf("%c ", G.vexs[v].data); while (p != NULL) { if (!visited[p->ivex]) { DFS(G, p->ivex, visited); } p = p->next; } }

这种结构的优势在于：