图_2.pptVIP

5.3 图的遍历 5.3.1 深度优先有哪些信誉好的足球投注网站遍历 从顶点v0出发，对图G进行深度优先有哪些信誉好的足球投注网站遍历（深度遍历）， dfs算法如下： (1)访问v0； (2)依次从v0的各个未被访问的邻接点出发深度遍历。 例：dfs(1) 1、dfs算法 dfs算法： void dfs（graph G，int v）//从v出发对图G进行深度遍历 {int w; visite(v); visited[v]=TRUE; //访问顶点v，并设置其访问标志 w=firstadj(G,v); //求v的第一个邻接点 while (w!=0) //当还存在邻接点时 {if (visited[w]==FALSE) dfs(G, w); //从没有访问过的邻接点出发深度遍历 w=nextadj(G,v,w); //求v的位于w之后的下一个邻接点 } } 遍历整个图的算法： 遍历图G要求访问到所有顶点，如果执行一次dfs(v)不能保证访问到所有顶点，则需要再选择未被访问的顶点作为起点重复调用dfs，直到所有顶点都被访问为止。 遍历图G的完整算法： void dfs_travel (graph G ) { int i; for (i=1; i=n; i++) visited[i]=FALSE; //初始化各顶点的访问标志 for (i=1; i=n; i++) if (visited[i]==FALSE) dfs(G,i); } 深度遍历算法的应用: 例：设计算法求无向图G的连通分量的个数。 5.3.1.3深度遍历算法的应用 int num(graph G) { int i; int k=0; for (i=1; i=n; i++) visited[i]=FALSE; for (i=1; i=n; i++) if (visited[i]==FALSE) { k++; dfs(G,i); } //累计连通分量数 return k ; } dfs算法的时间复杂度 5.3.2 广度优先有哪些信誉好的足球投注网站遍历 从顶点v0出发的广度遍历（bfs）算法如下： (1)访问v0（可作为访问的第一层）。 (2)依次访问v0的各邻接点v11，v12，…，v1k1（可作为访问的第二层）。 (3)假设最近一层的访问顶点依次为vi1，vi2，…，viki，则依次访问vi1，vi2，…，viki的未被访问的邻接点。 (4)重复（3），直到找不到未被访问的邻接点为止。 1、从指定顶点出发的广度遍历算法 bfs算法： void bfs(graph G, int v0) { int w; queue Q; init_queue(Q); visite(v0); visited[v0]=TRUE; En_queue(Q,v0); while (!empty(Q)) { v=del_queue(Q); w=firstadj(G,v); while (w!=0) {if (!visited[w]) { visite(w); visited[w]=TRUE; En_queue(Q,w); } w=nextadj(G,v); } } } 遍历整个图的算法： void bfs_travel(graph G) { int i; for (i=1; i=n; i++) visited[i]=FALSE; for (i=1; i=n; i++) if(!visited[i]) bfs(G,i); } 5.4 最小生成树 5.4.1 Prim算法 例：用Prim算法求解下图的最小生成树。 5.4.2 Kruskal算法 例：用Kruskal算法求解下图的最小生成树。 * * 9 1 2 3 4 5 6 7 8 10 8 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 10 9 图G的dfs(1)的执行过程示意图 访问序列：1,2,4,8,9,5,10,3,6,7 图G的深度遍历（dfs）生成树 先序遍历 用邻接矩阵表示图， O(n2) 用邻接表表示图， O(n+e) 8 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 10 9 图G的bfs(1)的执行过程示意图 访问