這篇文章主要講解了C++使用Kruskal和Prim算法實(shí)現(xiàn)最小生成樹(shù)的方法，內(nèi)容清晰明了，對(duì)此有興趣的小伙伴可以學(xué)習(xí)一下，相信大家閱讀完之后會(huì)有幫助。

創(chuàng)新互聯(lián)：2013年開(kāi)創(chuàng)至今為各行業(yè)開(kāi)拓出企業(yè)自己的“網(wǎng)站建設(shè)”服務(wù)，為千余家公司企業(yè)提供了專業(yè)的成都網(wǎng)站制作、成都做網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)和網(wǎng)站推廣服務(wù)， 按需規(guī)劃網(wǎng)站由設(shè)計(jì)師親自精心設(shè)計(jì)，設(shè)計(jì)的效果完全按照客戶的要求，并適當(dāng)?shù)奶岢龊侠淼慕ㄗh，擁有的視覺(jué)效果，策劃師分析客戶的同行競(jìng)爭(zhēng)對(duì)手，根據(jù)客戶的實(shí)際情況給出合理的網(wǎng)站構(gòu)架，制作客戶同行業(yè)具有領(lǐng)先地位的。

很久以前就學(xué)過(guò)最小生成樹(shù)之Kruskal和Prim算法，這兩個(gè)算法很容易理解，但實(shí)現(xiàn)起來(lái)并不那么容易。最近學(xué)習(xí)了并查集算法，得知并查集可以用于實(shí)現(xiàn)上述兩個(gè)算法后，我自己動(dòng)手實(shí)現(xiàn)了最小生成樹(shù)算法。

宏觀上講，Kruskal算法就是一個(gè)合并的過(guò)程，而Prim算法是一個(gè)吞并的過(guò)程，另外在Prim算法中還用到了一種數(shù)據(jù)結(jié)構(gòu)——優(yōu)先級(jí)隊(duì)列，用于動(dòng)態(tài)排序。由于這兩個(gè)算法很容易理解，在此不再贅述。接下來(lái)給出我的源代碼。

輸入

第一行包含兩個(gè)整數(shù)n和m，n表示圖中結(jié)點(diǎn)個(gè)數(shù)，m表示圖中邊的條數(shù)；接下來(lái)m行，每一行包含三個(gè)整數(shù)u,v,w，表示途中存在一條邊(u,v)，并且其權(quán)重為w；為了便于調(diào)試，我的程序是從文件中輸入數(shù)據(jù)的；

輸出

輸出程序選擇的最小生成樹(shù)的權(quán)值之和以及每一條邊信息；

Kruskal算法：

#include 
#include 
#include 
#include 
using namespace std;
 
struct Edge
{
 int u; //邊連接的一個(gè)頂點(diǎn)編號(hào)
 int v; //邊連接另一個(gè)頂點(diǎn)編號(hào)
 int w; //邊的權(quán)值
 friend bool operator<(const Edge& E1, const Edge& E2)
 {
 return E1.w < E2.w;
 }
};
//創(chuàng)建并查集
void MakeSet(vector& uset, int n)
{
 uset.assign(n, 0);
 for (int i = 0; i < n; i++)
 uset[i] = i;
}
//查找當(dāng)前元素所在集合的代表元
int FindSet(vector& uset, int u)
{
 int i = u;
 while (uset[i] != i) i = uset[i];
 return i;
}
void Kruskal(const vector& edges, int n)
{
 vector uset;
 vector SpanTree;
 int Cost = 0, e1, e2;
 MakeSet(uset, n);
 for (int i = 0; i < edges.size(); i++) //按權(quán)值從小到大的順序取邊
 {
 e1 = FindSet(uset, edges[i].u);
 e2 = FindSet(uset, edges[i].v);
 if (e1 != e2) //若當(dāng)前邊連接的兩個(gè)結(jié)點(diǎn)在不同集合中，選取該邊并合并這兩個(gè)集合
 {
 SpanTree.push_back(edges[i]);
 Cost += edges[i].w;
 uset[e1] = e2; //合并當(dāng)前邊連接的兩個(gè)頂點(diǎn)所在集合
 }
 }
 cout << "Result:\n";
 cout << "Cost: " << Cost << endl;
 cout << "Edges:\n";
 for (int j = 0; j < SpanTree.size(); j++)
 cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl;
 cout << endl;
}
int main()
{
 ifstream in("data.txt");
 
 int n, m;
 in >> n >> m;
 vector edges;
 edges.assign(m, Edge());
 for (int i = 0; i < m; i++)
 in >> edges[i].u >> edges[i].v >> edges[i].w;
 sort(edges.begin(), edges.end()); //排序之后，可以以邊權(quán)值從小到大的順序選取邊
 Kruskal(edges, n);
 
 in.close();
 
 system("pause");
 return 0;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞標(biāo)題：C++使用Kruskal和Prim算法實(shí)現(xiàn)最小生成樹(shù)的方法-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://weahome.cn/article/djjech.html