1. 深度优先搜索（DFS）
1.1 DFS 的原理
深度优先搜索的核心思想是“一条路走到黑”。从起始顶点出发，沿着一条路径一直往下走，直到无法继续前进时，再回退到上一个分岔口，选择另一条路径继续探索。这个过程很像走迷宫时，先沿着一条路走到底，遇到死胡同再回头换一条路。
这种“走到底再回头”的策略，决定了 DFS 会优先深入图的深处，而不是先访问同一层的其他顶点。因此，DFS 天然适合用来解决连通性判断、路径查找、拓扑排序等问题。
1.2 DFS 的递归实现
递归是实现 DFS 最自然的方式。我们定义一个递归函数，每次访问一个顶点时，先标记它为已访问，然后依次对它的所有未访问的邻居顶点递归调用自身。下面是用 C 语言实现的递归 DFS 代码：
#include <stdio.h> #include <stdbool.h> #define MAX_VERTICES 100 // 邻接矩阵 int graph[MAX_VERTICES][MAX_VERTICES]; bool visited[MAX_VERTICES]; int vertexCount; // 递归深度优先搜索 void dfsRecursive(int vertex) { visited[vertex] = true; printf("访问顶点: %d\n", vertex); for (int i = 0; i < vertexCount; i++) { if (graph[vertex][i] == 1 && !visited[i]) { dfsRecursive(i); } } } int main() { // 初始化图（示例：5 个顶点） vertexCount = 5; // 这里省略图的初始化赋值代码 // 从顶点 0 开始遍历 dfsRecursive(0); return 0; }递归实现代码简洁，逻辑清晰，非常适合初学者理解 DFS 的思想。但递归调用会占用系统栈空间，当图的规模很大时，可能会导致栈溢出。
1.3 DFS 的非递归实现
非递归实现使用显式的栈来模拟递归过程。我们先把起始顶点压入栈，然后循环执行：弹出栈顶顶点，如果它未被访问则标记并访问，再将其所有未访问的邻居压入栈。下面是 C 语言的非递归实现：
#include <stdio.h> #include <stdbool.h> #define MAX_VERTICES 100 #define STACK_SIZE 100 int graph[MAX_VERTICES][MAX_VERTICES]; bool visited[MAX_VERTICES]; int vertexCount; int stack[STACK_SIZE]; int top = -1; void push(int value) { if (top < STACK_SIZE - 1) { stack[++top] = value; } } int pop() { if (top >= 0) { return stack[top--]; } return -1; } bool isEmpty() { return top == -1; } // 非递归深度优先搜索 void dfsIterative(int startVertex) { push(startVertex); while (!isEmpty()) { int vertex = pop(); if (!visited[vertex]) { visited[vertex] = true; printf("访问顶点: %d\n", vertex); // 将未访问的邻居压入栈 for (int i = vertexCount - 1; i >= 0; i--) { if (graph[vertex][i] == 1 && !visited[i]) { push(i); } } } } } int main() { vertexCount = 5; // 这里省略图的初始化赋值代码 dfsIterative(0); return 0; }非递归实现避免了递归调用带来的栈溢出风险，但代码相对复杂一些。两种实现方式访问顶点的顺序可能略有不同，但都能正确完成遍历。
1.4 DFS 的时间复杂度
DFS 的时间复杂度取决于图的存储方式。如果使用邻接矩阵存储，遍历每个顶点的所有邻居需要检查一整行，因此时间复杂度为 O(V²)，其中 V 是顶点数。如果使用邻接表存储，每条边只会被检查一次，时间复杂度为 O(V + E)，其中 E 是边数。空间复杂度方面，递归实现需要 O(V) 的递归栈空间，非递归实现需要 O(V) 的显式栈空间。
2. 广度优先搜索（BFS）
2.1 BFS 的原理
广度优先搜索的核心思想是“层层推进”。从起始顶点出发，先访问所有与它直接相连的邻居顶点，然后再依次访问这些邻居的邻居，就像水波一样一圈一圈向外扩散。这种策略保证了 BFS 总是先访问距离起始顶点最近的顶点。
由于 BFS 按层次推进的特性，它非常适合用来求解最短路径问题，尤其是在无权图中，BFS 找到的路径一定是最短路径。
2.2 BFS 的队列实现
BFS 使用队列来管理待访问的顶点。队列的特点是先进先出，这正好符合 BFS 逐层访问的需求。算法流程如下：先将起始顶点入队并标记为已访问，然后循环执行：从队首取出一个顶点并访问，再将其所有未访问的邻居入队并标记。下面是 C 语言的 BFS 实现：
#include <stdio.h> #include <stdbool.h> #define MAX_VERTICES 100 #define QUEUE_SIZE 100 int graph[MAX_VERTICES][MAX_VERTICES]; bool visited[MAX_VERTICES]; int vertexCount; int queue[QUEUE_SIZE]; int front = 0; int rear = 0; void enqueue(int value) { if (rear < QUEUE_SIZE) { queue[rear++] = value; } } int dequeue() { if (front < rear) { return queue[front++]; } return -1; } bool isQueueEmpty() { return front == rear; } // 广度优先搜索 void bfs(int startVertex) { enqueue(startVertex); visited[startVertex] = true; while (!isQueueEmpty()) { int vertex = dequeue(); printf("访问顶点: %d\n", vertex); for (int i = 0; i < vertexCount; i++) { if (graph[vertex][i] == 1 && !visited[i]) { enqueue(i); visited[i] = true; } } } } int main() { vertexCount = 5; // 这里省略图的初始化赋值代码 bfs(0); return 0; }注意，在 BFS 中，顶点在入队时就要标记为已访问，而不是在出队时标记。这样可以避免同一个顶点被重复加入队列，保证算法的正确性。
2.3 BFS 的时间复杂度
BFS 的时间复杂度与 DFS 相同。使用邻接矩阵时，时间复杂度为 O(V²)；使用邻接表时，时间复杂度为 O(V + E)。空间复杂度方面，BFS 需要 O(V) 的队列空间来存储待访问的顶点。
3. DFS 与 BFS 的对比
DFS 和 BFS 各有特点，适用于不同的场景。下面从几个维度进行对比：
| 对比维度 | 深度优先搜索（DFS） | 广度优先搜索（BFS） |
|---|---|---|
| 核心思想 | 一条路走到底，再回头 | 层层推进，逐层扩散 |
| 数据结构 | 栈（递归或显式栈） | 队列 |
| 时间复杂度 | O(V²) 或 O(V+E) | O(V²) 或 O(V+E) |
| 空间复杂度 | O(V) | O(V) |
| 最短路径 | 不保证最短 | 无权图中保证最短 |
| 典型应用 | 连通性判断、拓扑排序、回溯搜索 | 最短路径、层次遍历、社交网络好友推荐 |
简单来说，如果你需要找到一条路径，或者判断图是否连通，DFS 是不错的选择；如果你需要找到最短路径，或者按层次处理顶点，BFS 更合适。
4. 代码示例
下面给出一个完整的 C 语言程序，演示如何在实际项目中应用 DFS 和 BFS 遍历一个无向图。程序首先构建一个包含 6 个顶点的图，然后分别用两种算法进行遍历：
#include <stdio.h> #include <stdbool.h> #define MAX_VERTICES 100 // 图结构 typedef struct { int matrix[MAX_VERTICES][MAX_VERTICES]; int vertexCount; } Graph; // 初始化图 void initGraph(Graph *g, int count) { g->vertexCount = count; for (int i = 0; i < count; i++) { for (int j = 0; j < count; j++) { g->matrix[i][j] = 0; } } } // 添加无向边 void addEdge(Graph *g, int u, int v) { g->matrix[u][v] = 1; g->matrix[v][u] = 1; } // 深度优先搜索（递归） void dfs(Graph *g, int vertex, bool visited[]) { visited[vertex] = true; printf("%d ", vertex); for (int i = 0; i < g->vertexCount; i++) { if (g->matrix[vertex][i] == 1 && !visited[i]) { dfs(g, i, visited); } } } // 广度优先搜索（队列） void bfs(Graph *g, int startVertex) { bool visited[MAX_VERTICES] = {false}; int queue[MAX_VERTICES]; int front = 0, rear = 0; visited[startVertex] = true; queue[rear++] = startVertex; while (front < rear) { int vertex = queue[front++]; printf("%d ", vertex); for (int i = 0; i < g->vertexCount; i++) { if (g->matrix[vertex][i] == 1 && !visited[i]) { visited[i] = true; queue[rear++] = i; } } } } int main() { Graph g; initGraph(&g, 6); // 构建图：0-1, 0-2, 1-3, 1-4, 2-4, 3-5, 4-5 addEdge(&g, 0, 1); addEdge(&g, 0, 2); addEdge(&g, 1, 3); addEdge(&g, 1, 4); addEdge(&g, 2, 4); addEdge(&g, 3, 5); addEdge(&g, 4, 5); bool visited[MAX_VERTICES] = {false}; printf("深度优先搜索（DFS）遍历结果: "); dfs(&g, 0, visited); printf("\n"); printf("广度优先搜索（BFS）遍历结果: "); bfs(&g, 0); printf("\n"); return 0; }运行这个程序，你会看到 DFS 和 BFS 以不同的顺序访问图中的顶点。DFS 会沿着一条路径深入到底，而 BFS 会按层次逐层展开。你可以尝试修改图的连接关系，观察两种算法的遍历顺序如何变化，从而加深对它们的理解。
5. 总结
图的遍历是图算法的基础，DFS 和 BFS 是两种最核心的遍历策略。DFS 借助栈实现“深入优先”，适合解决连通性、路径搜索等问题；BFS 借助队列实现“广度优先”，适合解决最短路径、层次遍历等问题。两者的时间复杂度相同，选择哪种算法主要取决于具体问题的需求。
对于初学者来说，建议先理解两种算法的核心思想，再动手实现代码，最后通过实际例子观察它们的遍历顺序差异。掌握了 DFS 和 BFS，你就为学习更复杂的图算法（如最短路径、最小生成树等）打下了坚实的基础。
