最小生成樹kruskal演算法

① 圖所示是一個無向帶權圖,請分別按Prim演算法和Kruskal演算法求最小生成樹.

•普里姆（Prim）演算法

基本思想

假設N=(V,E)是一個具有n個頂點的連通網，T=(U,TE)是所求的最小生成樹，其中U是T的頂點集，TE是T的邊集。

（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）並入集合TE，同時將v0並入U；

（3）重復（2），直到U=V為止。

此時，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹。

注意：1.最小生成樹不唯一。

2.該圖從節點最小開始。

② 克魯斯卡爾演算法求最小生成樹

克魯斯卡爾演算法的基本思想，這是我自己結合教材理解的，難免有誤，謹慎參考：
1：將圖中的n頂點看成是n個集合。解釋為，圖中共有6個頂點，那麼就有六個集合。即a,b,c,d,e,f各自分別都是一個集合。｛a｝,｛b｝等。
2：按權值由小到大的順序選擇邊。所選邊應滿足兩個頂點不在同一個頂點集合內。將該邊放到生成樹邊的集合，同時將該邊的兩個頂點所在的集合合並。這是書上的描述，可能有點難理解，這里解釋一下：
首先，選擇權值最小的邊，即為圖中的（a,c）邊，此時a,c滿足不在同一個頂點集合內，將這個邊記錄下來，然後合並這兩個頂點的集合，即此時剩下五個頂點集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝
3：重復步驟2，直到所有的頂點都在同一個集合內！解釋如下：
此時剩下的邊中權值最小的為（d，f），滿足不在同一個頂點集合，所以記錄下該邊，然後合並這兩個頂點集合。新的頂點集合為｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝
接著，繼續重復，選擇邊（b，e），滿足不在同一個頂點集合內，所以記錄下該邊，然後再次合並這兩個集合，新的集合為｛a,c｝ ｛d,f｝ ｛b,e｝
繼續，選擇邊（c,f）,滿足不在同一個頂點集合內，所以記錄下該邊，然後合並這兩個頂點所在的集合，新集合為｛a,c,d,f｝ ｛b,e｝
再繼續，選擇權值為15的邊，發現邊（c,d）和邊（a,d）都不滿足條件不在同一個頂點集合內，所以只能選擇邊（b,c），記錄下該邊，然後合並頂點集合，新集合為｛a,b,c,d,e,f｝，此時所有點都在同一集合內，所以結束！
4：將上面我們記錄的那些邊連接起來就行了！這就是最小生成樹，附本人手繪：

③ 圖的最小生成樹演算法

圖的生成樹和最小生成樹生成樹(SpanningTree):如果一個圖的子圖是一個包含圖所有節點的樹,那這個子圖就稱為生成樹.

④ 求最小生成樹 利用Kruskal演算法求圖G的一棵最小生成樹T，用c語言

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 並查集存儲結構
// Tags: 值為-1則表示為根節點
struct DisjointSet
{
int *arr;// 值為父節點下標
int number;// arr元素個數
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化並查集結構
// Input: number - 元素的個數
// Output:s - number個元素自成一集的並查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 刪除並查集結構
// Input: s - 並查集存儲結構
// Output:s - 回收內存後的結構
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 獲得某個結點的根節點
// Input: s - 並查集; index - 結點下標
// Output: return - 根節點下標
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合並index1和index2所在的兩個集合
// Input: index1 - 結點1下標, index2 - 結點2下標
// Output: s - 並查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判斷兩個結點是否在同一個集合中
// Input: s - 並查集, index1 - 結點1下標, index2 - 結點2下標
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 圖的鄰接矩陣
struct Graph
{
int **value;// 權值,-1表示無法到達
int number;
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一個圖
// Input: g - 圖的存儲結構, number - 結點個數
// Output: g - 圖
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一個圖
// Input: g - 圖, number - 結點個數
// Output: g - 圖的存儲結構
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 為圖在a，b間添加一條邊
// Input:e1, e2 - 兩個結點, value - 權值
// Output: graph - 加邊後的圖
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 顯示一條邊
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 邊的兩個結點
int value; // 邊的權值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根據權值判斷兩個邊的大小
// Tags: 由於priority_queue是最大堆，所以這里小於號變成大於號，從而使priority_queue變成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用戶輸入圖的邊
// Input: n - 加邊的個數
// Output: graph - 加邊後的圖
// Tags: Console下用戶輸入點對(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 圖
DisjointSet set;// 並查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化圖
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化並查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗費值
int add_num = 0;// 已經添加了幾個邊
OneEdge min_value_edge;// 當前權值最小邊

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 這里是因為了STL中2叉堆的結構中有一個緩沖區
// 需要將緩沖區中的每一個元素彈出來
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

這個是c++語言的，最小權值存儲在min_pay中，樹存儲在並查集set中，且在獲取最小權值路徑的時候用了STL中的2叉堆，演算法復雜度為O(|V| * lgE)
不知是否滿足您的要求

⑤ prim和kruscal演算法得到的最小生成樹是否一樣

應該不一樣。可以用一個圖根據兩演算法試一下，若一樣，再修改圖，之後應該就可以了。
（網路或者查書本更加有效……）
構造G的最小生成樹的Prim演算法的基本思想是：首先置S={1}，然後，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。
這個過程一直進行到S=V時為止。
Kruskal演算法構造G的最小生成樹：將所有的邊按權從小到大排序。然後從第一條邊開始，依邊權遞增的順序查看每一條邊，並按下述方法連接2個不同的連通分支：當查看到第k條邊(v, w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v, w)將T1和T2連接成一個連通分支，然後繼續查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止

⑥ 最小生成樹 普里姆演算法和克魯斯卡爾演算法

kruskal演算法的時間復雜度主要由排序方法決定，其排序演算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O（eloge）的排序演算法時，克魯斯卡演算法的時間復雜度即為O（eloge），因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成樹效果最好！

克魯斯卡爾演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

普里姆演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。
--以上傳自http://hi..com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html

1.Kruskal
//題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定義邊集
int cmp(const void *a,const void *b)//快排比較函數
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v為點集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}

2.Prim
//題目地址同上

#include <iostream>
using namespace std;

#define M 101
#define maxnum 100001
int dis[M][M];

int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 與Dijksta演算法的差別之處
}
}
return sum;
}

int main()
{
int n,i,j;
while( cin>>n ){

for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}

cout<<prim(n)<<endl;
}
return 0;
}

代碼來自網路

⑦ kruskal演算法是什麼呢

kruskal演算法是求加權連通圖的最小生成樹的演算法。

kruskal演算法總共選擇n- 1條邊，(共n個點)所使用的貪心准則是:從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。

kruskal演算法分e步，其中e是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。

Kruskal演算法基本思想：

每次選不屬於同一連通分量(保證不生成圈)且邊權值最小的頂點，將邊加入MST，並將所在的2個連通分量合並，直到只剩一個連通分量。

排序使用Quicksort(O(eloge))。

檢查是否在同一連通分量用Union-Find，每次Find和union運算近似常數。

Union-Find使用rank啟發式合並和路徑壓縮。

總復雜度O(eloge)=O(elogv) (因為e<n(n-1)/2)。

⑧ 最小生成樹兩種演算法有何區別

主要有兩個：
1.普里姆（Prim)演算法

特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法

特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。

⑨ 用kruskal演算法構造例3的最小生成樹是什麼意思

1.kruskal演算法
假設連通網N＝（V，{E}）。則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T＝（V，{}），圖中每個頂點自成一個連通分量。在E中選擇最小代價的邊，若該邊依附的頂點落在T中不同的連通分量中，則將該邊加入到T中，否則捨去此邊而選擇下一條代價最小的邊，依次類推，直到T中所有頂點都在同一連通分量上為止。
示例如下：

圖中先將每個頂點看作獨立的子圖，然後查找最小權值邊，這條邊是有限制條件的，邊得兩個頂點必須不在同一個圖中，如上圖，第一個圖中找到最小權值邊為（v1，v3），且滿足限制條件，繼續查找到邊（v4，v6），（v2，v5），（v3，v6），當查找到最後一條邊時，僅僅只有（v2，v3）滿足限制條件，其他的如（v3，v4），（v1，v4）都在一個子圖裡面，不滿足條件，至此已經找到最小生成樹的所有邊。
2.kruskal演算法程序設計
由於我們要查找邊權值最小的邊，那麼我們的第一步應該把邊權值排序，這樣就可以很快查找到權值最小的邊，為了簡化程序設計，我們不使用其他的數據結構，僅僅設立一個結構體數組來存儲邊，用一個標記數組來標記哪些邊已經被選擇（實際程序設計的時候沒有用到標記數組）；
解決了邊得存儲和排序問題，現在是演算法最關鍵的就是怎麼判斷邊的兩個頂點不在一個子圖裡面，一個簡單的辦法是設立一個輔助數組f[n]，初始化如下：
void Initialize()
{
int i;
for(i=0; i
f[i] = i;
}
如此初始化是為了讓每個頂點各自為一個圖，如果找到一條邊（i,j）那麼做如下標記：(i
void Mark_same(int i, int j)
{
//找到i的父節點
while(f[i] != i)
{
i= f[i];
}
f[j] = i;//將j指向其父節點
}

上面的標記過程也給了我們怎麼判斷兩個頂點是否在一個圖中找到了方法，即判斷其父節點是否相同，相同則是在一個圖里；
int Is_same(int i, int j)
{
//找到i的父節點
while(f[i] != i)
{
i= f[i];
}
//找到i的父節點
while(f[j] != j)
{
j= f[j];
}
return i == j ? 1 : 0;
}

注意：實際設計程序的時候不用標記已選邊，因為已選擇的邊會講端點集合合並為一個集合，從而在判斷是否為同一集合的時候就可以排除了。

⑩ 最小生成樹是什麼

1.生成樹從前述的深度優先和廣度優先遍歷演算法知，對於一個擁有n個頂點的無向連通圖，它的邊數一般都大於n－1。生成樹是指在連通圖中，由n個頂點和不構成迴路的n－1條邊構成的樹。若由深度優先遍歷得到的生成樹稱為深度優先生成樹，則由廣度優先遍歷得到的生成樹稱為廣度優先生成樹。再進一步分析可知，對於滿足條件，連通圖的n個頂點和不構成迴路的n－1條邊構成的生成樹有多棵，換言之，圖的生成樹不唯一。2.最小生成樹對於帶權的圖，其生成樹的邊也帶權，在這些帶權的生成樹中必有一棵邊的權值之和最小的生成樹，這棵生成樹就是最小（代價）生成樹。

最小生成樹在實際中具有重要用途，如在通信網的設計中，用頂點表示城市，用邊表示兩個城市之間的通信線路，邊的權值表示建造通信線路的費用，這n個城市之間最多可以建n（n－1）／2條線路。如果要求在任意兩個城市之間都有線路相連，且建設費用最少，即從n（n－1）／2條邊中選取權值最小的n－1條，這就是最小生成樹問題。2.構造最小生成樹的基本原則（1）盡可能選取權值最小的邊，但不能構成迴路。

（2）選擇n－1條邊構成最小生成樹。

常見的最小生成樹演算法有普里姆（Prim）演算法和克魯斯卡爾（kruskal）演算法兩種。