克鲁斯克尔演算法维基百科,自由的 encyclopedia 克鲁斯克尔演算法(英语:Kruskal's algorithm)是一种用来寻找最小生成树的演算法[1],由美国数学家约瑟夫·克鲁斯克尔在1956年发表[2]。用来解决同样问题的还有普林演算法和布卢瓦卡演算法(英语:Borůvka's algorithm)等。三种演算法都是贪心算法的应用。和布卢瓦卡演算法不同的地方是,克鲁斯克尔演算法在图中存在相同权值的边时也有效。 Quick Facts 克鲁斯克尔演算法, 概况 ...克鲁斯克尔演算法概况类别最小生成树资料结构并查集复杂度平均时间复杂度 O ( | E | log | V | ) {\displaystyle O(|E|\log |V|)} 或 O ( | E | α ( | V | ) ) {\displaystyle O(|E|\alpha (|V|))} 空间复杂度 O ( | E | + | V | ) {\displaystyle O(|E|+|V|)} 相关变量的定义 V {\displaystyle V} 点集 E {\displaystyle E} 边集Close
克鲁斯克尔演算法(英语:Kruskal's algorithm)是一种用来寻找最小生成树的演算法[1],由美国数学家约瑟夫·克鲁斯克尔在1956年发表[2]。用来解决同样问题的还有普林演算法和布卢瓦卡演算法(英语:Borůvka's algorithm)等。三种演算法都是贪心算法的应用。和布卢瓦卡演算法不同的地方是,克鲁斯克尔演算法在图中存在相同权值的边时也有效。 Quick Facts 克鲁斯克尔演算法, 概况 ...克鲁斯克尔演算法概况类别最小生成树资料结构并查集复杂度平均时间复杂度 O ( | E | log | V | ) {\displaystyle O(|E|\log |V|)} 或 O ( | E | α ( | V | ) ) {\displaystyle O(|E|\alpha (|V|))} 空间复杂度 O ( | E | + | V | ) {\displaystyle O(|E|+|V|)} 相关变量的定义 V {\displaystyle V} 点集 E {\displaystyle E} 边集Close