克鲁斯克尔演算法維基百科,自由的 encyclopedia 克魯斯克爾演算法(英語:Kruskal's algorithm)是一種用來尋找最小生成樹的演算法[1],由美國數學家約瑟夫·克魯斯克爾在1956年發表[2]。用來解決同樣問題的還有普林演算法和布盧瓦卡演算法(英语:Borůvka's algorithm)等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是,克魯斯克爾演算法在圖中存在相同權值的邊時也有效。 事实速览 克鲁斯克尔演算法, 概况 ...克鲁斯克尔演算法概况類別最小生成树資料結構并查集复杂度平均時間複雜度 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} 边集关闭
克魯斯克爾演算法(英語:Kruskal's algorithm)是一種用來尋找最小生成樹的演算法[1],由美國數學家約瑟夫·克魯斯克爾在1956年發表[2]。用來解決同樣問題的還有普林演算法和布盧瓦卡演算法(英语:Borůvka's algorithm)等。三種演算法都是贪心算法的應用。和布盧瓦卡演算法不同的地方是,克魯斯克爾演算法在圖中存在相同權值的邊時也有效。 事实速览 克鲁斯克尔演算法, 概况 ...克鲁斯克尔演算法概况類別最小生成树資料結構并查集复杂度平均時間複雜度 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} 边集关闭