问答详情
源自:4-6 图的编码实战-最小生成树之克鲁斯卡尔算法(二)

最小边的点集合问题

在算法第二步的找到最小边连接的点,并找出点所在的点集合,对点做出相应的处理,这样的目的是什么


提问者:慕慕9573698 2020-02-10 20:09

个回答

  • 董瘦瘦
    2020-02-26 20:45:04

    这是克鲁斯卡尔算法的原理啊

    1. 在邻接矩阵里取出所有边后找出最小边

    2. 最小边对应的点不在集合中则添加进去

    3. 一个在的话则把另一个添加到该点集合中

    4. 两个都在同一个点集合中,只能抛弃这条边,为什么呢?因为会形成回环。例如:有一个点集合为{A,B,C},要找的边为AC,对应两个点都在,再选AC这条边的话A-B,B-C,A-C就形成回环,所以在程序里continue跳过

    5. 两个点在不同的点集合中,说明这两个点集合代表的边可以通过当前这条边连接起来,对应程序里的处理就是拼接两个vector