最小边的点集合问题
来源：4-6 图的编码实战-最小生成树之克鲁斯卡尔算法（二）
慕慕9573698
2020-02-10 20:09
在算法第二步的找到最小边连接的点，并找出点所在的点集合，对点做出相应的处理，这样的目的是什么
写回答
关注
1回答
-
- 董瘦瘦
- 2020-02-26 20:45:04
这是克鲁斯卡尔算法的原理啊
在邻接矩阵里取出所有边后找出最小边
最小边对应的点不在集合中则添加进去
一个在的话则把另一个添加到该点集合中
两个都在同一个点集合中，只能抛弃这条边，为什么呢？因为会形成回环。例如：有一个点集合为{A,B,C}，要找的边为AC，对应两个点都在，再选AC这条边的话A-B,B-C,A-C就形成回环，所以在程序里continue跳过
两个点在不同的点集合中，说明这两个点集合代表的边可以通过当前这条边连接起来，对应程序里的处理就是拼接两个vector
数据结构探险之图篇
图是众多实际问题解决方案之源，从基础概念入手掌握图的处理
56337 学习 · 81 问题
相似问题