【数据结构与算法】第38篇：图论（二）：深度优先搜索（DFS）与广度优先搜索（BFS）

一、图遍历的基本概念1.1 为什么需要遍历和树一样图也需要一种方式“访问”所有顶点。但图可能有环所以需要标记已访问的顶点避免重复访问。1.2 两种遍历方式遍历方式核心思想数据结构DFS一条路走到底回溯栈递归BFS一层层向外扩展队列二、深度优先搜索DFS2.1 算法思想从一个顶点出发访问它的一个邻接点再访问该邻接点的邻接点……直到无法继续然后回溯。示例图text0 — 1 | | 2 — 3从0出发的DFS0 → 1 → 3 → 2取决于邻接顺序2.2 递归实现c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 邻接矩阵图 typedef struct { int matrix[MAX_VERTICES][MAX_VERTICES]; int vertexCount; } Graph; // 初始化图 void initGraph(Graph *g, int n) { g-vertexCount n; for (int i 0; i n; i) { for (int j 0; j n; j) { g-matrix[i][j] 0; } } } // 添加边无向图 void addEdge(Graph *g, int u, int v) { g-matrix[u][v] 1; g-matrix[v][u] 1; } // DFS递归实现 void dfsRecursive(Graph *g, int vertex, int visited[]) { visited[vertex] 1; printf(%d , vertex); for (int i 0; i g-vertexCount; i) { if (g-matrix[vertex][i] 1 !visited[i]) { dfsRecursive(g, i, visited); } } } // DFS入口 void dfs(Graph *g, int start) { int visited[MAX_VERTICES] {0}; printf(DFS遍历序列: ); dfsRecursive(g, start, visited); printf(\n); } int main() { Graph g; initGraph(g, 4); addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 2, 3); dfs(g, 0); return 0; }运行结果textDFS遍历序列: 0 1 3 22.3 非递归实现显式栈c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 栈结构 typedef struct { int data[MAX_VERTICES]; int top; } Stack; void initStack(Stack *s) { s-top -1; } int isEmpty(Stack *s) { return s-top -1; } void push(Stack *s, int val) { s-data[s-top] val; } int pop(Stack *s) { return s-data[s-top--]; } // DFS非递归 void dfsIterative(Graph *g, int start) { int visited[MAX_VERTICES] {0}; Stack stack; initStack(stack); push(stack, start); visited[start] 1; printf(DFS(栈)遍历序列: ); while (!isEmpty(stack)) { int vertex pop(stack); printf(%d , vertex); for (int i g-vertexCount - 1; i 0; i--) { if (g-matrix[vertex][i] 1 !visited[i]) { visited[i] 1; push(stack, i); } } } printf(\n); }三、广度优先搜索BFS3.1 算法思想从一个顶点出发先访问它的所有邻接点再访问这些邻接点的邻接点一层层向外扩展。示例图同上从0出发的BFS0 → 1 → 2 → 33.2 队列实现c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 队列结构 typedef struct { int data[MAX_VERTICES]; int front; int rear; } Queue; void initQueue(Queue *q) { q-front q-rear 0; } int isEmpty(Queue *q) { return q-front q-rear; } void enqueue(Queue *q, int val) { q-data[q-rear] val; } int dequeue(Queue *q) { return q-data[q-front]; } // BFS void bfs(Graph *g, int start) { int visited[MAX_VERTICES] {0}; Queue queue; initQueue(queue); visited[start] 1; enqueue(queue, start); printf(BFS遍历序列: ); while (!isEmpty(queue)) { int vertex dequeue(queue); printf(%d , vertex); for (int i 0; i g-vertexCount; i) { if (g-matrix[vertex][i] 1 !visited[i]) { visited[i] 1; enqueue(queue, i); } } } printf(\n); } int main() { Graph g; initGraph(g, 4); addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 2, 3); bfs(g, 0); return 0; }运行结果textBFS遍历序列: 0 1 2 3四、完整代码演示邻接表版本c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 邻接表节点 typedef struct EdgeNode { int vertex; struct EdgeNode *next; } EdgeNode; // 顶点节点 typedef struct { EdgeNode *first; } VertexNode; // 图结构 typedef struct { VertexNode vertices[MAX_VERTICES]; int vertexCount; } GraphList; // 初始化 void initGraphList(GraphList *g, int n) { g-vertexCount n; for (int i 0; i n; i) { g-vertices[i].first NULL; } } // 添加边无向图 void addEdgeList(GraphList *g, int u, int v) { EdgeNode *e1 (EdgeNode*)malloc(sizeof(EdgeNode)); e1-vertex v; e1-next g-vertices[u].first; g-vertices[u].first e1; EdgeNode *e2 (EdgeNode*)malloc(sizeof(EdgeNode)); e2-vertex u; e2-next g-vertices[v].first; g-vertices[v].first e2; } // DFS递归邻接表 void dfsListRecursive(GraphList *g, int vertex, int visited[]) { visited[vertex] 1; printf(%d , vertex); EdgeNode *p g-vertices[vertex].first; while (p ! NULL) { if (!visited[p-vertex]) { dfsListRecursive(g, p-vertex, visited); } p p-next; } } void dfsList(GraphList *g, int start) { int visited[MAX_VERTICES] {0}; printf(DFS(邻接表): ); dfsListRecursive(g, start, visited); printf(\n); } // 队列 typedef struct { int data[MAX_VERTICES]; int front, rear; } Queue; void initQueue(Queue *q) { q-front q-rear 0; } int isEmpty(Queue *q) { return q-front q-rear; } void enqueue(Queue *q, int val) { q-data[q-rear] val; } int dequeue(Queue *q) { return q-data[q-front]; } // BFS邻接表 void bfsList(GraphList *g, int start) { int visited[MAX_VERTICES] {0}; Queue q; initQueue(q); visited[start] 1; enqueue(q, start); printf(BFS(邻接表): ); while (!isEmpty(q)) { int vertex dequeue(q); printf(%d , vertex); EdgeNode *p g-vertices[vertex].first; while (p ! NULL) { if (!visited[p-vertex]) { visited[p-vertex] 1; enqueue(q, p-vertex); } p p-next; } } printf(\n); } int main() { GraphList g; initGraphList(g, 4); addEdgeList(g, 0, 1); addEdgeList(g, 0, 2); addEdgeList(g, 1, 3); addEdgeList(g, 2, 3); dfsList(g, 0); bfsList(g, 0); return 0; }运行结果textDFS(邻接表): 0 2 3 1 BFS(邻接表): 0 2 1 3注意由于邻接表使用头插法边的顺序与添加顺序相反所以遍历序列与邻接矩阵版本可能不同。五、DFS与BFS的对比5.1 遍历序列对比以图0-1, 0-2, 1-3, 2-3为例遍历方式序列邻接矩阵序列邻接表头插DFS0,1,3,20,2,3,1BFS0,1,2,30,2,1,35.2 核心区别对比项DFSBFS数据结构栈递归队列空间复杂度O(树高)O(最大宽度)最短路径不保证保证无权图连通分量可找出可找出环检测可检测可检测拓扑排序适用适用5.3 时间复杂度存储方式DFSBFS邻接矩阵O(V²)O(V²)邻接表O(VE)O(VE)六、应用场景应用推荐原因迷宫寻路最短路径BFS第一次到达即为最短拓扑排序DFS后序输出检测环DFS递归栈可追踪路径连通分量DFS/BFS均可二分图检测BFS按层染色强连通分量DFSTarjan/Kosaraju算法深度优先的搜索如八皇后DFS需要回溯七、完整代码带图构建和双遍历c#include stdio.h #include stdlib.h #define MAX_VERTICES 100 // 图结构邻接表 typedef struct EdgeNode { int vertex; struct EdgeNode *next; } EdgeNode; typedef struct { EdgeNode *first; } VertexNode; typedef struct { VertexNode vertices[MAX_VERTICES]; int vertexCount; } Graph; // 初始化 void initGraph(Graph *g, int n) { g-vertexCount n; for (int i 0; i n; i) { g-vertices[i].first NULL; } } // 添加边 void addEdge(Graph *g, int u, int v) { EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-vertex v; e-next g-vertices[u].first; g-vertices[u].first e; e (EdgeNode*)malloc(sizeof(EdgeNode)); e-vertex u; e-next g-vertices[v].first; g-vertices[v].first e; } // DFS void dfs(Graph *g, int v, int visited[]) { visited[v] 1; printf(%d , v); EdgeNode *p g-vertices[v].first; while (p) { if (!visited[p-vertex]) { dfs(g, p-vertex, visited); } p p-next; } } void startDFS(Graph *g, int start) { int visited[MAX_VERTICES] {0}; printf(DFS: ); dfs(g, start, visited); printf(\n); } // BFS void bfs(Graph *g, int start) { int visited[MAX_VERTICES] {0}; int queue[MAX_VERTICES]; int front 0, rear 0; visited[start] 1; queue[rear] start; printf(BFS: ); while (front rear) { int v queue[front]; printf(%d , v); EdgeNode *p g-vertices[v].first; while (p) { if (!visited[p-vertex]) { visited[p-vertex] 1; queue[rear] p-vertex; } p p-next; } } printf(\n); } int main() { Graph g; initGraph(g, 6); // 构建图 addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 2, 4); addEdge(g, 3, 5); addEdge(g, 4, 5); startDFS(g, 0); bfs(g, 0); return 0; }运行结果textDFS: 0 2 4 5 3 1 BFS: 0 2 1 4 3 5八、小结这一篇我们学习了图的两种遍历方式遍历核心数据结构应用DFS深入到底回溯栈递归拓扑排序、环检测、连通分量BFS层层扩散按层队列最短路径无权图、二分图关键代码模板c// DFS模板 void dfs(Graph *g, int v, int visited[]) { visited[v] 1; for (邻接点 w) { if (!visited[w]) dfs(g, w, visited); } } // BFS模板 void bfs(Graph *g, int start) { 队列 q; visited[start] 1; q.push(start); while (q不空) { v q.pop(); for (邻接点 w) { if (!visited[w]) { visited[w] 1; q.push(w); } } } }下一篇我们讲最小生成树Prim算法与Kruskal算法。九、思考题为什么DFS通常用递归实现而BFS用队列实现可以互换吗在邻接矩阵表示的图中DFS和BFS的时间复杂度都是O(V²)哪个常数因子更小如果图是非连通的如何遍历所有顶点如何用DFS检测图中是否有环欢迎在评论区讨论你的答案。