图搜索算法详解：广度优先搜索与深度优先搜索的探索之旅

news/2024/10/16 0:21:39/

算法>图搜索算法详解：广度优先搜索与深度优先搜索的探索之旅

1. 广度优先搜索（BFS）
- 1.1 伪代码
- 1.2 C语言实现
2. 深度优先搜索（DFS）
- 2.1 伪代码
- 2.2 C语言实现
3. 总结

算法>图搜索算法是计算机科学中用于在图结构中查找路径的算法。图由顶点（或节点）和边组成，它们可以表示各种类型的数据和它们之间的关系。算法>图搜索算法可以分为两大类：广度优先搜索（BFS）和深度优先搜索（DFS）。下面我将分别介绍这两种算法，并提供伪代码和C语言的实现示例。

在这里插入图片描述

1. 广度优先搜索（BFS）

广度优先搜索是一种遍历图的算法，它从一个节点开始，逐层遍历图中的所有节点。BFS常用于寻找最短路径。

1.1 伪代码

BFS(G, start_v):创建队列Q创建一个访问标记数组visited将start_v入队Qvisited[start_v] = truewhile Q非空:取出队列中的第一个节点vfor 每个节点v的邻居w:if w未被访问:将w入队Qvisited[w] = true

1.2 C语言实现

#include <stdio.h>
#include <stdlib.h>#define MAX_NODES 1000int visited[MAX_NODES]; // 访问标记数组
int graph[MAX_NODES][MAX_NODES]; // 邻接矩阵表示图
int numVertices; // 顶点数量void bfs(int start_v) {int Q[MAX_NODES], front = 0, rear = 0; // 用数组模拟队列visited[start_v] = 1;Q[rear++] = start_v; // 将起始顶点加入队列while (front != rear) {int v = Q[front++]; // 从队列中取出顶点printf("Visited: %d\n", v);for (int i = 0; i < numVertices; i++) {if (graph[v][i] && !visited[i]) {visited[i] = 1;Q[rear++] = i; // 将邻居加入队列}}}
}int main() {// 初始化图和顶点数量// ...// 调用BFS函数bfs(0); // 假设从顶点0开始return 0;
}

2. 深度优先搜索（DFS）

深度优先搜索是一种遍历图的算法，它从一个节点开始，尽可能深地搜索图的分支。当节点v的邻接边都已经被搜索过时，算法会回溯到前一个节点。

2.1 伪代码

DFS(G, v):如果v已经被访问过，则返回visited[v] = true访问顶点vfor 每个v的邻居w:如果w未被访问：DFS(G, w)

2.2 C语言实现

#include <stdio.h>
#include <stdlib.h>void dfs(int v) {visited[v] = 1;printf("Visited: %d\n", v);for (int i = 0; i < numVertices; i++) {if (graph[v][i] && !visited[i]) {dfs(i);}}
}int main() {// 初始化图和顶点数量// ...// 调用DFS函数dfs(0); // 假设从顶点0开始return 0;
}