最小生成樹(shù)：

這個(gè)定義有兩個(gè)約束：最小和樹(shù)

對(duì)于樹(shù)，從而引出以下三個(gè)最小生成樹(shù)的特點(diǎn)

在圖中無(wú)環(huán)

連接所有圖中的點(diǎn)

N個(gè)頂點(diǎn)，有N-1條邊

最小：指的是生成這棵樹(shù)的邊的權(quán)值之和最小

最小生成樹(shù)的求取有兩種經(jīng)典的算法，分別是Prim(普里姆) 算法和Kruskal(克魯斯卡爾)算法

這兩種算法的算法思想都是基于貪心算法的，也就是選擇權(quán)值最小的邊，但是這兩種算法的實(shí)現(xiàn)方法不同

Prim(普里姆)算法：從頂點(diǎn)出發(fā)，優(yōu)先選擇與連接兩個(gè)頂點(diǎn)集合中的權(quán)值最小的邊

Kruskal(克魯斯卡爾)算法：直接選擇權(quán)值最小的邊

Prim(普里姆)算法

prim算法的核心是實(shí)時(shí)更新三個(gè)列表信息構(gòu)成的

第一個(gè)列表selected，是判斷是否已選頂點(diǎn)，若為true，表示頂點(diǎn)已選，若為false，表示頂點(diǎn)未選，初始為false；

第二個(gè)列表minDist，表示兩個(gè)點(diǎn)之間的距離，初始為∞（無(wú)窮大）；

第三個(gè)列表parent，存放它的雙親結(jié)點(diǎn)，初始為-1

整個(gè)生成過(guò)程是，首先（Update）更新列表信息，從列表下標(biāo)由小到大更新minDist列表

然后（Scan）掃描整個(gè)列表，更新parent列表

最后（Add）將選擇的點(diǎn)添加到已選頂點(diǎn)中，也就是更新selected列表

圖示過(guò)程

如下圖

第一個(gè)列表selected，是判斷是否已選頂點(diǎn)，若為T，表示頂點(diǎn)已選，若為F，表示頂點(diǎn)未選，初始為F；

第二個(gè)列表minDist，表示兩個(gè)點(diǎn)之間的距離，初始為inf（無(wú)窮大）；

第三個(gè)列表parent，存放它的雙親結(jié)點(diǎn)，初始為-1

與V1相連接的點(diǎn)分別是V2，V3，V4，在列表中minDist和列表parent中更新數(shù)據(jù)，找到minDist最小且selected列表為F的結(jié)點(diǎn)，就是連接結(jié)點(diǎn)，即下圖中為V3

與V1，V3相連接的點(diǎn)分別是V2，V4，V5，V6，在列表中minDist和列表parent中更新數(shù)據(jù)，找到minDist最小且selected列表為F的結(jié)點(diǎn)，就是連接結(jié)點(diǎn)，即下圖中為V6

與V1，V3，V6相連接的點(diǎn)分別是V2，V4，V5，在列表中minDist和列表parent中更新數(shù)據(jù)，找到minDist最小且selected列表為F的結(jié)點(diǎn)，就是連接結(jié)點(diǎn)，即下圖中為V4

與V1，V3，V6，V4相連接的點(diǎn)分別是V2，V5，在列表中minDist和列表parent中更新數(shù)據(jù)，找到minDist最小且selected列表為F的結(jié)點(diǎn)，就是連接結(jié)點(diǎn)，即下圖中為V2

與V1，V3，V6，V4，V2相連接的點(diǎn)分別是V5，在列表中minDist和列表parent中更新數(shù)據(jù)，找到minDist最小且selected列表為F的結(jié)點(diǎn)，就是連接結(jié)點(diǎn)，即下圖中為V5，是selected列表中的值都為T，生成最小生成樹(shù)完畢

Prim算法的時(shí)間復(fù)雜度 $O(|V{|}^2)$，不依賴于 $|E|$，因此它適用于求解邊稠密的圖的最小生成樹(shù)。

代碼提示

void Prim(MGraph g, int v) {//普利姆算法（參數(shù)：鄰接矩陣，起點(diǎn)（即第一個(gè)生成的點(diǎn)，可隨便取））int lowcost[MAXV], closest[MAXV], i, min, j, k;//賦初值，即將closest數(shù)組都賦為第一個(gè)節(jié)點(diǎn)v，lowcost數(shù)組賦為第一個(gè)節(jié)點(diǎn)v到各節(jié)點(diǎn)的權(quán)重for (i = 0; i < g.n; i++) {closest[i] = v;lowcost[i] = g.edges[v][i];}//接下來(lái)找剩下的n-1個(gè)節(jié)點(diǎn)（g.n是圖的節(jié)點(diǎn)個(gè)數(shù)）for (i = 1; i < g.n; i++) {min = INF;//遍歷所有節(jié)點(diǎn)for (j = 0; j < g.n; j++) {//若該節(jié)點(diǎn)還未被選且權(quán)值小于之前遍歷所得到的最小值if (lowcost[j] != 0 && lowcost[j] < min) { //更新min的值min = lowcost[j];//記錄當(dāng)前最小權(quán)重的節(jié)點(diǎn)的編號(hào)k = j;}}//表明k節(jié)點(diǎn)已被選了(作標(biāo)記)lowcost[k] = 0;//遍歷所有節(jié)點(diǎn)for (j = 0; j < g.n; j++) {if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) {//更新lowcost數(shù)組，closest數(shù)組//更新權(quán)重，使其當(dāng)前最小lowcost[j] = g.edges[k][j];//進(jìn)入到該if語(yǔ)句里，說(shuō)明剛選的節(jié)點(diǎn)k與當(dāng)前節(jié)點(diǎn)j有更小的權(quán)重，則closest[j]的被連接節(jié)點(diǎn)需作修改為kclosest[j] = k;}}} }

Kruskal(克魯斯卡爾)算法

把圖中所有的邊和權(quán)重放入一個(gè)列表，并按權(quán)值從小到大排序

從列表中按次序每次選擇一條邊放入圖中（此時(shí)邏輯上圖中只有頂點(diǎn)沒(méi)有邊）

在放入圖中需要做判斷，圖中是否形成環(huán)

若沒(méi)有環(huán)，則這條邊成為最小生成樹(shù)的一條邊

相反，如果加上這條邊后形成了環(huán)，那么這邊就被丟棄，繼續(xù)將下一條邊放入圖中

重復(fù)步驟2到步驟5

直到選擇了n-1條邊，算法完成

圖示過(guò)程

存在一張圖，它有6個(gè)點(diǎn)和10條邊，如圖a所示，最后完成Kruskal算法后，會(huì)有5條邊被選定（即挑選完符合條件的5條邊）。

圖a各邊權(quán)值如下，現(xiàn)在將邊和權(quán)重放入一個(gè)列表，并按權(quán)值從小到大排序。

從列表中按次序選擇v1-v3放入圖中，該邊權(quán)重為1，此時(shí)圖中不存在環(huán)，所以V1-V3被選定，且此時(shí)邊數(shù)為1，如圖b

從列表中按次序選擇v4-v6放入圖中，該邊權(quán)重為2，此時(shí)圖中不存在環(huán)，所以V4-V6被選定，且此時(shí)邊數(shù)為2，如圖c

從列表中按次序選擇v2-v5放入圖中，該邊權(quán)重為3，此時(shí)圖中不存在環(huán)，所以v2-v5被選定，且此時(shí)邊數(shù)為3，如圖d

從列表中按次序選擇v3-v6放入圖中，該邊權(quán)重為4，此時(shí)圖中不存在環(huán)，所以v3-v6被選定，且此時(shí)邊數(shù)為4，如圖e

從列表中按次序選擇v1-v4放入圖中，該邊權(quán)重為5，但此時(shí)圖中存在環(huán)，所以v1-v4不能被選定，且此時(shí)邊數(shù)仍為4，如圖f

從列表中按次序選擇v3-v4放入圖中，該邊權(quán)重為5，但此時(shí)圖中存在環(huán)，所以v3-v4不能被選定，且此時(shí)邊數(shù)仍為4，如圖g

從列表中按次序選擇v2-v3放入圖中，該邊權(quán)重為5，此時(shí)圖中不存在環(huán)，所以v2-v3被選定，如圖h，且此時(shí)邊數(shù)為5，最小生成樹(shù)生成完畢

Prim算法的時(shí)間復(fù)雜度 $O(|E|log|E|)$，因此它適用于求解邊稀疏（頂點(diǎn)較多）的圖的最小生成樹(shù)。

代碼提示

/** @Prama:傳進(jìn)來(lái)一個(gè)edge和weight列表mapnode，* @Prama:一個(gè)結(jié)點(diǎn)數(shù)v* @return:nums<map<pair<int,int>,int> >，返回一棵最小生成樹(shù)*/ stack<map<pair<int,int>,int> > kruskal(nums<map<pair<int,int>,int> > mapnode, int v){// 按weight從小到大排列,也就是map<pair<int,int>,int>中的對(duì)應(yīng)值sort_weight(mapnode);// 最小生成樹(shù)的邊棧stack<map<pair<int,int>,int> > ans; int edge=0;// 邊 = 頂點(diǎn)數(shù) - 1;while(edge<v){ans.push_back(nums[i]);edge++;// 有環(huán)，將插入的邊去掉，同時(shí)掃描下一條邊if (isLoop(ans)) {ans.pop();edge--;}i++;} }

總結(jié)

以上是生活随笔為你收集整理的【数据结构-图】2.多图详解最小生成树（多图详解+实现代码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。