|
|
知识路径： > 应用数学 > 图论应用 > 图论应用 > 最小生成树 >
|
|
相关知识点：2个
|
|
|
|
|
设T的初始状态只有n个顶点而无边的森林T=(V，φ)，按边长递增的顺序选择E中的n-1条安全边(u，v)并加入T，生成最小生成树。所谓安全边是指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。
|
|
|
|
克鲁斯卡尔算法的特点是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O(elog2e)，与图中顶点数无关，所以较适合于稀疏图。
|
|
|
|
|
|
|
|
例如，使用普里姆算法构造如上图所示的最小生成树的过程如下面5个图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
