深度优先搜索与广度优先搜索算法详解

一、先解答上次的思考题图顶点 0 1 2 3边0-1、0-2、1-2、2-3从 0 开始 DFS 一个可能结果0 1 2 3顺序不唯一只要符合深度优先规则都对二、今天学习目标理解BFS 广度优先遍历核心思想先访问离起点最近的一层一层扩散队列实现 BFS非递归稳邻接表 BFS 完整可运行代码三、什么是 BFSBFS Breadth First Search像水波扩散一样先访问起点再访问起点所有直接邻居第一层再访问邻居的邻居第二层……特点用队列实现可以保证最短路径无权图不会递归爆栈四、BFS 步骤起点入队标记 visitedwhile 队列不空出队一个节点 u 并访问遍历 u 的所有邻居 v若 v 未访问标记 visited 并入队五、完整代码邻接表 BFS#include stdio.h #include stdlib.h #define N 5 // 边节点 struct EdgeNode { int to; struct EdgeNode* next; }; // 顶点 struct Vertex { struct EdgeNode* head; } adj[N]; int visited[N]; // 队列 int queue[N]; int front 0, rear 0; // 初始化图 void init() { for (int i 0; i N; i) adj[i].head NULL; } // 添加无向边 void addEdge(int u, int v) { struct EdgeNode* e (struct EdgeNode*)malloc(sizeof(struct EdgeNode)); e-to v; e-next adj[u].head; adj[u].head e; struct EdgeNode* e2 (struct EdgeNode*)malloc(sizeof(struct EdgeNode)); e2-to u; e2-next adj[v].head; adj[v].head e2; } // BFS void bfs(int start) { printf(BFS遍历); visited[start] 1; queue[rear] start; while (front rear) { int u queue[front]; printf(%d , u); struct EdgeNode* p adj[u].head; while (p) { int v p-to; if (!visited[v]) { visited[v] 1; queue[rear] v; } p p-next; } } } int main() { init(); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(3, 4); bfs(0); return 0; }六、运行结果BFS遍历0 2 1 4 3顺序可能因邻接表插入顺序略有不同均正确七、DFS vs BFS 对比表格方式数据结构特点典型用途DFS递归 / 栈一条路走到底连通性、回溯、迷宫BFS队列一层一层扩散最短路径、层次遍历八、今日小练习图顶点0 1 2 3边0-10-21-22-3从 0 开始 BFS写出遍历顺序。典型答案0 1 2 3