（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第12讲 图的优先遍历

学科竞赛编程 C++ NOIP NOI IOI 1 图的深度优先遍历 第一步 顶点vi出发，访问，标记，找邻接顶点vi1 第二步 vi1出发，DFS访问和它邻接的所有顶点 第三步 转到第一步 ，直到所有和vi邻接的顶点全部被访问 第四步 继续选取图中其他未被访问顶点作为起始顶点，转第一步 遍历 完成 算法思想： 设初始状态时图中的所有顶点未被访问， 2 【 图的深度优先遍历 1→2→5，然后退回到2，退回到1。 3 1 5 2 4 1 图的深度优先遍历 5 4 3 1 2 1 2 【 1→2→5，然后退回到2，退回到1。 【 从1开始再访问点3 ，3没有未访问邻接点，退回到1 图的深度优先遍历 2 5 3 4 1 【 从1开始再访问点3 ，3没有未访问邻接点，退回到1 1 2 3 【 1→2→5，然后退回到2，退回到1。 【 再从1开始访问未被访问过的点4，再退回到1 【 图的深度优先遍历 　void dfs(int i) //图用数组模拟邻接表存储，访问点i 　{ 　　 visited[i] = true; //标记为已访问 　　 for (int j = 1; j <= num[i]; j++) //遍历与i相关联的所有未访问过的顶点 　　 if (!visited[g[i][j]]) 　　 dfs(g[i][j]); 　} 图的深度优先遍历 【 int main() { …… memset(visited,false,sizeof(visited)); for (int i = 1; i <= n; i++) //每一个点都作为起点尝试访问，因为不是从任何 //一点开始都能遍历整个图的，例如下图。 if (!visited[i]) dfs(i); …… return 0; } 1 2 5 4 3 以3为起点根本不能遍历整个图 第一步 顶点vi出发，访问 第二步 访问vi的所有邻接顶点 第三步 转第一步，分别以vi邻接的顶点进行遍历 第四步 继续选取图中未被访问顶点作为起始顶点，转第一步，直到全部遍历全部顶点 遍历 完成 算法思想： 图的广度优先遍历 设初始状态时图中的所有顶点未被访问 8 图的广度优先遍历 下图是有向图的广度优先搜索遍历示例(箭头)。 下图的BFS次序是：___________________________ v1 v2 v3 v4 v5 V1 2 V2 0 ʌ V3 3 V4 1 V5 1 1 3 ʌ 0 1 2 ʌ 3 ʌ 4 ʌ v1→ v2 → v4 → v3 → v5 9 【 图的广度优先遍历 void bfs(int i) { int j,k,open,closed; memset(q,0,sizeof(q)); open=0;closed=1;q[1]=i; cout<<i<<" "; visited[i]=1; while(open<closed){ open++;k=q[open]; for(j=1;j<=n;j++) if((a[k][j]==1)&&(visited[j]==0)){ visited[j]=1; closed++; q[closed]=j; } } } 像科学家一样思考 像工程师一样解决问题 11 $$