为用Prim算法求最小生成树，需要哪些辅助变量

答案:2 悬赏:40 手机版

解决时间 2021-02-25 00:22

提问者网友：十年饮冰
2021-02-24 00:53

最佳答案

五星知识达人网友：独钓一江月
2021-02-24 02:23

你需要存一个图的必备变量
你需要一个数组 l[i] 记录第 i 个点所连的最小生成树边的边权
一个布尔数组 u[i] 记录第 i 个点是否已经作为起点拓展过
再有就是打擂台用的辅助变量了

全部回答

1楼网友：舊物识亽
2021-02-24 03:36

不好意思吖按照图弄那两个中间数组太久了。。。实现方法也有不同。我跟您说说我学的通用实现方法吧！点集合：a，代表已经扩展到的点。边集合b：代表待考虑的边，一开始为空。一开始从任意点出发，如0.此时集合a中只有点0。将和a相邻的所有边加入到b中。从b中选最短的一条边e。e的一个端点必不在a中，则将它加入a中。将不在a中的那个点的所有边加入b中，在b中删除边e 这样b中减少了一条边（先前的边中最短的）。在a中增加了一个新点，并且这个点的相关边加入了b中。而b中减少的这条边就是最小生成树的一条边。这样一来，调用以上两个步骤n-1次（有n个点），则可以得到n-1条线段，就是其最小生成树。如果不是很懂可以q我，我会用通俗的语言解释的^^ qq:328880142

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息