Kruskal's - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

核心思想

• 贪婪算法
• 直接选择边权最小的边
• 具有相同权值的边，则可任意选取其中之一

算法步骤（最小生成树无环属性）

1. 把图所有的边都移除，并都放到一个优先队列中，按照边权从小到大排列
2. 把优先队列中的边按从小到大的顺序放回到图中，若出现环，就把该边丢弃
3. 直到全部的结点都连通

标准写法

要点

维护一个表储存边权，每次需要找到边权最小的边，优先队列或AVL树搜索的时间复杂度是0(logn)