1. 深度优先搜索DFS1.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. 广度优先搜索BFS2.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(VE)O(V²) 或 O(VE)空间复杂度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你就为学习更复杂的图算法如最短路径、最小生成树等打下了坚实的基础。
1. 深度优先搜索DFS1.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. 广度优先搜索BFS2.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(VE)O(V²) 或 O(VE)空间复杂度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你就为学习更复杂的图算法如最短路径、最小生成树等打下了坚实的基础。
