下面是求无向连同图最小生成树的一种算法.pdf

6.19 下面是求无向连同图最小生成树的一种算法 将图中所有边按权从大到小排序后为（e1,e2….em ） i=1; while (所剩边数顶点数） { 从图中删去ei 如果图不连通，则恢复ei I++ } 证明这个算法是正确的。 证明： 定理1： 如果一条边e 被删去了并且没有被恢复，那么被删去之前e 一定在某一个环里，并且在这个 环中e 的权最大。 证明： 设e 被删之前的图为G 。 如果e 被删去，并且没有被恢复，说明e 被删除后图G-{e}还是连通的。设e 连接的两个顶 点为A,B 。那么G-{e} 中存在A 到B 的通路p 。于是在G 中，p+{e}构成一个环。 显然，图G 中，边的集合p+{e} 中任何一条边被删除都不会破坏G 的连通性。因此，按照 已知条件，被删除的边e 一定是p+{e} 中权值最大的一条边。 定理2 ： 设C 为任意一个圈，e’是圈中权最大的边，那么G-{e’} 中的MST 也是G 中的MST 。 证明： 设 T 为 G 的任意一棵MST 。如果e’ ∈T，那么我们来证明可以构造出一个MST 为 T’使 w(T)=w(T’) ，并且e’不属于T’ 。 因为T 是MST ，那么T-{e’}分成两个连通分支G1,G2 设集合S={ e | e ∈G 且 e 的两端分别连接G1 中的某个顶点和G2 中的某个顶点} (1) e’为S 中权最小的元素。 反证法：拿一个比e’小的元素替换e’，得到一个更小的生成树，矛盾。 (2) 圈C 中，除了e’,至少还有一条边e’’ ∈S 设e’连接的两个顶点为A,B 。从C 中去掉e’后，A,B 之间还有一条路径p,不妨设A ∈G1,B ∈G2 。所以，C 中至少有一条边连接G1,G2 。 (3) W(e’’)=W(e’) W 表示权 因为e’是圈中权最大的边 于是由(1)(2)，得到W(e’’)=W(e’) 。再由(3)，得到W(e’’)=W(e) 。 于是，构造一棵树T’=T-{e’}+{e’’} 。显然，W(T’)=W(T) ，所以，T’是G 的最小生成树，并 且并且e’不属于T’ 。 由定理（1）(2)，每删去一条边后的G-{e} 的MST 和原来的图G 的MST 权重相同。得证。 7.2 唯一最小支撑树 设计一个程序，判断给定无向连通图 G 是否存在唯一一棵最小支撑树。允许直接 调用Prim 或Kruskal 的最小支撑树算法。函数原型为: bool uniqueMST(Graph G) 如果图G 具有唯一最小支撑树，返回true,否则返回false. 算法：先求出一棵MST,设为T 。 然后依次在G 中去掉T 的边ei,对于每个图G-{ei} 。求出它的MST 的权和Wi 如果所有的Wi 都大于W(T) ，那么G 的MST 是唯一的，否则不唯一。 算法时间复杂度为O(V^3) double SumOfWeight(Edge* T) { double W=0; foreach (Edge e in T) { W+=e.Weight; } return W; } //求一棵树的权和 bool uniqueMST(Graph G) { Edge* MST,TEMP; Prim(G,0,MST); //求一棵MST double W=SumOfWeight(MST),_W; //求MST的权和 foreach (Edge e in MST) { G.DeleteEdge(e); Prim(G,0,TEMP); _W=SumOfWeight(TEMP); if (_W==W) return false; G.AddEdge(e); } return true; } 思考题： 6.10 二分图: 二分图 非二分图 (2)判断一个连通图是否为二分图 算法：用 DFS,访问时用两种颜色标记结点。相邻的结点用不同的颜色。如果发现一个可以 到达的结点与当前结点同色，就不是二分图，否则是 bool dfs(Graph G,int V,bool CL) { G.Mark[V]=VISITED; G.Color[V]=CL; for (Edge e=G.FirstEdge(V)