❶ 最小生成樹兩種演算法有何區別
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
❷ prim和kruscal演算法得到的最小生成樹是否一樣
應該不一樣。可以用一個圖根據兩演算法試一下，若一樣，再修改圖，之後應該就可以了。
（網路或者查書本更加有效……）
構造G的最小生成樹的Prim演算法的基本思想是：首先置S={1}，然後，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-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;
}
代碼來自網路
❹ 普里姆演算法和克魯斯卡爾演算法區別
普里姆演算法和克魯斯卡爾演算法區別如下：
克魯斯卡爾演算法：是在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構埋或成迴路，則放棄，選晌液宴取次小邊。
普里姆演算法：同樣是在未選取的邊中尋找最小邊，但是選取的原則多了宴銀一條，就是該邊必須和已選取的邊相連，比如，如果邊(1, 2)已被選取，那麼接下來選取的邊，必須是和頂點1，或者頂點2相連的。