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

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

Kruskal 算法的基本概念

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

  • :由頂點(節點)集合和邊集合組成,邊可以有權值,用于表示頂點之間的關系和連接代價。
  • 生成樹:對于一個連通圖,它的生成樹是包含圖中所有頂點的無環連通子圖。
  • 最小生成樹:在帶權連通圖的所有生成樹中,邊的權值之和最小的生成樹稱為最小生成樹。

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

Kruskal 算法的思想

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

具體執行過程如下:

  1. 初始化:將圖中的所有邊按照權值從小到大進行排序,并初始化一個空的邊集合用于存儲最小生成樹的邊,同時將每個頂點看作一個獨立的集合(利用并查集數據結構實現)。
  1. 遍歷邊集:依次遍歷排序后的邊集合,對于每條邊,檢查其兩個端點是否屬于不同的集合(即是否會形成環)。如果屬于不同集合,則將該邊加入最小生成樹的邊集合中,并合并兩個端點所在的集合;如果屬于相同集合,則跳過該邊,因為加入后會形成環。
  1. 結束條件:當最小生成樹的邊集合中包含n - 1條邊時(n為圖中頂點的數量),停止遍歷,此時得到的邊集合構成的樹即為最小生成樹。

Kruskal 算法的解題思路

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

  1. 構建圖模型:根據題目描述,將問題抽象為帶權連通圖,確定頂點集合、邊集合以及每條邊的權值。
  1. 初始化并查集:為圖中的每個頂點創建一個獨立的集合,用于后續判斷邊加入后是否會形成環。
  1. 邊排序:將圖中的所有邊按照權值從小到大進行排序。
  1. 執行 Kruskal 算法:遍歷排序后的邊集合,按照算法規則選取邊加入最小生成樹的邊集合中,同時使用并查集維護頂點集合的連通性。
  1. 處理結果:根據題目要求,返回最小生成樹的邊集合、邊的權值之和,或者進行其他相關處理。

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 算法是數據結構和算法部分的重要考點,主要涉及以下幾個方面:

  1. 算法原理與實現:考生需要熟練掌握 Kruskal 算法的基本原理、執行步驟和代碼實現。常考查算法的初始化過程、邊的排序方法、并查集的使用,以及如何通過貪心策略構建最小生成樹。例如,要求考生分析算法在給定圖上的執行過程,或者寫出算法的偽代碼或具體實現代碼。
  1. 時間復雜度與空間復雜度:Kruskal 算法的時間復雜度主要由邊的排序和并查集操作決定。邊排序的時間復雜度為\(O(E \log E)\)(\(E\)為邊的數量),并查集操作的時間復雜度近似為\(O(E \alpha(V))\)(\(V\)為頂點數量,\(\alpha(V)\)是一個增長極其緩慢的函數,可近似看作常數),因此整體時間復雜度為\(O(E \log E)\)。空間復雜度主要用于存儲邊集合和并查集,為\(O(E + V)\)。考研 408 中可能會考查對這些復雜度的分析和理解。
  1. 與其他最小生成樹算法的對比:Prim 算法也是求解最小生成樹的常用算法,考研 408 中可能會考查 Kruskal 算法與 Prim 算法的對比。例如,分析它們的適用場景(Kruskal 算法適用于稀疏圖,Prim 算法適用于稠密圖)、時間復雜度和空間復雜度的差異等。
  1. 算法的應用與變形:考研 408 中可能會出現基于 Kruskal 算法的變形題目,結合實際問題進行考查。例如,在最小生成樹的基礎上增加限制條件(如限制某些邊必須包含或不能包含),要求考生靈活運用 Kruskal 算法的思想進行求解。這需要考生深入理解算法本質,能夠將算法原理應用到不同的場景中。

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

總結

Kruskal 算法以其簡潔高效的貪心策略,為最小生成樹問題提供了優秀的解決方案。本文從算法的基本概念、核心思想出發,詳細介紹了解題思路,并通過 LeetCode 例題和 Java 代碼實現展示了算法的實際應用,同時結合考研 408 的考點進行了深入分析。

希望本文能夠幫助讀者更深入地理解Kruskal 算法,并在實際項目中發揮其優勢。謝謝閱讀!


希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方,請隨時告訴我。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/88084.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/88084.shtml
英文地址,請注明出處:http://en.pswp.cn/web/88084.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Vue+Openlayers加載OSM、加載天地圖

文章目錄1. 介紹2. 加載底圖2.1 加載默認OSM地圖2.2 加載天地圖1. 介紹 Openlayers官網&#xff1a;https://openlayers.org/ 安裝依賴&#xff1a;npm i ol 2. 加載底圖 參考博客&#xff1a; vueopenlayers環境配置&#xff1a;https://blog.csdn.net/cuclife/article/det…

Python處理電子表格文件庫之pyexcel使用詳解

概要 pyexcel是一個功能強大的Python第三方庫,專門用于處理各種格式的電子表格文件。核心價值在于提供了統一的接口來讀取、寫入和操作Excel、CSV、ODS等多種電子表格格式,極大簡化了數據處理工作流程。與傳統的單一格式處理庫不同,pyexcel采用了插件化架構,使開發者能夠通…

【網絡安全】惡意 Python 包“psslib”仿冒 passlib,可導致 Windows 系統關閉

文章目錄惡意 Python 包“psslib”仿冒 passlib如何避免psslib的威脅惡意 Python 包“psslib”仿冒 passlib Socket 的威脅研究團隊發現了一個名為 psslib 的惡意 Python 包&#xff0c;旨在以提供密碼安全功能為幌子突然關閉 Windows 系統。 該軟件包由威脅行為者使用別名 u…

ai之對接電信ds后端服務,通過nginx代理轉發https為http,對外請求,保持到達第三方后請求頭不變

前置環境&#xff1a; 在微信小程序中嵌入H5頁面&#xff08;智能客服&#xff09;&#xff0c;需要讓h5頁面在https的域名服務器上。即通過 nginx 部署成web服務&#xff0c;還得配置域名和端口443訪問。電信的第三方deepseek服務 &#xff0c;只接收http請求&#xff0c;暫未…

第十四節:Vben Admin 最新 v5.0 (vben5) + Python Flask 快速入門 - Flask 后端 生產部署講解

Vben5 系列文章目錄 ?? 基礎篇 ? 第一節:Vben Admin 最新 v5.0 (vben5) + Python Flask 快速入門 ? 第二節:Vben Admin 最新 v5.0 (vben5) + Python Flask 快速入門 - Python Flask 后端開發詳解(附源碼) ? 第三節:Vben Admin 最新 v5.0 (vben5) + Python Flask 快速入…

Unity開發如何解決iOS閃退問題

一、iOS閃退常見原因及排查方法1. 內存問題&#xff08;最常見原因&#xff09; 癥狀表現&#xff1a; 設備發熱后閃退 加載大型場景時崩潰 控制臺出現EXC_RESOURCE RESOURCE_TYPE_MEMORY日志 解決方案&#xff1a; // 內存監控代碼 void Update() { Debug.Log($"內存使用…

【機器學習筆記 Ⅲ】5 強化學習

強化學習&#xff08;Reinforcement Learning, RL&#xff09; 強化學習是機器學習的一個分支&#xff0c;其核心思想是讓智能體&#xff08;Agent&#xff09;通過與環境&#xff08;Environment&#xff09;的交互學習最優策略&#xff08;Policy&#xff09;&#xff0c;以最…

pytorch深度學習-卷積神經網絡CNN-MNIST-gpu加速

一、為什么需要 CNN&#xff1f;從圖像識別的 “麻煩” 說起假設你想讓電腦識別一張圖片里有沒有貓。 如果用傳統神經網絡&#xff1a;一張 100100 的彩色圖片&#xff0c;有 100100330000 個像素點&#xff0c;每個像素點都是一個輸入神經元。傳統網絡需要每個輸入神經元和隱藏…

【阿里巴巴JAVA開發手冊】IDE的text file encoding設置為UTF-8; IDE中文件的換行符使用Unix格式,不要使用Windows格式。

問題&#xff1a;當使用 IDEA SSH 遠程開發時&#xff0c;SFTP 同步的 Windows 本地編輯的 config/plugin_config 文件文本內容中 “換行符”與 Unix、Linux 的文件文本內容換行符字符集不一致&#xff0c;導致 docker 容器中自定義 /opt/seatunnel/bin/install_plugin 在執行以…

自動駕駛ROS2應用技術詳解

自動駕駛ROS2應用技術詳解 目錄 自動駕駛ROS2節點工作流程自動駕駛感知融合技術詳解多傳感器數據同步技術詳解ROS2多節點協作與自動駕駛系統最小節點集 1. 自動駕駛ROS2節點工作流程 1.1 感知輸出Topic的后續處理 在自動駕駛系統中&#xff0c;感知節點輸出的各種Topic會被…

Redis底層實現原理之訂閱發布機制

文章目錄1. 通知類型2. 實現原理2.1 Pub/Sub2.1.1 基礎知識點2.1.2 頻道和訂閱者的存儲通知原理2.1.3 鍵空間通知2.1.4 客戶端消費2.1.5 缺陷2.2 Redis Stream2.2.1 基礎知識點2.2.2 基礎數據結構2.2.3 消費者組管理2.2.4 消息和消費者持久化2.2.5 消息生產和消費2.2.6 消費者拉…

【MATLAB代碼】AOA與TDOA混合定位例程,自適應基站數量,二維,可調節錨點數量。訂閱專欄后,可直接查看matlab源代碼

本文給出一個matlab代碼,用于在二維平面上,使用AOA的角度測量和TDOA的到達時間差的測量,來達到對未知點的精確定位。最后輸出定位示意圖、真實點坐標、僅AOA定位坐標與誤差、僅TDOA定位的坐標與誤差、AOA+TDOA混合定位的坐標與誤差。訂閱專欄后可直接查看源代碼,粘貼到MATL…

Node.js 所有主要版本的發布時間、穩定版本(Stable)和長期支持版本(LTS) 的整理

以下是 Node.js 所有主要版本的發布時間、穩定版本&#xff08;Stable&#xff09;和長期支持版本&#xff08;LTS&#xff09; 的整理&#xff0c;涵蓋從早期版本到當前最新版本的信息。 &#x1f4c5; Node.js 版本發布規律 每 6 個月發布一個新主版本&#xff08;偶數月&am…

【牛客刷題】小紅的v三元組

文章目錄 一、題目介紹1.1 題目描述1.2 輸入描述1.3 輸出描述1.4 示例二、解題思路2.1 核心算法設計2.2 性能優化關鍵2.3 算法流程圖三、算法實現四、算法分析4.1 時間復雜度4.2 空間復雜度4.3 正確性證明五、為什么選擇離散化+樹狀數組的解法?5.1 問題本質分析5.2 解法設計思…

c語言學習_函數遞歸

今天學習函數遞歸。函數遞歸通俗來說就是函數自己調用自己&#xff0c;遞歸的主要思考方式在于&#xff1a;把大事化小。例子&#xff1a;接受一個整型值&#xff0c;按照順序打印它的每一位。void print(unsigned int n) {if (n > 9){print(n / 10);}printf("%d"…

Bash與Zsh與Fish:在Linux中你應該使用哪個Shell

命令行 shell 是與操作系統交互的重要工具&#xff0c;使用戶能夠高效地執行命令、自動化任務和運行腳本。 雖然有各種外殼選項可供選擇&#xff0c;但Bash、Zsh和Fish作為最受歡迎的選擇脫穎而出&#xff0c;每種都提供獨特的功能&#xff0c;因此理解它們的差異對于選擇適合…

Peek-Ubuntu上Gif錄制工具-24.04LTS可裝

安裝方法&#xff08;Ubuntu24.04.2LTS測試通過&#xff09; sudo apt update sudo apt install peek純無語&#xff0c;&#x1f9df; 一個軟件&#xff0c;仨網站&#xff0c;四份重復的教程&#xff1a; 添加 PPA更新源報錯&#xff08;不支持 noble&#xff09;搜到 4 篇教…

DVWA靶場通關筆記-驗證碼繞過reCAPTCHA(High級別)

目錄 一、reCAPTCHA 二、代碼審計&#xff08;High級別&#xff09; 1、滲透準備 &#xff08;1&#xff09;配置security為High級別。 &#xff08;2&#xff09;配置RECAPTCHA參數 &#xff08;3&#xff09;再次打開靶場 2、源碼分析 &#xff08;1&#xff09;inde…

【Java安全】RMI基礎

文章目錄介紹實現服務端 Server客戶端 Client通信過程數據端與注冊中心(1099 端口)建立通訊客戶端與服務端建立 TCP 通訊客戶端序列化傳輸 調用函數的輸入參數至服務端總結介紹 RMI 全稱 Remote Method Invocation&#xff08;遠程方法調用&#xff09;&#xff0c;即在一個 J…

MySQL索引面試問題梳理

本文系統剖析MySQL索引的核心機制&#xff1a; ?索引分類全景圖?&#xff1a;詳解聚簇/非聚簇索引的邏輯差異與物理存儲特點?B樹的統治性優勢?&#xff1a;通過對比Hash/B樹揭示InnoDB的底層選擇邏輯 一、索引分類的常見困惑解析 1. 按物理存儲分類 類型 存儲內容 數量限…