C語言詳細分析貪心策略中最小生成樹的Prime算法設計與實現

Posted on by

淺析最小生成樹

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

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

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

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

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

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。繼續上面的貪心選擇一直進行到U=V為止，此時，選取到的所有邊恰好構成G的一棵最小生成樹T。需要註意的是，貪心選擇這一步驟在算法中應執行多次，每執行一次，集合TE和U都將發生變化，即分別增加一條邊和一個頂點。

此算法核心部分

結構體的選擇

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

實現思路

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

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

構造實例

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

構造過程

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

代碼詳解

#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} };//點結構體數組
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)};//邊結構體數組
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在上文已經較為詳細的介紹瞭，而且還給出瞭node數組A和LS數組L的圖示，不過要註意默認的邊都是不在“樹”上的；

主函數一共有四個for循環，最後一個for循環僅僅就是為瞭輸出在最小生成樹上的邊，和prime的核心沒有關系；

第一個for循環也就是最大的for循環，用來確定生成最小生成樹的找邊次數；

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

第三個for循環是為瞭篩選出所有滿足此條件邊中權值最小的邊，並把該邊的小標用p記錄；將最終選出的邊放在“樹”上，利用第三個for循環把與該邊連接的點都放在“樹”上，然後循環執行上述過程，直到沒有滿足條件的邊，大循環結束，輸出最小生成樹。

這裡詳細的解析一下FindOne函數：

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的一個連接到瞭在“樹”上的結點才為真
}
//調用方法 ： FindOne(L[j], A)

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

調試結果

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

第二次循環，p為2，數組中第三條邊左右連接點對應的ID2和3都會變為true；

​​​​​​第三次循環，p為3，同理，ID5會變成true；

接下來重復上面的過程，直到沒有滿足條件的邊，循環結束；

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

總結

Prime算法屬於貪心算法的一種，盡情的找到權值最小的邊並連接到一起，最小生成樹的算法分享與實現圓滿完成瞭，希望對大傢有實質性的幫助

到此這篇關於C語言詳細分析貪心策略中最小生成樹的Prime算法設計與實現的文章就介紹到這瞭,更多相關C語言Prime算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：