c語言如何實(shí)現(xiàn)最小生成樹？相信很多新手小白還沒學(xué)會(huì)這個(gè)技能，通過這篇文章的總結(jié)，希望你能學(xué)會(huì)這個(gè)技能。以下資料是實(shí)現(xiàn)的步驟。
成都創(chuàng)新互聯(lián)于2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元貢覺做網(wǎng)站,已為上家服務(wù),為貢覺各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575
1.最小生成樹介紹
什么是最小生成樹？
最小生成樹（Minimum spanning tree，MST）是在一個(gè)給定的無向圖G(V,E)中求一棵樹T，使得這棵樹擁有圖G中的所有頂點(diǎn)，且所有邊都是來自圖G中的邊，并且滿足整棵樹的邊權(quán)值和最小。
2.prim算法
和Dijkstra算法很像！！請看如下Gif圖，prim算法的核心思想是對圖G(V,E)設(shè)置集合S，存放已被訪問的頂點(diǎn)，然后每次從集合V-S中選擇與集合S的最短距離最小的一個(gè)頂點(diǎn)（記為u），訪問并加入集合S。之后，令頂點(diǎn)u為中間點(diǎn)，優(yōu)化所有從u能到達(dá)的頂點(diǎn)v與集合s之間的最短距離。這樣的操作執(zhí)行n次，直到集合s中包含所有頂點(diǎn)。
不同的是，Dijkstra算法中的dist是從源點(diǎn)s到頂點(diǎn)w的最短路徑；而prim算法中的dist是從集合S到頂點(diǎn)w的最短路徑，以下是他們的偽碼描述對比，關(guān)于Dijkstra算法的詳細(xì)描述請參考文章
算法實(shí)現(xiàn)：
#include
#include
#define INF 100000
#define MaxVertex 105
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int parent[MaxVertex]; // 并查集
int dist[MaxVertex]; // 距離
int Nv; // 結(jié)點(diǎn)
int Ne; // 邊
int sum; // 權(quán)重和
using namespace std;
vector MST; // 最小生成樹
// 初始化圖信息
void build(){
Vertex v1,v2;
int w;
cin>>Nv>>Ne;
for(int i=1;i<=Nv;i++){
for(int j=1;j<=Nv;j++)
G[i][j] = 0; // 初始化圖
dist[i] = INF; // 初始化距離
parent[i] = -1; // 初始化并查集
}
// 初始化點(diǎn)
for(int i=0;i>v1>>v2>>w;
G[v1][v2] = w;
G[v2][v1] = w;
}
}
// Prim算法前的初始化
void IniPrim(Vertex s){
dist[s] = 0;
MST.push_back(s);
for(Vertex i =1;i<=Nv;i++)
if(G[s][i]){
dist[i] = G[s][i];
parent[i] = s;
}
}
// 查找未收錄中dist最小的點(diǎn)
Vertex FindMin(){
int min = INF;
Vertex xb = -1;
for(Vertex i=1;i<=Nv;i++)
if(dist[i] && dist[i] < min){
min = dist[i];
xb = i;
}
return xb;
}
void output(){
cout<<"被收錄順序："<關(guān)于prim算法的更加詳細(xì)講解請參考視頻 https://www.bilibili.com/video/av55114968?p=99
3.kruskal算法
Kruskal算法也可以用來解決最小生成樹的問題，其算法思想很容易理解，典型的邊貪心，其算法思想為：
● 在初始狀態(tài)時(shí)隱去圖中所有的邊，這樣圖中每個(gè)頂點(diǎn)都是一個(gè)單獨(dú)的連通塊，一共有n個(gè)連通塊
● 對所有邊按邊權(quán)從小到大進(jìn)行排序
● 按邊權(quán)從小到大測試所有邊，如果當(dāng)前測試邊所連接的兩個(gè)頂點(diǎn)不在同一個(gè)連通塊中，則把這條測試邊加入當(dāng)前最小生成樹中，否則，將邊舍棄。
● 重復(fù)執(zhí)行上一步驟，直到最小生成樹中的邊數(shù)等于總頂點(diǎn)數(shù)減一 或者測試完所有邊時(shí)結(jié)束；如果結(jié)束時(shí)，最小生成樹的邊數(shù)小于總頂點(diǎn)數(shù)減一，說明該圖不連通。
請看下面的Gif圖！
算法實(shí)現(xiàn)：
#include
#include
#include
#include
#define INF 100000
#define MaxVertex 105
typedef int Vertex;
int G[MaxVertex][MaxVertex];
int parent[MaxVertex]; // 并查集最小生成樹
int Nv; // 結(jié)點(diǎn)
int Ne; // 邊
int sum; // 權(quán)重和
using namespace std;
struct Node{
Vertex v1;
Vertex v2;
int weight; // 權(quán)重
// 重載運(yùn)算符成最大堆
bool operator < (const Node &a) const
{
return weight>a.weight;
}
};
vector MST; // 最小生成樹
priority_queue q; // 最小堆
// 初始化圖信息
void build(){
Vertex v1,v2;
int w;
cin>>Nv>>Ne;
for(int i=1;i<=Nv;i++){
for(int j=1;j<=Nv;j++)
G[i][j] = 0; // 初始化圖
parent[i] = -1;
}
// 初始化點(diǎn)
for(int i=0;i>v1>>v2>>w;
struct Node tmpE;
tmpE.v1 = v1;
tmpE.v2 = v2;
tmpE.weight = w;
q.push(tmpE);
}
}
// 路徑壓縮查找
int Find(int x){
if(parent[x] < 0)
return x;
else
return parent[x] = Find(parent[x]);
}
// 按秩歸并
void Union(int x1,int x2){
if(parent[x1] < parent[x2]){
parent[x1] += parent[x2];
parent[x2] = x1;
}else{
parent[x2] += parent[x1];
parent[x1] = x2;
}
}
void Kruskal(){
// 最小生成樹的邊不到 Nv-1 條且還有邊
while(MST.size()!= Nv-1 && !q.empty()){
Node E = q.top(); // 從最小堆取出一條權(quán)重最小的邊
q.pop(); // 出隊(duì)這條邊
if(Find(E.v1) != Find(E.v2)){ // 檢測兩條邊是否在同一集合
sum += E.weight;
Union(E.v1,E.v2); // 并起來
MST.push_back(E);
}
}
}
void output(){
cout<<"被收錄順序："<上述就是小編為大家分享的c語言實(shí)現(xiàn)最小生成樹的方法了，如果您也有類似的疑惑，不妨參照上述方法進(jìn)行嘗試。如果想了解更多相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊。
本文標(biāo)題：c語言如何實(shí)現(xiàn)最小生成樹
鏈接地址：http://weahome.cn/article/jseejc.html
重慶分公司
重慶分公司
