Sign in
or
Register
Courses
Textbook
Compiler
Contests
Topics
Computer Science. Textbook
圖論
生成树:Kruskal 算法
具有指定边权重的图中最小生成树的示例:
克鲁斯卡尔算法:
1) 按权重对边进行排序 以非递减顺序。
2) 我们形成一个 n 棵树的列表(每个顶点都是一棵树)。
3) 我们开始将这些树组合成最小生成树的过程:
遍历所有边,如果当前边的两端属于不同的子树,则合并这些子树。
4) 在所有边的枚举结束时,所有的顶点将属于同一个子树。