ch10 課堂參考代碼

ch10 最小生成樹

生成樹:對于 n 個結點 m 條邊的無向圖 G,由全部 n 個結點和其中 n - 1 條邊構成的無向連通子圖稱為 G 的一棵生成樹。

  • 如果圖 G 原本就不連通,則不存在生成樹,只存在生成森林。

最小生成樹(Minimum Spanning Tree,MST):對于帶邊權的無向圖 G,邊的權值之和最小的生成樹稱為 G 的最小生成樹。

求解 MST 常用 Kruskal 算法或 Prim 算法,這兩種算法都基于貪心法。

  • Kruskal 算法時間復雜度 O ( m log ? m ) O(m\log m) O(mlogm) ,適用于稀疏圖。
  • Prim 算法時間復雜度 O ( n 2 ) O(n^2) O(n2) ,適用于完全圖或稠密圖。

模板

prim

算法流程:選取任意一個結點作為樹 T,然后貪心地選取離 T 最近的那個點,并把它和對應的邊加到 T 中。不斷進行這個操作,就可以得到一棵最小生成樹 T。

const int inf = 0x3f3f3f3f;
const int maxn = 5010;
int cost[maxn][maxn];
// 是否在 T 中
bool used[maxn];
// 點 i 與 T 相連的最短邊的權值
int d[maxn];
int n;/*
標記一個點 d[u] = 0
循環地執行:不在 T 中的節點與 T 相連的最短的邊,擁有該邊的節點 u最小生成樹權值加上這條邊把 u 加入 T:維護 used, d
直到 n 個點全部加入 T 中
*/
long long prim() {memset(d, 0x3f, sizeof(d));d[1] = 0;  // 希望第一步加入點 1long long res = 0;for (int i = 1; i <= n; ++i) {int u = -1;for (int v = 1; v <= n; ++v) {// 選不在樹 T 且與 T 相連的最短邊if (!used[v] && (u == -1 || d[v] < d[u])) u = v;}if (d[u] == inf) return -1;// 把點 u 加入樹 Tres += d[u];used[u] = 1;for (int v = 1; v <= n; ++v) {if (!used[v]) d[v] = min(d[v], cost[u][v]);}}return res;
}

kruskal

算法流程:每次都從剩余的邊中選出一條邊權最小的,并且這條邊的兩個端點 u 和 v 屬于兩個不同的連通分量(即 u 和 v 不連通),則加入該邊,連接兩個連通分量。

const int maxn = 100010, maxm = 100010;
struct Edge {int u, v, w;bool operator<(const Edge &n) const { return w < n.w; }
}E[maxm];
int fa[maxn], n, m;
void init() {for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void merge(int x, int y) {int rx = find(x), ry = find(y);fa[ry] = rx;
}
long long kru() {sort(E, E + m); // 邊權從小到大排序long long res = 0;int cnt = n; // 記錄當前連通分量的個數for (int i = 0; i < m; ++i) {Edge e = E[i];if (find(e.u) != find(e.v)) {merge(e.u, e.v);--cnt, res += e.w;}}if (cnt > 1) return -1; // 不連通return res;
}
int main() {cin >> n >> m;for (int i = 0; i < m; ++i) {cin >> E[i].u >> E[i].v >> E[i].w;}init();cout << kru() << endl;return 0;
}

注意并查集只是維護結點的連通情況,不代表最終的 MST。如果需要將 MST 儲存起來方便后面遍歷這棵 MST,可以用 vector 數組(鄰接表)將加入的邊 e[i] 儲存。

// 有邊權的情況,需要儲存出邊的終點v和邊權w
struct Edge2{int v, w;
};
vector<Edge2> G[N]; // G[u]儲存結點u的所有出邊信息(終點v和邊權w)// 選中e[i]這條邊加入時,執行
G[e[i].u].push_back({e[i].v, e[i].w});
G[e[i].v].push_back({e[i].u, e[i].w});

瓶頸生成樹

  • 指最大的邊權值最小的生成樹。

  • 與最小生成樹的區別

    • 最小生成樹目標是希望所有邊權加起來最小。
    • 瓶頸生成樹目標是希望邊權最大的那條邊權值盡量小。如果把邊權理解為邊的長度,就是希望最長的那條邊盡量短。
  • 性質: 最小生成樹一定是瓶頸生成樹,而瓶頸生成樹不一定是最小生成樹。

    反證法證明:

    設最小生成樹中的最大邊權為 w,如果最小生成樹不是瓶頸生成樹的話,則瓶頸生成樹的所有邊權都小于 w。

    只需刪去原最小生成樹中的最長邊,用瓶頸生成樹中的一條邊來連接刪去邊后形成的兩棵樹,得到的新生成樹一定比原最小生成樹的權值和還要小,這樣就產生了矛盾。

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

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

相關文章

費曼技巧及提高計劃

費曼技巧及提高計劃 一、什么是費曼技巧&#xff1f; 費曼技巧&#xff08;Feynman Technique&#xff09;由諾貝爾物理學獎得主理查德費曼提出&#xff0c;是一種通過“以教代學”來徹底理解復雜概念的學習方法。其核心邏輯是&#xff1a; “如果你不能簡單解釋一件事&#x…

LongRefiner:解決長文檔檢索增強生成的新思路

大語言模型與RAG的應用越來越廣泛&#xff0c;但在處理長文檔時仍面臨不少挑戰。今天我們來聊聊一個解決這類問題的新方法——LongRefiner。 背景問題&#xff1a;長文檔處理的兩大難題 使用檢索增強型生成&#xff08;RAG&#xff09;系統處理長文檔時&#xff0c;主要有兩個…

5月16日復盤-目標檢測開端

5月16日復盤 一、圖像處理之目標檢測 1. 目標檢測認知 ? Object Detection&#xff0c;是指在給定的圖像或視頻中檢測出目標物體在圖像中的位置和大小,并進行分類或識別等相關任務。 ? 目標檢測將目標的分割和識別合二為一。 ? What、Where 2. 使用場景 目標檢測用于…

MySQL基礎面試通關秘籍(附高頻考點解析)

文章目錄 一、事務篇&#xff08;必考重點&#xff09;1.1 事務四大特性&#xff08;ACID&#xff09;1.2 事務實戰技巧 二、索引優化大法2.1 索引類型全家福2.2 EXPLAIN命令實戰 三、存儲引擎選型指南3.1 InnoDB vs MyISAM 終極對決 四、SQL優化實戰手冊4.1 慢查詢七宗罪4.2 分…

Word圖片格式調整與轉換工具

軟件介紹 本文介紹的這款工具主要用于輔助Word文檔處理。 圖片排版功能 經常和Word打交道的人或許都有這樣的困擾&#xff1a;插入的圖片大小各異&#xff0c;排列也參差不齊。若不加以調整&#xff0c;遇到要求嚴格的領導&#xff0c;可能會讓人頗為頭疼。 而這款工具能夠統…

工業巡檢機器人 —— 機器人市場的新興增長引擎

摘要 在機器人產業蓬勃發展的當下&#xff0c;不同類型機器人的市場表現差異顯著。工業機械臂雖市場規模龐大&#xff0c;但已趨近飽和&#xff0c;陷入紅海競爭&#xff1b;人形機器人因技術瓶頸仍多停留于實驗室階段&#xff0c;距離大規模商用尚有較長距離。與之形成鮮明對比…

Oracle where條件執行先后順序

Oracle where條件執行先后順序 在Oracle數據庫中&#xff0c;WHERE子句的條件執行順序通常是根據你在WHERE子句中指定的條件來決定的&#xff0c;而不是按照某種固定的順序執行的。當你編寫一個WHERE子句時&#xff0c;你可以包含多個條件&#xff0c;這些條件可以是邏輯運算符…

在Linux中使用 times函數 和 close函數 兩種方式 打印進程時間。

times函數用于獲取當前進程時間,其函數原型如下所示: #include <sys/times.h> clock_t times(struct tms *buf); //使用該函數需要包含頭文件<sys/times.h>。 函數參數和返回值含義如下: buf:times()會將當前進程時間信息存在一個 struct tms 結構體數據…

Python文字轉語音TTS庫示例(edge-tts)

1. 安裝 pip install edge-tts2. 命令行使用 # 生成語音文件 # -f:要轉換語音的文本文件,例如一個txt文件 # --text:指明要保存的mp3的文本 # --write-media:指明保存的mp3文件路徑 # --write-subtitles:指定輸出字幕/歌詞路徑 # --rate:調整語速,+50%加快了50% # --v…

Elasticsearch性能調優全攻略:從日志分析到集群優化

#作者&#xff1a;獵人 文章目錄 前言搜索慢查詢日志索引慢寫入日志性能調優之基本優化建議性能調優之索引寫入性能優化提升es集群寫入性能方法&#xff1a;性能調優之集群讀性能優化性能調優之搜索性能優化性能調優之GC優化性能調優之路由優化性能調優之分片優化 前言 es里面…

MongoDB從入門到實戰之Windows快速安裝MongoDB

前言 本章節的主要內容是在 Windows 系統下快速安裝 MongoDB 并使用 Navicat 工具快速連接。 MongoDB從入門到實戰之MongoDB簡介 MongoDB從入門到實戰之MongoDB快速入門 MongoDB從入門到實戰之Docker快速安裝MongoDB 下載 MongoDB 安裝包 打開 MongoDB 官網下載頁面&…

Serverless,云計算3.0階段

Hi~各位讀者朋友們&#xff0c;感謝您閱讀本文&#xff0c;我是笠泱&#xff0c;本期簡單分享下Serverless。Serverless是一種云計算服務模式&#xff0c;為業務代碼提供運行環境及調度服務。開發者只需專注于編寫業務邏輯代碼&#xff0c;無需管理底層基礎設施&#xff08;如服…

eSearch:一款集截圖、OCR與錄屏于一體的多功能軟件

eSearch&#xff1a;一款集截圖、OCR與錄屏于一體的多功能軟件 軟件介紹 eSearch是一款專為Windows 10和11用戶設計的多功能軟件&#xff0c;集截圖、OCR文字識別、錄屏等功能于一體&#xff0c;且完全免費。其便捷版無需安裝&#xff0c;運行后最小化至托盤圖標&#xff0c;…

React學習———useContext和useReducer

useContext useContext是React的一個Hook&#xff0c;用于在函數組件中訪問上下文&#xff08;context&#xff09;的值。它可以幫助我們在組件樹中共享狀態&#xff0c;而不需要通過props一層層傳遞 特點 用于跨組件共享狀態需要配合React.createContext和Context.Provider…

安卓刷機模式詳解:Fastboot、Fastbootd、9008與MTK深刷

安卓刷機模式詳解&#xff1a;Fastboot、Fastbootd、9008與MTK深刷 一、刷機模式對比 1. Fastboot模式 簡介&#xff1a;傳統安卓底層刷機模式&#xff0c;通過USB連接電腦操作優點&#xff1a;支持大多數安卓設備&#xff0c;操作相對簡單缺點&#xff1a;需要設備進入特定…

HDFS的概述

HDFS組成構架&#xff1a; 注&#xff1a; NameNode&#xff08;nn&#xff09;&#xff1a;就是 Master&#xff0c;它是一個主管、管理者。 (1) 管理 HDFS 的名稱空間&#xff1b; (2) 配置副本策略。記錄某些文件應該保持幾個副本&#xff1b; (3) 管理數據塊&#xff0…

配置Spark環境

1.上傳spark安裝包到某一臺機器&#xff08;自己在finaShell上的機器&#xff09;。 2.解壓。 把第一步上傳的安裝包解壓到/opt/module下&#xff08;也可以自己決定解壓到哪里&#xff09;。對應的命令是&#xff1a;tar -zxvf 安裝包 -C /opt/module 3.重命名。進入/opt/mo…

Java筆記五

1 Math類 1.1 概述 tips&#xff1a;了解內容 查看API文檔&#xff0c;我們可以看到API文檔中關于Math類的定義如下&#xff1a; Math類所在包為java.lang包&#xff0c;因此在使用的時候不需要進行導包。并且Math類被final修飾了&#xff0c;因此該類是不能被繼承的。 Math…

QT 插槽實現

方法 1&#xff1a;使用 default property 實現標簽插入 通過定義 default property&#xff0c;可以使組件直接嵌套在目標組件中&#xff0c;類似于插槽機制。 CustomSlotExample.qml import QtQuick 2.15 import QtQuick.Controls 2.15// 定義一個支持插槽的自定義組件 Re…

spark在shell中運行RDD程序

在hdfs中/wcinput中創建一個文件&#xff1a;word2.txt在里面寫幾個單詞 啟動hdfs集群 [roothadoop100 ~]# myhadoop start [roothadoop100 ~]# cd /opt/module/spark-yarn/bin [roothadoop100 ~]# ./spark-shell 寫個11測試一下 按住ctrlD退出 進入環境&#xff1a;spark-shel…