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