A. prim演算法和kruskal 演算法哪個好
Kruskal演算法適用於邊稀疏的情形,而Prim演算法適用於邊稠密的情形
B. Prim 演算法和 Kruskal 演算法
1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；
2).初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {},為空；
3).重復下列操作，直到Vnew = V：
a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；
b.將v加入集合Vnew中，將<u, v>邊加入集合Enew中；
4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。
反證法 ：假設prim生成的不是最小生成樹
1).設prim生成的樹為G0
2).假設存在Gmin使得cost(Gmin)<cost(G0) 則在Gmin中存在<u,v>不屬於G0
3).將<u,v>加入G0中可得一個環，且<u,v>不是該環的最長邊(這是因為<u,v>∈Gmin)
4).這與prim每次生成最短邊矛盾
5).故假設不成立，命題得證.
1).記Graph中有v個頂點，e個邊
2).新建圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).將原圖Graph中所有e個邊按權值從小到大排序
4).循環：從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節點都在同一個連通分量中
如果這條邊連接的兩個節點於圖Graphnew中不在同一個連通分量中，添加這條邊到圖Graphnew中
歸納基礎：
n=1，顯然能夠找到最小生成樹。
歸納過程：
假設Kruskal演算法對n≤k階圖適用，那麼，在k+1階圖G中，我們把最短邊的兩個端點a和b做一個合並操作，即把u與v合為一個點v'，把原來接在u和v的邊都接到v'上去，這樣就能夠得到一個k階圖G'(u,v的合並是k+1少一條邊)，G'最小生成樹T'可以用Kruskal演算法得到。
我們證明T'+{<u,v>}是G的最小生成樹。
用反證法，如果T'+{<u,v>}不是最小生成樹，最小生成樹是T，即W(T)<W(T'+{<u,v>})。顯然T應該包含<u,v>，否則，可以用<u,v>加入到T中，形成一個環，刪除環上原有的任意一條邊，形成一棵更小權值的生成樹。而T-{<u,v>}，是G'的生成樹。所以W(T-{<u,v>})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>})，產生了矛盾。於是假設不成立，T'+{<u,v>}是G的最小生成樹，Kruskal演算法對k+1階圖也適用。
由數學歸納法，Kruskal演算法得證。
C. 最小生成樹兩種演算法有何區別
主要有兩個：
1.普里姆（Prim)演算法
特點：時間復雜度為O(n2).適合於求邊稠密的最小生成樹。
2.克魯斯卡爾（Kruskal)演算法
特點：時間復雜度為O(eloge)(e為網中邊數），適合於求稀疏的網的最小生成樹。
D. 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條邊。這個過程一直進行到只剩下一個連通分支時為止
E. KRUSKAL演算法和PRIM演算法
不是吧，網路白科裡面有這倆個演算法的詳細的講解，你可以去查查
F. 最小生成樹 普里姆演算法和克魯斯卡爾演算法
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;
}
代碼來自網路
G. 如何用淺顯的語言解釋Kruskal演算法和Prim演算法
不嚴謹的說：將全集分為遍歷集合未遍歷集。兩種演算法都是遍歷集慢慢擴大為全集的過程。
Kruskal：集合中元素是邊，每次從未遍歷集中找一個最短邊，如果遍歷集包含它後不會構成迴路，就包含，重復過程直到所有點都連通。
Prim：集合中元素是點，每次從未遍歷集中找一個距離遍歷集距離最近的點，將其包含，重復過程直到包含所有點。
當然對於Kruskal，遍歷集並沒有擴展為全集，把全部邊都包含了也沒有意義了。
H. prim演算法和kruskal演算法的區別
邊數較少可以用Kruskal,因為Kruskal演算法每次查找最短的邊。 邊數較多可以用Prim，因為它是每次加一個頂點，對邊數多的適用。