算法學習筆記：9.Kruskal 算法——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

在圖論的眾多算法中，Kruskal 算法以其簡潔高效的特性，成為求解最小生成樹（Minimum Spanning Tree，MST）的經典方法。無論是在通信網絡的優化設計、電路布線的成本控制，還是在計算機考研 408 的備考過程中，Kruskal 算法都占據著重要的地位。

Kruskal 算法的基本概念

在介紹 Kruskal 算法之前，我們需要先明確幾個關鍵概念：

圖：由頂點（節點）集合和邊集合組成，邊可以有權值，用于表示頂點之間的關系和連接代價。

生成樹：對于一個連通圖，它的生成樹是包含圖中所有頂點的無環連通子圖。

最小生成樹：在帶權連通圖的所有生成樹中，邊的權值之和最小的生成樹稱為最小生成樹。

Kruskal 算法的目標，就是在給定的帶權連通圖中，找到這樣一棵最小生成樹。例如，在一個城市間的通信網絡建設中，每個城市是圖的頂點，城市間鋪設通信線路的成本是邊的權值，Kruskal 算法可以幫助我們找到成本最低的網絡連接方案。

Kruskal 算法的思想

Kruskal 算法基于貪心策略，其核心思想是：在圖中選取權值最小的邊，若該邊加入已選邊集合后不會形成環，則將其加入；不斷重復這個過程，直到選取的邊構成一棵包含圖中所有頂點的樹，此時得到的樹就是最小生成樹。

具體執行過程如下：

初始化：將圖中的所有邊按照權值從小到大進行排序，并初始化一個空的邊集合用于存儲最小生成樹的邊，同時將每個頂點看作一個獨立的集合（利用并查集數據結構實現）。

遍歷邊集：依次遍歷排序后的邊集合，對于每條邊，檢查其兩個端點是否屬于不同的集合（即是否會形成環）。如果屬于不同集合，則將該邊加入最小生成樹的邊集合中，并合并兩個端點所在的集合；如果屬于相同集合，則跳過該邊，因為加入后會形成環。

結束條件：當最小生成樹的邊集合中包含n - 1條邊時（n為圖中頂點的數量），停止遍歷，此時得到的邊集合構成的樹即為最小生成樹。

Kruskal 算法的解題思路

利用 Kruskal 算法解決實際問題時，一般遵循以下步驟：

構建圖模型：根據題目描述，將問題抽象為帶權連通圖，確定頂點集合、邊集合以及每條邊的權值。

初始化并查集：為圖中的每個頂點創建一個獨立的集合，用于后續判斷邊加入后是否會形成環。

邊排序：將圖中的所有邊按照權值從小到大進行排序。

執行 Kruskal 算法：遍歷排序后的邊集合，按照算法規則選取邊加入最小生成樹的邊集合中，同時使用并查集維護頂點集合的連通性。

處理結果：根據題目要求，返回最小生成樹的邊集合、邊的權值之和，或者進行其他相關處理。

LeetCode 例題及 Java 代碼實現

例題：網絡延遲時間（LeetCode 1135）

用以太網線纜將 n 臺計算機連接成一個網絡，計算機的編號從 0 到 n - 1。線纜用 connections 表示，其中 connections[i] = [a_i, b_i, cost_i] 連接計算機 a_i 和 b_i ，費用為 cost_i。請你計算將所有計算機連接成一個網絡的最低成本。如果無法將所有計算機連接成一個網絡，則返回 -1 。

解題思路

本題可以將計算機看作圖的頂點，線纜連接看作邊，連接費用看作邊的權值，問題轉化為求圖的最小生成樹的權值之和。使用 Kruskal 算法，先對邊按權值排序，然后通過并查集判斷邊加入后是否成環，逐步構建最小生成樹，最后計算最小生成樹的權值之和。如果最終選取的邊數小于n - 1，則說明無法連接所有計算機，返回 -1 。

代碼實現

import java.util.Arrays;import java.util.Comparator;public class MinimumCostToConnectSticks {// 并查集的父節點數組private int[] parent;// 初始化并查集private void init(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 查找節點的根節點private int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 合并兩個節點所在的集合private boolean union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;return true;}return false;}public int minimumCost(int n, int[][] connections) {init(n);// 按邊的權值從小到大排序Arrays.sort(connections, Comparator.comparingInt(c -> c[2]));int cost = 0;int count = 0;for (int[] connection : connections) {int a = connection[0] - 1;int b = connection[1] - 1;int weight = connection[2];if (union(a, b)) {cost += weight;count++;if (count == n - 1) {break;}}}return count == n - 1 ? cost : -1;}}

例題：重新安排行程（LeetCode 332）

給定一個機票的字符串二維數組 [from, to]，子數組中的兩個成員分別表示飛機出發和降落的機場地點，對該行程進行重新規劃排序。所有這些機票都屬于一個從 JFK（肯尼迪國際機場）出發的先生，所以該行程必須從 JFK 開始。

提示：

如果存在多種有效的行程，請你按字典排序返回最小的行程組合。例如，行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小，排序更靠前。

所有的機場都用三個大寫字母表示（機場代碼）。

假定所有機票至少存在一種合理的行程。

所有的機票必須都用一次且只能用一次。

解題思路

本題可以將機場看作頂點，機票看作邊，構建一個圖。由于要求按字典序最小的行程，我們可以先對邊（機票）進行排序，然后利用類似 Kruskal 算法的思想，從JFK出發，逐步選取邊構建路徑。在構建過程中，使用深度優先搜索（DFS）來遍歷圖，確保所有邊都被使用一次且僅一次。

代碼實現

import java.util .*;public class ReconstructItinerary {private Map<String, PriorityQueue<String>> graph;private List<String> result;private void dfs(String airport) {PriorityQueue<String> nextAirports = graph.get(airport);while (nextAirports != null && !nextAirports.isEmpty()) {dfs(nextAirports.poll());}result.add(0, airport);}public List<String> findItinerary(List<List<String>> tickets) {graph = new HashMap<>();for (List<String> ticket : tickets) {String from = ticket.get(0);String to = ticket.get(1);graph.putIfAbsent(from, new PriorityQueue<>());graph.get(from).offer(to);}result = new ArrayList<>();dfs("JFK");return result;}}

Kruskal 算法與考研 408

在計算機考研 408 中，Kruskal 算法是數據結構和算法部分的重要考點，主要涉及以下幾個方面：

算法原理與實現：考生需要熟練掌握 Kruskal 算法的基本原理、執行步驟和代碼實現。常考查算法的初始化過程、邊的排序方法、并查集的使用，以及如何通過貪心策略構建最小生成樹。例如，要求考生分析算法在給定圖上的執行過程，或者寫出算法的偽代碼或具體實現代碼。

時間復雜度與空間復雜度：Kruskal 算法的時間復雜度主要由邊的排序和并查集操作決定。邊排序的時間復雜度為\(O(E \log E)\)（\(E\)為邊的數量），并查集操作的時間復雜度近似為\(O(E \alpha(V))\)（\(V\)為頂點數量，\(\alpha(V)\)是一個增長極其緩慢的函數，可近似看作常數），因此整體時間復雜度為\(O(E \log E)\)。空間復雜度主要用于存儲邊集合和并查集，為\(O(E + V)\)。考研 408 中可能會考查對這些復雜度的分析和理解。

與其他最小生成樹算法的對比：Prim 算法也是求解最小生成樹的常用算法，考研 408 中可能會考查 Kruskal 算法與 Prim 算法的對比。例如，分析它們的適用場景（Kruskal 算法適用于稀疏圖，Prim 算法適用于稠密圖）、時間復雜度和空間復雜度的差異等。

算法的應用與變形：考研 408 中可能會出現基于 Kruskal 算法的變形題目，結合實際問題進行考查。例如，在最小生成樹的基礎上增加限制條件（如限制某些邊必須包含或不能包含），要求考生靈活運用 Kruskal 算法的思想進行求解。這需要考生深入理解算法本質，能夠將算法原理應用到不同的場景中。

在備考過程中，建議考生通過做大量的練習題來加深對 Kruskal 算法的理解，熟練掌握算法的各種細節。同時，對比學習 Prim 算法等相關內容，形成系統的知識體系，提高在考試中的解題能力。