数据结构：思想与方法-翁惠玉-27783第十三章幻灯片.ppt

* 第13章 最小生成树 生成树与最小生成树 Kruskal算法 Prim算法 算法的正确性 * 生成树 A B C D E H M A B C D E H M 无向图G 无向图G的生成树 生成树是无向连通图的极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。 * 最小生成树 定义：加权无向图的所有生成树中边的权值（代价） 之和最小的树。 实例： 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 1 2 4 3 5 6 1 5 3 4 2 左图的最小代价生成树 * 第13章 最小生成树 生成树与最小生成树 Kruskal算法 Prim算法 算法的正确性 * Kruscal 算法 基本思想：考虑图中权值最小的边。如果加入这条边不会导致回路，则加入；否则考虑下一条边，直到包含了所有的顶点 实现： 初始时，设置生成树为（V，Φ），如果V有n个顶点，则初始的生成树为具有n个连通分量的树。 按权值的大小逐个考虑所有的边，如果改变的加入能连接两个连通分量，则加入。当生成树只有一个连通分量时，算法结束。 * 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 1、初始连通分量：{1},{2},{3},{4},{5},{6} 2、反复执行添加、放弃动作。 边 动作 连通分量 (1,3) 添加 {1,3},{4},{5},{6},{2} (4,6) 添加 {1,3},{4, 6},{2},{5} (2,5) 添加 {1,3},{4, 6},{2,5} (3,6) 添加 {1,3,4, 6},{2,5} (1,4) 放弃 因构成回路 (3,4) 放弃 因构成回路 (2,3) 添加 {1,3,4,5,6,2} 最小代价生成树 1 2 4 3 5 6 1 5 3 4 2 * 算法难点及解决方案 如何从所有边中选择代价最小的边：用一个优先级队列来实现。将所有的边放入一个优先级队列，边的优先级就是它的权值。权值越小，优先级越高。 如何判断加入一条边后会不会形成回路：用并查集来实现。将一个连通分量表示为并查集中的一个子集，检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行Find操作。如果两个Find的结果相同，则表示两个端点已连通，加入这条边会形成回路，否则将这条边加入生成树。添加边的操作就是一个Union操作，将两个端点所属的子集归并起来，表示其中的所有顶点都已连通。 * 定义优先级队列中的元素类型 struct edge { int beg, end; TypeOfEdge w; bool operator(const edge rp) const {return w rp.w;} }; * kruskal算法的实现 template class TypeOfVer, class TypeOfEdge void adjListGraphTypeOfVer, TypeOfEdge::kruskal( ) const { int edgesAccepted = 0，u, v; edgeNode *p; edge e; DisjointSet ds( Vers ); priorityQueueedge pq; //生成优先级队列 for (int i = 0; i Vers; ++i) { for (p = verList[i].head; p != NULL; p = p-next) if (i p-end) { e.beg = i; e.end = p-end; e.w = p-weight; pq.enQueue(e); } } * //开始归并 while( edgesAccepted Vers - 1 ) { e = pq.deQueue(); u = ds.Find(e.beg); v = ds.Find(e.end); if( u != v ) { edgesAccepted++; ds.Union( u, v ); cout ( verList[e.beg].ver ,