这是克鲁斯卡尔算法的原理啊
在邻接矩阵里取出所有边后找出最小边
最小边对应的点不在集合中则添加进去
一个在的话则把另一个添加到该点集合中
两个都在同一个点集合中,只能抛弃这条边,为什么呢?因为会形成回环。例如:有一个点集合为{A,B,C},要找的边为AC,对应两个点都在,再选AC这条边的话A-B,B-C,A-C就形成回环,所以在程序里continue跳过
两个点在不同的点集合中,说明这两个点集合代表的边可以通过当前这条边连接起来,对应程序里的处理就是拼接两个vector
顶顶顶
看边的数量的话也是可以的,因为不形成闭环,N-1 条边是一定与N个点相连接的。
这个等式表明两个结点位于同一集合里。这能够得到这两个结点可以通过其他结点相连的结论,所以如果A,B再直接相连便会形成闭环