现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序
题型:问答题
问题:
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(e1,e2,…,en);
i=1;
while(所剩边数>=顶点数)
从图中删去ei;
若图不再连通,则恢复ei;
i=i+1;
请问上述方法能否求得原图的最小生成树若该方法可行,请证明之;否则请举例说明。
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(e1,e2,…,en);
i=1;
while(所剩边数>=顶点数)
从图中删去ei;
若图不再连通,则恢复ei;
i=i+1;
请问上述方法能否求得原图的最小生成树若该方法可行,请证明之;否则请举例说明。