目录
2.深度优先搜索（Deepth First Search,DFS）
3.广度优先搜索（Breadth First Search,BFS）
1.为什么需要两种遍历方法？
- 解决不同问题：DFS适用于寻找路径、解决迷宫问题等需要深入探索的场景。BFS适用于寻找最短路径、分层搜索等需要广泛探索的场景。
- 效率和资源：DFS使用递归或栈实现，适合内存有限但递归深度不大的情况。BFS使用队列实现，适合图的层次不深，但节点数较多的情况。
- 结果的不同：DFS找到的路径可能不是最短路径，而BFS保证找到的路径是最短路径（无权图）。
假设小人出迷宫，需要找出从起点到绿色出口的位置：
根据深度优先遍历的思想：
小人需要从右上角一直探索到左下角，非常费时费力。
但如果使用，广度优先遍历呢？
根据广度优先的思想，层层向外探索：
小人最后找到的一定是最短路径：
不理解图示？请往下看：
2.深度优先搜索（Deepth First Search,DFS）
思想：
就像在迷宫中行走，选择一个方向不断往前走，直到无法再继续前进时才回头寻找其他路径。
具体过程：
- 从图的某个起始点开始。
- 访问这个节点，并将其标记为已访问。
- 选择一个未访问的邻居节点，重复步骤2。如果所有邻居节点都已访问，则回到上一个节点，继续选择未访问的邻居节点。
- 直到所有节点都被访问过。
伪代码：
void DFS ( Vertex V )
{ visited[ V ] = true;
for ( V 的每个邻接点 W )
if ( !visited[ W ] )
DFS( W );
}时间复杂度:
若有 N个顶点、 E条边，时间复杂度是
| 用邻接矩阵存储图 | O( |
| 用邻接表存储图 | O(N+E) |
3.广度优先搜索（Breadth First Search,BFS）
思想：
就像在同心圆中层层扩展，从起始点开始，先访问所有与起始点直接相连的节点，再访问与这些节点相连的节点，以此类推。
具体过程：
- 从图的某个起始点开始。
- 访问这个节点，并将其标记为已访问，同时将其邻居节点加入队列。
- 从队列中取出一个节点，访问它，并将它的所有未访问的邻居节点加入队列。
- 直到队列为空，所有节点都被访问过。
伪代码：
void BFS ( Vertex V )
{ visited[V] = true;
Enqueue(V, Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for ( V 的每个邻接点 W ){
if ( !visited[W] ) {
visited[W] = true;
Enqueue(W, Q);
}
}
}
}时间复杂度:
若有 N个顶点、 E条边，时间复杂度是
| 用邻接矩阵存储图 | O( |
| 用邻接表存储图 | O(N+E) |
图示：
C语言代码演示
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
} Graph;
void initializeGraph(Graph *g, int vertices) {
g->numVertices = vertices;
int i;
for (i = 0; i < vertices; i++) {
int j;
for (j = 0; j < vertices; j++) {
g->adjMatrix[i][j] = 0;
}
}
}
void addEdge(Graph *g, int src, int dest) {
g->adjMatrix[src][dest] = 1;
g->adjMatrix[dest][src] = 1; // 如果是无向图
}
// DFS 递归实现
void DFSUtil(Graph *g, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
int i;
for (i = 0; i < g->numVertices; i++) {
if (g->adjMatrix[v][i] == 1 && !visited[i]) {
DFSUtil(g, i, visited);
}
}
}
void DFS(Graph *g) {
bool visited[MAX_VERTICES] = {false};
int v;
for (v = 0; v < g->numVertices; v++) {
if (!visited[v]) {
DFSUtil(g, v, visited);
}
}
}
// BFS 实现
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 v = queue[front++];
printf("%d ", v);
int i;
for (i = 0; i < g->numVertices; i++) {
if (g->adjMatrix[v][i] == 1 && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
}
int main() {
Graph g;
initializeGraph(&g, 5);
addEdge(&g, 0, 1);
addEdge(&g, 0, 4);
addEdge(&g, 1, 2);
addEdge(&g, 1, 3);
addEdge(&g, 1, 4);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
printf("Depth First Search (DFS): ");
DFS(&g);
printf("\n");
printf("Breadth First Search (BFS) starting from vertex 0: ");
BFS(&g, 0);
printf("\n");
return 0;
}
