參考這篇部落格：
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
總結： prim算法： 算法簡單描述
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來描述所得到的最小生成樹。
下面對算法的圖例描述
| 圖例 | 說明 | 不可選 | 可選 | 已選（Vnew） |
|---|---|---|---|---|
 | 此為原始的權重連通圖。每條邊一側的數字代表其權值。 | - | - | - |
 | 頂點D被任意選為起始點。頂點A、B、E和F通過單條邊與D相連。A是距離D最近的頂點，是以将A及對應邊AD以高亮表示。 | C, G | A, B, E, F | D |
| | 下一個頂點為距離D或A最近的頂點。B距D為9，距A為7，E為15，F為6。是以，F距D或A最近，是以将頂點F與相應邊DF以高亮表示。 | C, G | B, E, F | A, D |
| | 算法繼續重複上面的步驟。距離A為7的頂點B被高亮表示。 | C | B, E, G | A, D, F |
| | 在目前情況下，可以在C、E與G間進行選擇。C距B為8，E距B為7，G距F為11。E最近，是以将頂點E與相應邊BE高亮表示。 | 無 | C, E, G | A, D, F, B |
| | 這裡，可供選擇的頂點隻有C和G。C距E為5，G距E為9，故選取C，并與邊EC一同高亮表示。 | 無 | C, G | A, D, F, B, E |
| | 頂點G是唯一剩下的頂點，它距F為11，距E為9，E最近，故高亮表示G及相應邊EG。 | 無 | G | A, D, F, B, E, C |
| | 現在，所有頂點均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權值之和為39。 | 無 | 無 | A, D, F, B, E, C, G |
練習：poj1258：
代碼：#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 1000000
long m,n,sum;
long map[1000][1000],dis[1000],vis[1000];
int prim(long map[][1000],long n)
{
int min;
sum=0;
for(int i=1; i<=n; i++)
dis[i]=map[1][i];
memset(vis,0,sizeof(vis));
vis[1]=1;
for(int i=1; i<n; i++)
{
min=max;
int u=-1;
for(int j=1; j<=n; j++)
if(dis[j]<min&&!vis[j])
{
min=dis[j];
u=j;
}
if(u==-1)break;
vis[u]=1;
sum+=min;
for(int j=1; j<=n; j++)
if(map[u][j]<dis[j])
dis[j]=map[u][j];
}
return sum;
}
int main()
{
while(scanf("%d",&m)!=EOF)
{
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++)
scanf("%d",&map[i][j]);
printf("%d\n",prim(map,m));
}
return 0;
} Kruskal算法： 算法簡單描述
1).記Graph中有v個頂點，e個邊
2).建立圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).将原圖Graph中所有e個邊按權值從小到大排序
4).循環：從權值最小的邊開始周遊每條邊 直至圖Graph中所有的節點都在同一個連通分量中
if 這條邊連接配接的兩個節點于圖Graphnew中不在同一個連通分量中
添加這條邊到圖Graphnew中
圖例描述：
圖論之最小生成樹-prim算法和Kruskal算法參考這篇部落格： http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
首先第一步，我們有一張圖Graph，有若幹點和邊
圖論之最小生成樹-prim算法和Kruskal算法參考這篇部落格： http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
将所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這裡再次展現了貪心算法的思想。資源排序，對局部最優的資源進行選擇，排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了右圖
圖論之最小生成樹-prim算法和Kruskal算法參考這篇部落格： http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
在剩下的變中尋找。我們找到了CE。這裡邊的權重也是5
圖論之最小生成樹-prim算法和Kruskal算法參考這篇部落格： http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
依次類推我們找到了6,7,7，即DF，AB，BE。
圖論之最小生成樹-prim算法和Kruskal算法參考這篇部落格： http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
下面繼續選擇， BC或者EF盡管現在長度為8的邊是最小的未選擇的邊。但是現在他們已經連通了（對于BC可以通過CE,EB來連接配接，類似的EF可以通過EB,BA,AD,DF來接連）。是以不需要選擇他們。類似的BD也已經連通了（這裡上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是右：
練習：poj1251
代碼：#include<iostream>
#include<cstdio>
#include <algorithm>
using namespace std;
#define MAX 26
/* 定義邊(x,y)，權為w */
struct node
{
int x, y;
int w;
};
struct node e[MAX * MAX];
int father[MAX];
int ans;
int cmp(struct node a, struct node b)
{
return a.w < b.w;
}
int cha(int x)
{
if (x != father[x])
father[x] = cha(father[x]);
return father[x];
}
void bing(int x, int y, int w)
{
int xx=cha(x);
int yy=cha(y);
if (xx== yy) return;
father[x] = y;
ans += w;
}
int main()
{
int k, m, n;
char ch;
while(scanf("%d",&m)!=-1&& m != 0)
{
k = 0;
for (int i = 0; i < m; i++)
father[i]=i;
for (int i = 0; i < m - 1; i++)
{
cin >> ch >> n;
for (int j = 0; j < n; j++)
{
cin >> ch >> e[k].w;
//scanf("%c%d",ch,&e[k].w);
// getchar();
e[k].x = i;
e[k].y = ch - 'A';
k++;
}
}
sort(e, e + k,cmp);
ans =0;
for (int i = 0; i < k; i++)
{
int h=cha(e[i].x),g=cha(e[i].y);
bing(h,g,e[i].w);
}
printf("%d\n",ans);
}
return 0;
}
PS: 自己的了解，大多數題用k可以搞定，但是有些題是不能的，我記憶的方法是prim是從點來找，而k是通過定義先将所有的邊進行排序操作之後通過邊的權值來繼續算法的。（希望不要弄混了。看自己的想法吧）。