2023年8月1日发(作者：)

标准Kruskal算法及时间复杂度分析kruskal算法的标准实现⽅法是基于并查集的以下是《算法导论》上kruskal算法的伪代码翻译⼀下：（数字对应上图⾏号）1、初始化⽣成树的边集A为空集2、对集合中的每⼀个顶点，都将它的集合初始化为⾃⾝4、将边按权值进⾏排序5、对排序好后的边从⼩到⼤进⾏判断：如果这条边所连的2个顶点不在同⼀个集合中，则将这条边加⼊到⽣成树的边集A中，并将此边所连的两个顶点u和v的集合做⼀个Union操作，如此循环加到⽣成树中的边集数量为n-1时停⽌

时间复杂度分析：V代表节点数量，E代表边的数量1、初始化⽣成树的边集A为空集：O（1）2、对集合中的每⼀个顶点，都将它的集合初始化为⾃⾝：O（V）4、将边按权值进⾏排序：O（ElogE）5、对排序好后的边从⼩到⼤进⾏判断，如果这条边所连的2个顶点不在同⼀个集合中，则将这条边加⼊到⽣成树的边集A中，并将此边所连的两个顶点u和v的集合做⼀个Union操作，如此循环加到⽣成树中的边集数量为n-1时停⽌：O（V+E）α（V）具体证明过程在《算法导论》的并查集章节⾥由于各个⼦块不是嵌套的⽽是顺序的，所以时间复杂度取最⾼的那个即为O（ElogE）

2023年8月1日发(作者：)

标准Kruskal算法及时间复杂度分析kruskal算法的标准实现⽅法是基于并查集的以下是《算法导论》上kruskal算法的伪代码翻译⼀下：（数字对应上图⾏号）1、初始化⽣成树的边集A为空集2、对集合中的每⼀个顶点，都将它的集合初始化为⾃⾝4、将边按权值进⾏排序5、对排序好后的边从⼩到⼤进⾏判断：如果这条边所连的2个顶点不在同⼀个集合中，则将这条边加⼊到⽣成树的边集A中，并将此边所连的两个顶点u和v的集合做⼀个Union操作，如此循环加到⽣成树中的边集数量为n-1时停⽌

时间复杂度分析：V代表节点数量，E代表边的数量1、初始化⽣成树的边集A为空集：O（1）2、对集合中的每⼀个顶点，都将它的集合初始化为⾃⾝：O（V）4、将边按权值进⾏排序：O（ElogE）5、对排序好后的边从⼩到⼤进⾏判断，如果这条边所连的2个顶点不在同⼀个集合中，则将这条边加⼊到⽣成树的边集A中，并将此边所连的两个顶点u和v的集合做⼀个Union操作，如此循环加到⽣成树中的边集数量为n-1时停⽌：O（V+E）α（V）具体证明过程在《算法导论》的并查集章节⾥由于各个⼦块不是嵌套的⽽是顺序的，所以时间复杂度取最⾼的那个即为O（ElogE）