淺析最小生成樹

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

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

耗費：生成樹上各邊權的總和

最小生成樹：在G的所有生成樹中，耗費最小的生成樹最小生成樹在實際中有廣泛應用。

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

Prime算法思想

牽扯到貪心策略

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

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

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

此算法核心部分

結構體的選擇

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

實現(xiàn)思路

tips:onTreet 屬性是布爾類型，為true時該結點在“樹”上

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

構造實例

按Prim算法對如圖所示的無向連通帶權圖構造一棵最小生成樹。

構造過程

點和邊結構體數(shù)組圖示如上所示，我們需要的最終效果為下圖所示：

代碼詳解

#include <iostream>
using namespace std;
struct Node {
	int ID;//結點序號
	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為邊左右連接點，v是邊的權值
	}
};
Node A[] = { {1,false}, {2,false}, {3,false}, {4,false}, {5,false} };//點結構體數(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)};//邊結構體數(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的一個連接到了在“樹”上的結點才為真
}
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;//選中的邊設置為在“樹”上
        //將邊的連接點放在“樹”上
		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;
	}
}

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

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

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

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

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

這里詳細的解析一下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的一個連接到了在“樹”上的結點才為真
}
//調(diào)用方法 ： FindOne(L[j], A)

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

調(diào)試結果

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

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

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

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

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

總結

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

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

最新評論