圖論算法中最小生成樹（Minimum Spanning Tree，MST）問題是一個經典且具有重要實際意義的問題。Kruskal算法作為求解最小生成樹的常用算法之一，以其簡潔的思想和高效的實現，在網絡規劃、電路設計、聚類分析等眾多領域發揮著關鍵作用。本文我將深入剖析Kruskal算法的原理、詳細介紹其執行流程，并分別使用Python、C++和Java三種編程語言進行代碼實現，幫你全面掌握這一經典算法。

一、Kruskal算法的基本概念

1.1 最小生成樹

對于一個連通無向圖 (G=(V, E))，其中 (V) 是頂點集合，(E) 是邊集合，其最小生成樹是一個包含圖中所有頂點的樹狀子圖 (T=(V, E’))（(E’ \subseteq E)），并且滿足邊的權值之和最小。最小生成樹具有以下特點：

• 包含圖中的所有頂點，即頂點數為 (|V|)。
• 邊數為 (|V| - 1)，因為樹的邊數比頂點數少 1。
• 不存在回路（環），確保其樹狀結構。
• 邊的權值總和在所有滿足上述條件的子圖中最小。

1.2 Kruskal算法核心思想

Kruskal算法基于貪心策略，其核心思想是：從圖中所有邊中選擇權值最小的邊，若該邊的兩個頂點不在同一個連通分量中，則將這條邊加入到最小生成樹中；重復這個過程，直到最小生成樹包含圖中的所有頂點，或者邊的數量達到 (|V| - 1) 為止。通過不斷選擇局部最優（權值最小且不構成回路的邊），最終得到全局最優的最小生成樹。

二、Kruskal算法的執行流程

1. 初始化：將圖中的每條邊按照權值從小到大進行排序。同時，初始化一個用于存儲最小生成樹的邊集合 mst_edges，以及一個用于判斷頂點是否在同一個連通分量的并查集數據結構（可以使用數組或更復雜的并查集類實現）。
2. 遍歷邊：依次遍歷排序后的邊集合，對于每條邊 ((u, v, w))（其中 (u) 和 (v) 是邊的兩個頂點，(w) 是邊的權值）：
   • 使用并查集判斷頂點 (u) 和 (v) 是否在同一個連通分量中。如果不在同一個連通分量，說明將這條邊加入最小生成樹不會形成回路，則將該邊加入到 mst_edges 中，并通過并查集將 (u) 和 (v) 所在的連通分量合并。
   • 如果頂點 (u) 和 (v) 已經在同一個連通分量中，說明加入這條邊會形成回路，直接跳過該邊。
3. 結束條件：當最小生成樹的邊數達到 (|V| - 1) 時，或者遍歷完所有邊后，算法結束。此時，mst_edges 中存儲的邊集合即為圖的最小生成樹。
   

三、Kruskal算法的代碼實現

3.1 Python實現

def find(parent, i):if parent[i] == i:return ireturn find(parent, parent[i])def union(parent, rank, x, y):xroot = find(parent, x)yroot = find(parent, y)if rank[xroot] < rank[yroot]:parent[xroot] = yrootelif rank[xroot] > rank[yroot]:parent[yroot] = xrootelse:parent[yroot] = xrootrank[xroot] += 1def kruskalMST(graph):result = []i, e = 0, 0edges = []for u in range(len(graph)):for v, w in enumerate(graph[u]):if w > 0:edges.append((u, v, w))edges.sort(key=lambda item: item[2])parent = []rank = []for v in range(len(graph)):parent.append(v)rank.append(0)while e < len(graph) - 1 and i < len(edges):u, v, w = edges[i]i = i + 1x = find(parent, u)y = find(parent, v)if x != y:e = e + 1result.append((u, v, w))union(parent, rank, x, y)return resultgraph = [[0, 10, 6, 5, 0, 0],[10, 0, 0, 15, 0, 0],[6, 0, 0, 4, 7, 0],[5, 15, 4, 0, 0, 8],[0, 0, 7, 0, 0, 9],[0, 0, 0, 8, 9, 0]
]
print(kruskalMST(graph))

3.2 C++實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Edge {
public:int src, dest, weight;Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};bool compareEdges(const Edge& a, const Edge& b) {return a.weight < b.weight;
}int find(vector<int>& parent, int i) {if (parent[i] == i)return i;return find(parent, parent[i]);
}void unionSet(vector<int>& parent, vector<int>& rank, int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot])parent[xroot] = yroot;else if (rank[xroot] > rank[yroot])parent[yroot] = xroot;else {parent[yroot] = xroot;rank[xroot]++;}
}vector<Edge> kruskalMST(vector<vector<int>>& graph) {vector<Edge> edges;for (int u = 0; u < graph.size(); u++) {for (int v = 0; v < graph.size(); v++) {if (graph[u][v] > 0) {edges.push_back(Edge(u, v, graph[u][v]));}}}sort(edges.begin(), edges.end(), compareEdges);vector<int> parent(graph.size());vector<int> rank(graph.size(), 0);for (int i = 0; i < graph.size(); i++) {parent[i] = i;}vector<Edge> result;int e = 0, i = 0;while (e < graph.size() - 1 && i < edges.size()) {Edge next_edge = edges[i++];int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);if (x != y) {e++;result.push_back(next_edge);unionSet(parent, rank, x, y);}}return result;
}int main() {vector<vector<int>> graph = {{0, 10, 6, 5, 0, 0},{10, 0, 0, 15, 0, 0},{6, 0, 0, 4, 7, 0},{5, 15, 4, 0, 0, 8},{0, 0, 7, 0, 0, 9},{0, 0, 0, 8, 9, 0}};vector<Edge> mst = kruskalMST(graph);for (const auto& edge : mst) {cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;}return 0;
}

3.3 Java實現

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;class Edge implements Comparable<Edge> {int src, dest, weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}@Overridepublic int compareTo(Edge other) {return Integer.compare(this.weight, other.weight);}
}class Kruskal {static int find(int[] parent, int i) {if (parent[i] == i)return i;return find(parent, parent[i]);}static void union(int[] parent, int[] rank, int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot])parent[xroot] = yroot;else if (rank[xroot] > rank[yroot])parent[yroot] = xroot;else {parent[yroot] = xroot;rank[xroot]++;}}static List<Edge> kruskalMST(int[][] graph) {List<Edge> edges = new ArrayList<>();for (int u = 0; u < graph.length; u++) {for (int v = 0; v < graph.length; v++) {if (graph[u][v] > 0) {edges.add(new Edge(u, v, graph[u][v]));}}}Collections.sort(edges);int[] parent = new int[graph.length];int[] rank = new int[graph.length];for (int i = 0; i < graph.length; i++) {parent[i] = i;}List<Edge> result = new ArrayList<>();int e = 0, i = 0;while (e < graph.length - 1 && i < edges.size()) {Edge nextEdge = edges.get(i++);int x = find(parent, nextEdge.src);int y = find(parent, nextEdge.dest);if (x != y) {e++;result.add(nextEdge);union(parent, rank, x, y);}}return result;}
}public class KruskalAlgorithm {public static void main(String[] args) {int[][] graph = {{0, 10, 6, 5, 0, 0},{10, 0, 0, 15, 0, 0},{6, 0, 0, 4, 7, 0},{5, 15, 4, 0, 0, 8},{0, 0, 7, 0, 0, 9},{0, 0, 0, 8, 9, 0}};List<Edge> mst = Kruskal.kruskalMST(graph);for (Edge edge : mst) {System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);}}
}

四、算法復雜度分析

4.1 時間復雜度

Kruskal算法的時間復雜度主要由兩部分組成：

• 對邊進行排序的時間復雜度：假設圖中有 (E) 條邊，使用比較排序算法（如快速排序、歸并排序）對邊按權值排序，時間復雜度為 (O(E \log E))。由于在連通圖中 (E \geq V - 1)，所以 (O(E \log E)) 可以近似為 (O(E \log V))。
• 遍歷邊并判斷連通性和合并連通分量的時間復雜度：在最壞情況下，需要遍歷所有 (E) 條邊，每次遍歷需要使用并查集判斷頂點的連通性和合并連通分量，其時間復雜度近似為 (O(\alpha(V)))（(\alpha(V)) 是阿克曼函數的反函數，增長極其緩慢，在實際應用中可近似看作常數時間）。因此，遍歷邊的總時間復雜度為 (O(E \alpha(V)))，可近似為 (O(E))。

綜合以上兩部分，Kruskal算法的時間復雜度為 (O(E \log V))，其中 (E) 是邊的數量，(V) 是頂點的數量。

4.2 空間復雜度

Kruskal算法的空間復雜度主要取決于存儲圖的邊集合和并查集數據結構所需的空間：

• 存儲邊集合：需要存儲圖中的所有邊，邊的數量為 (E)，因此存儲邊集合的空間復雜度為 (O(E))。
• 并查集數據結構：需要存儲每個頂點的父節點信息和秩信息，頂點數量為 (V)，所以并查集的空間復雜度為 (O(V))。

綜合起來，Kruskal算法的空間復雜度為 (O(E + V))，在實際應用中，由于 (E \geq V - 1)，所以空間復雜度可近似為 (O(E))。

五、Kruskal算法應用場景

5.1 網絡布線

在構建計算機網絡、電力網絡等實際場景中，需要在多個節點之間進行連接，同時要使連接的成本最小。將各個節點看作圖的頂點，節點之間的連接看作邊，邊的權值可以是連接的成本（如鋪設電纜的長度、費用等），通過Kruskal算法可以找到成本最小的網絡連接方案，確保所有節點都能連通且總費用最低。

5.2 聚類分析

在數據聚類問題中，可以將數據點看作圖的頂點，頂點之間的距離（如歐幾里得距離）看作邊的權值。通過Kruskal算法構建最小生成樹，然后從最小生成樹中刪除權值較大的邊，將圖分割成多個連通分量，每個連通分量就對應一個聚類。這種方法可以根據不同的需求，通過調整刪除邊的策略，得到不同數量和規模的聚類結果 。

5.3 電路設計

在集成電路設計中，需要將多個電子元件連接起來，同時要盡量減少連線的長度，以降低電路的成本和功耗。將電子元件看作頂點，元件之間的連接看作邊，邊的權值為連線長度，利用Kruskal算法可以找到連接所有元件的最短連線方案，優化電路設計。

總結

Kruskal算法以其簡潔高效的貪心策略，成為求解最小生成樹問題的經典算法。通過對算法原理、執行流程的詳細講解，以及Python、C++、Java三種編程語言的代碼實現，我們深入理解了Kruskal算法的具體實現方式，事不宜遲，我們不妨找些算法題刷起來吧!

That’s all, thanks for reading!
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～