【数据结构与算法】第38篇：图论（二）：深度优先搜索（DFS）与广度优先搜索（BFS）
·
一、图遍历的基本概念
1.1 为什么需要遍历
和树一样，图也需要一种方式“访问”所有顶点。但图可能有环，所以需要标记已访问的顶点，避免重复访问。
1.2 两种遍历方式
| 遍历方式 | 核心思想 | 数据结构 |
|---|---|---|
| DFS | 一条路走到底，回溯 | 栈（递归） |
| BFS | 一层层向外扩展 | 队列 |
二、深度优先搜索（DFS）
2.1 算法思想
从一个顶点出发，访问它的一个邻接点，再访问该邻接点的邻接点……直到无法继续，然后回溯。
示例图：
text
0 — 1
| |
2 — 3
从0出发的DFS：0 → 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;
}
运行结果：
text
DFS遍历序列: 0 1 3 2
2.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");
}
三、广度优先搜索（BFS）
3.1 算法思想
从一个顶点出发，先访问它的所有邻接点，再访问这些邻接点的邻接点，一层层向外扩展。
示例图（同上）：
从0出发的BFS：0 → 1 → 2 → 3
3.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;
}
运行结果：
text
BFS遍历序列: 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;
}
运行结果：
text
DFS(邻接表): 0 2 3 1 BFS(邻接表): 0 2 1 3
注意：由于邻接表使用头插法，边的顺序与添加顺序相反，所以遍历序列与邻接矩阵版本可能不同。
五、DFS与BFS的对比
5.1 遍历序列对比
以图 0-1, 0-2, 1-3, 2-3 为例：
| 遍历方式 | 序列（邻接矩阵） | 序列（邻接表头插） |
|---|---|---|
| DFS | 0,1,3,2 | 0,2,3,1 |
| BFS | 0,1,2,3 | 0,2,1,3 |
5.2 核心区别
| 对比项 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归） | 队列 |
| 空间复杂度 | O(树高) | O(最大宽度) |
| 最短路径 | 不保证 | 保证（无权图） |
| 连通分量 | 可找出 | 可找出 |
| 环检测 | 可检测 | 可检测 |
| 拓扑排序 | 适用 | 适用 |
5.3 时间复杂度
| 存储方式 | DFS | BFS |
|---|---|---|
| 邻接矩阵 | O(V²) | O(V²) |
| 邻接表 | O(V+E) | O(V+E) |
六、应用场景
| 应用 | 推荐 | 原因 |
|---|---|---|
| 迷宫寻路（最短路径） | BFS | 第一次到达即为最短 |
| 拓扑排序 | DFS | 后序输出 |
| 检测环 | DFS | 递归栈可追踪路径 |
| 连通分量 | DFS/BFS | 均可 |
| 二分图检测 | BFS | 按层染色 |
| 强连通分量 | DFS | Tarjan/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;
}
运行结果：
text
DFS: 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检测图中是否有环？
欢迎在评论区讨论你的答案。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
3
0- 0
已为社区贡献8条内容
所有评论(0)