第17讲图2.ppt

①普里姆算法 Prim ②克鲁斯卡尔算法 Kruskal 二、图的连通性问题 2、最小代价生成树 Minimum Cost Spanning Tree 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 ①普里姆算法 Prim * * 授课者：章 英 E-mail：walking7876@ Essential of Lecture Seventeen ： 一、图的遍历（深度、广度） 二、最小生成树 三、普里姆算法 四、克鲁斯卡尔算法 难点 图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。 在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。 为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit[MAX]作为对顶点的标记，当顶点vi未被访问，visit[i]值为 0；当vi已被访问，则visit[i]值为 1。 一、图的遍历 Traversing Graph 图的遍历与 树的遍历有什么不同 有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 Depth_First Search 广度优先遍历 Breadth_First Search 一、图的遍历 一、图的遍历 从图中某顶点v出发： （1）访问顶点v；（2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历； 1、深度优先遍历 深一层递归 递归返回 深度优先遍历序列?入栈序列?出栈序列? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍历序列： V1 V2 V2 V4 V4 V5 V5 一、图的遍历 深一层递归 递归返回 深度优先遍历序列?入栈序列?出栈序列? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍历序列： V1 V2 V2 V4 V4 V5 V8 V8 一、图的遍历 深一层递归 递归返回 深度优先遍历序列?入栈序列?出栈序列? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍历序列： V1 V2 V2 V4 V4 V5 V8 一、图的遍历 深一层递归 递归返回 深度优先遍历序列?入栈序列?出栈序列? V1 V3 V2 V4 V5 V6 V7 V8 V1 遍历序列： V1 V7 V2 V4 V5 V8 V3 V3 V6 V6 V7 一、图的遍历 一、图的遍历 void DFSTraverse( Graph *G ) { int v, visited[MAX_VERTEX_NUM]; for(v=0; vG?vexnum;v++) visited[v]=0; for(v=0; vG?vexnum;v++) if( !visited[v] ) DFS(G,v,visited); } 例17-1.c 图的深度优先遍历算法 一、图的遍历 void DFS(Graph G, int v, int visited[ ]) { int w; visit[v]=1; printf( “%d, ”, v); for(w=FirstAdjVex(G,v); w0; w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w,visited); } 图的深度优先遍历算法 例17-1.c 一、图的遍历 V0 V7 V6 V5 V4 V3 V2 V1 0 1 2 3 4 5 6 7 V0 V1 V2 V3 V4 V5 V6 V7 1 2 0 1 1 5 7 7 3 0 6 4 2 6 5 2 4 3 图的深度优先遍历算法 算法分析 图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿firstarc链到nextarc 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2