最小樹演算法

1. 求最小生成樹的kruska演算法，效率盡量高，盡量多點注釋！c++代碼

/*
基本演算法思想：
為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小，自然應從權值最小的邊選起，直至選出 n-1 條互不構成迴路的權值最小邊為止。
具體作法如下：首先構造一個只含 n 個頂點的森林，然後依權值從小到大從連通網中選擇不使森林中產生迴路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網的最小生成樹。
由於生成樹上不允許有迴路，因此並非每一條居當前權值最小的邊都可選。

用並查積 和 克魯是卡爾演算法實現查找最短邊
利用快排按邊遞增排列，每次從中選出最短邊,同時將最短邊的兩個頂點並入到集合中
心得：利用並查積 和 kruskal演算法結合找最短路徑可以使查找的效率更高
加入集合中的邊都是構成最小生成樹的邊，所以每家一次sum 都要加上這兩個頂點之間的距離
*/
/*下面的代碼輸入n個節點，然後輸入n*（n-1）/2條邊及權值，輸出是連通這些邊的最小權值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始點
int v; //終結點
int w; //權重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //從小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父親
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //並查集初始化，每個節點到父親是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //點edge[i].u的父親是x
y=find(edge[i].v); //點edge[i].v的父親是y
if(x!=y) //判斷是否會路
{
count++; //加上一條邊
p[x]=y; //把x和y加入統一個集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //輸入n個節點
{
int i;
for(i=0;i<n*(n-1)/2;i++) //輸入 n*（n-1）/2條邊
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示點edge[i].u和點edge[i].v之間的權重為 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

樓主，這可是本人一個字一個字敲出來點，要給分啊

2. 已知一個無向圖如下，分別用普里姆和克魯斯卡爾演算法生成最小生成樹（假設以1為起點，試畫出構造過程）。

1)普里姆演算法思想
從圖中任意取出一個頂點， 把它當成棵樹，然後從與這棵樹相接的邊中選取一條最短(權值最小)的邊， 並將這條邊及其所連接的頂點也並入這棵樹中，此時得到了一棵有兩個頂點的樹。然後從與這棵樹相接的邊中選取一條最短的邊，並將這條邊及其所連頂點並入當前樹中，得到一棵有3個頂點的樹。以此類推，直到圖中所有頂點都被並入樹中為止，此時得到的生成樹就是最小生成樹。
2)克魯斯卡爾演算法思想
先將邊中的權值從小到大排序，每次找出候選邊中權值最小的邊，就將該邊並入生成樹中。重復此過程直到所有邊都被檢測完為止。其中要注意的是克魯斯卡爾演算法需要用到並查集，以此來判斷接下來要並入的邊是否會和已並入的邊構成迴路。這兩個圖分別用普里姆和克魯斯卡爾生成的最小生成樹見圖。

需要注意的是，在接下來要並入的最小權值不唯一的情況下，可以選取的邊是不唯一的，所以其最小生成樹也不唯一。(純手打，望採納，謝謝。)

3. 最小生成樹 普里姆演算法有問

普里姆演算法構造最小生成樹演算法的思想是：選擇一個結點，然後從這個結點開始，選擇權值最小的邊，用一條邊連接，然後再以前面的那個結點開始，和你連接的那個結點作為根節點，再選擇權值最小的邊進行連接。
對權值給出解釋：以上圖為例，權值就是你第一個圖那幾條邊（弧）上，所標的數字。
對樓主所提出的問題：並不是連接那圓圈中最小的圓圈，如果沒錯的話，那圓圈中的數字表示的是V1---V6六個頂點，並不是代表數字，以3和6為頂點，找權值最小邊，顯然6——4為最小，即權值為2，頂點364相連接的時候各以364為頂點尋找最小邊，應該先從6連接到2，那麼現在加入頂點的為3642頂點，現在以3642為頂點尋找最小邊，應該從2連接到1，現在被連接的有63421，在以63421為頂點尋找最小邊
出現了問題：如果以5為權值的話，無論從2連接到4還是從3連接到4都出現了環，當然我們知道數中是不能出現環的，所以尋找次小的，剩餘5與13之間權值最小為13.所以將1連接5，即得到最小生成樹。
樓主可以按照我說的在紙上畫一下試試
從6連接到3因為有前提條件：從頂點V3開始用普里姆方法求其最小生成數，可見是從頂點3連接到6，而不是從6連接到3
希望可以解決樓主的疑惑，謝謝！