淺析最小生成樹

設(shè)G=(V,E)是無向連通帶權(quán)圖。E中每條邊(v,w)的權(quán)為c[v][w]。

生成樹：如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。

耗費(fèi)：生成樹上各邊權(quán)的總和

最小生成樹：在G的所有生成樹中，耗費(fèi)最小的生成樹最小生成樹在實(shí)際中有廣泛應(yīng)用。

例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。

Prime算法思想

牽扯到貪心策略

設(shè)G=(V，E)是無向連通帶權(quán)圖，V={1,2,…,n}；

設(shè)最小生成樹T=(U，TE)，算法結(jié)束時U=V，TE E。

首先，令U={u0}，TE={}。然后，只要U是V的真子集，就做如下貪心選擇：選取滿足條件i U，j V-U，且邊(i，j)是連接U和V-U的所有邊中的最短邊，即該邊的權(quán)值最小。然后，將頂點(diǎn)j加入集合U，邊(i，j)加入集合TE。繼續(xù)上面的貪心選擇一直進(jìn)行到U=V為止，此時，選取到的所有邊恰好構(gòu)成G的一棵最小生成樹T。需要注意的是，貪心選擇這一步驟在算法中應(yīng)執(zhí)行多次，每執(zhí)行一次，集合TE和U都將發(fā)生變化，即分別增加一條邊和一個頂點(diǎn)。

此算法核心部分

結(jié)構(gòu)體的選擇

選擇一個合適的數(shù)據(jù)結(jié)構(gòu)可以讓程序的實(shí)現(xiàn)效率大大提高，難度大大降低；既然是生成最小生成樹，不妨選擇點(diǎn)和邊結(jié)構(gòu)體；因此創(chuàng)建兩個結(jié)構(gòu)體，第一個點(diǎn)node結(jié)構(gòu)體包含所有的結(jié)點(diǎn)；第二個邊結(jié)構(gòu)體包含所有待選擇的邊、連接點(diǎn)及權(quán)值。

實(shí)現(xiàn)思路

tips:onTreet 屬性是布爾類型，為true時該結(jié)點(diǎn)在“樹”上

首先對應(yīng)第一個結(jié)點(diǎn)找我們需要的邊，我們需要什么樣的邊呢，那就是在邊的兩個連接點(diǎn)中，有且僅有一個連結(jié)點(diǎn)等于結(jié)點(diǎn)的名稱（這個可以在點(diǎn)結(jié)構(gòu)體中加ID屬性），并且這個結(jié)點(diǎn)必須是根結(jié)點(diǎn)（即onTree為true），滿足這個條件，就把另一個連接點(diǎn)的onTree屬性設(shè)為true；最后為了把滿足條件的邊連起來，我就個邊結(jié)構(gòu)體也加一個onTree屬性，輸出所有onTree 為true的邊結(jié)構(gòu)體即可。

構(gòu)造實(shí)例

按Prim算法對如圖所示的無向連通帶權(quán)圖構(gòu)造一棵最小生成樹。

構(gòu)造過程

點(diǎn)和邊結(jié)構(gòu)體數(shù)組圖示如上所示，我們需要的最終效果為下圖所示：

代碼詳解

#include <iostream>
using namespace std;
struct Node {
	int ID;//結(jié)點(diǎn)序號
	bool OnTree;//是否屬于最小生成樹
};
struct LS {
	int N1, N2; int V; bool OnTree;//OnTree用于判斷此邊是否在“樹”上
	LS(int n1, int n2, int v) {
		N1 = n1; N2 = n2; V = v; OnTree = false;//N1,N2為邊左右連接點(diǎn)，v是邊的權(quán)值
	}
};
Node A[] = { {1,false}, {2,false}, {3,false}, {4,false}, {5,false} };//點(diǎn)結(jié)構(gòu)體數(shù)組
LS L[8] = { LS(1,2,1),LS(1,3,4) ,LS(2,3,2),
LS(2,5,2),LS(4,5,4),LS(3,4,6),LS(3,5,3),LS(1,4,8)};//邊結(jié)構(gòu)體數(shù)組
bool FindOne(LS L ,Node A[]) {//布爾類型
	int m = 0;
	for (int i = 0; i < 5; i++)
		if (L.N1 == A[i].ID && A[i].OnTree) m++;
	for (int i = 0; i < 5; i++)
		if (L.N2 == A[i].ID && A[i].OnTree) m++;
	return m ==1;//只有N1和N2的一個連接到了在“樹”上的結(jié)點(diǎn)才為真
}
int main()
{
	A[0].OnTree = true;
	for (int i = 0; i < 5; i++) {
		int p = 0;
		for (int j = 0; j < 8; j++) {
			if (FindOne(L[j], A)) {
				p = j; break;
			}
		}
		for (int i = 0; i < 8; i++) {
			if (FindOne(L[i], A))
				if (L[i].V < L[p].V) p = i;
		}
		L[p].OnTree = true;//選中的邊設(shè)置為在“樹”上
        //將邊的連接點(diǎn)放在“樹”上
		for (int i = 0; i < 5; i++) {
			if (L[p].N1 == A[i].ID) A[i].OnTree = true;
			if (L[p].N2 == A[i].ID) A[i].OnTree = true;
		}
	}
    //輸出最小生成樹所有邊
	for (int i = 0; i < 8; i++) {
		cout << L[i].OnTree;
	}
}

結(jié)構(gòu)體node 和結(jié)構(gòu)體LS在上文已經(jīng)較為詳細(xì)的介紹了，而且還給出了node數(shù)組A和LS數(shù)組L的圖示，不過要注意默認(rèn)的邊都是不在“樹”上的；

主函數(shù)一共有四個for循環(huán)，最后一個for循環(huán)僅僅就是為了輸出在最小生成樹上的邊，和prime的核心沒有關(guān)系；

第一個for循環(huán)也就是最大的for循環(huán)，用來確定生成最小生成樹的找邊次數(shù)；

第二個for循環(huán)是為了找出我們所需要的邊，如果存在一條邊，有且僅有一個連結(jié)點(diǎn)等于結(jié)點(diǎn)的名稱并且該連接點(diǎn)是在“樹”上的，那么返回改邊下標(biāo)并用變量p記錄；

第三個for循環(huán)是為了篩選出所有滿足此條件邊中權(quán)值最小的邊，并把該邊的小標(biāo)用p記錄；將最終選出的邊放在“樹”上，利用第三個for循環(huán)把與該邊連接的點(diǎn)都放在“樹”上，然后循環(huán)執(zhí)行上述過程，直到?jīng)]有滿足條件的邊，大循環(huán)結(jié)束，輸出最小生成樹。

這里詳細(xì)的解析一下FindOne函數(shù)：

bool FindOne(LS L ,Node A[]) {//布爾類型
	int m = 0;
	for (int i = 0; i < 5; i++)
		if (L.N1 == A[i].ID && A[i].OnTree) m++;
	for (int i = 0; i < 5; i++)
		if (L.N2 == A[i].ID && A[i].OnTree) m++;
	return m ==1;//只有N1和N2的一個連接到了在“樹”上的結(jié)點(diǎn)才為真
}
//調(diào)用方法 ： FindOne(L[j], A)

調(diào)用該函數(shù)的時候，實(shí)參第一個是邊結(jié)構(gòu)體類型的L數(shù)組內(nèi)的任意一個元素，第二個則是點(diǎn)結(jié)構(gòu)體類型的A數(shù)組的首地址，所以形參第一個需要傳入LS類型的變量L，第二個則是整個Node類型的數(shù)組，這樣傳參才相互對應(yīng)，如果對于函數(shù)傳參有疑問，可以參考這篇函數(shù)的傳參方式然后定義變量m初始值為0，第一個for循環(huán)是和該邊的第一個連接點(diǎn)作比較，滿足條件則m+1；第二個for循環(huán)是和該邊第二個連接點(diǎn)作比較，滿足條件也會加m也會加1；但是我只要比較結(jié)果為一的m，這樣就能篩選出滿足條件的邊。

調(diào)試結(jié)果

第一次循環(huán)，滿足條件的最小權(quán)值邊下標(biāo)應(yīng)為0（p為0），初始值第一個結(jié)點(diǎn)默認(rèn)放在“樹”上；由于p為0，所以第一個邊的兩個連接點(diǎn)都會被放在“樹”上；（ID1和2都是true）

第二次循環(huán)，p為2，數(shù)組中第三條邊左右連接點(diǎn)對應(yīng)的ID2和3都會變?yōu)閠rue；

??????第三次循環(huán)，p為3，同理，ID5會變成true；

接下來重復(fù)上面的過程，直到?jīng)]有滿足條件的邊，循環(huán)結(jié)束；

最后就是輸出所有在“樹”上的邊了，數(shù)組中為1的邊就是被選中的邊，這樣清晰的得到了最終的最小生成樹了。

總結(jié)

Prime算法屬于貪心算法的一種，盡情的找到權(quán)值最小的邊并連接到一起，最小生成樹的算法分享與實(shí)現(xiàn)圓滿完成了，希望對大家有實(shí)質(zhì)性的幫助

到此這篇關(guān)于C語言詳細(xì)分析貪心策略中最小生成樹的Prime算法設(shè)計(jì)與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語言Prime算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論