1. 無向圖與開放樹
在講最小生成樹之前，先來說一說開放樹。連通而無環路的無向圖稱做
開放樹
。如果指定開放樹中某一頂點為根，并且把每一條邊看成是背離根的，則一棵開放樹變成一棵樹。
開放樹有2個性質：
- 具有n>=1個頂點的開放樹包含n-1條邊
- 如果在開放樹中任意增加一條邊，将構成一個環路
如下列兩個圖：
2. 最小生成樹
隻針對無向圖
假設E中的每條邊都有權重，為c(u,v)，也叫做邊長。圖G的一棵生成樹是連接配接V中所有頂點的一棵開放樹。将生成樹中所有邊長的總和稱為生成樹的價。
使這個價最小的生成樹稱為圖的最小生成樹
。
設G=(V,E)是一個連通圖，在E上定義一個權函數C，且{(V1,T1),(V2,T2),...,(Vk,Tk)}是G的任意生成森林，令
其中，|T| <= |E|，又假設e=(v,w)是E-T中的一條邊，其權值C[v][w]最小，而且v在V1中，w不在V1中，則圖G有一棵包含T和e的生成樹，其價不大于包含T的任何生成樹的價。
以上的性質下，兩種算法應運而生：Prim算法和Kruskal算法
- Prim算法
/*輸入為權重無向圖G=(V,E)，其中V={1,2,3,...,n}
要點：引進集合U和T，U準備放頂點，T準備放邊。初值為U={1}，T為空，選擇最小權的邊(u,v)，使u在U中，v在V-U中，将v加入U，(u,v)加入T。重複這個過程 */
void Prim(costtype C[n+1][n+1])
{
/*CLOSECT表示U中的頂點，(i,CLOSECT[i])具有最小的權，而LOWCOST[i]表示該邊的權，其中i不在U中 */
costtype LOWCOST[n+1];
int CLOSEST[n+1]；
int i,j,k;
costtype min;
for(i=2;i <= n;i++)
{
//初始化
LOWCOST[i] = C[1][i]；
CLOSEST[i] = 1;
}
for(i=2;i=n;i++)
{
min = LOWCOST[i];
k=i;
//找出最小權的邊
for(j=2;j<=n;j++) {
if(LOWCOST[j] < min) {
min = LOWCOST[j];
k = j;
}
cout<<"("<<k<<","<<CLOSECT[k] << ")"<<endl;
LOWCOST[k] = infinity; /* k加入U */
//對新加入的k的基礎上，更新LOWCOST和CLOSECT
for(j = 2;j<=n;j++) {
if(C[k][j] < LOWCOST[j] && LOWCOST[j] != infinity) {
LOWCOST[j] = C[k][j];
CLOSECT[j] = k;
}
}
}
}
- Kruskal算法
void Kruskal(V,T)
{
T = V;
ncomp = n;
while(ncomp > 1) {
從E中取出并删除權最小的邊(v,u)
if(v和u屬于T中不同的連通分量) {
T= T + (v,u);
ncomp --;
}
}
}
Prim算法複雜度為O(n2)，而Kruskal算法複雜度為O(ne)，故Prim算法适用于點較少的情況
3. 最小樹形圖
隻針對有向圖
首先為除根之外的每個點標明一條入邊，這條入邊一定要是所有入邊中最小的。現在所有的最小入邊都選擇出來了，如果這個入邊集不存在有向環的話，我們可以證明這個集合就是該圖的最小樹形圖。這個證明并不是很難。如果存在有向環的話，我們就要将這個有向環縮成一個人工頂點，同時改變圖中邊的權。假設某點u在該環上，并設這個環中指向u的邊權是in[u]，那麼對于每條從u出發的邊(u, i, w)，w為權，在新圖中連接配接(new, i, w)的邊，其中new為新加的人工頂點; 對于每條進入u的邊(i, u, w)，在新圖中建立邊(i, new, w-in[u])的邊。
int ZLEdmonds(int n,int map[maxn][maxn])
{
bool visited[maxn],flag[[maxn];
int pre[maxn];
int sum=0,i,j,k;
for( i=0; i<n; i++){
flag[i]=false;
map[i][i]=INF;
}
pre[0]=0;
while( true){
//求最短弧集合E0。
for( i=1; i<n; i++){
if( flag[i]) continue;
pre[i]=i;
for( j=0; j<n; j++){ //pre[i]儲存終點為i的最短弧的起點。
if( !flag[j]&&map[j][i]<map[pre[i]][i])
pre[i]=j;
}
if( pre[i]==i) return -1;
}
//檢查E0
for( i=1; i<n; i++){
if( flag[i]) continue;
for( j=0; j<n; j++)
visited[j]=false;
visited[0]=true;
j=i;
do{
visited[j]=true;
j=pre[j];
}while( !visited[j]);
if( !j) continue; //沒有找到環。
i=j;//将整個環的權值儲存，累計入原圖的最小樹形圖
do{
sum+=map[pre[j]][j];
j=pre[j];
}while( j!=i);
j=i;//對于環上的點有關的邊，修改邊權
do{
for( k=0; k<n; k++){
if( !flag[k]&&map[k][j]&&map[k][j]<INF&&k!=pre[j])
map[k][j]-=map[pre[j]][j];
}
j=pre[j];
}while( j!=i);
//縮點，将整個環縮成i号點，所有環上的點有關的邊轉移到點i
for( j=0; j<n; j++){
if( j==i) continue;
for( k=pre[i]; k!=i; k++){
if( map[k][j]<map[i][j])
map[i][j]=map[k][j];
if( map[j][k]<map[j][i])
map[j][i]=map[j][k];
}
}
//标記環上其他的點為被縮掉 下次再找Ei時不參與
for( j=pre[i]; j!=i; j=pre[j])
falg[j]=true;
//目前環縮點結束，形成新的圖G'，跳出繼續求G'的最小樹形圖 ，累計入sum。
}
if( i==n){
for( i=0; i<n; i++)
if( !flag[i])
sum+=map[pre[i]][i];
break;
}
}
return sum;
}
作者: vachester
出處：http://www.cnblogs.com/vachester/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連結，否則保留追究法律責任的權利。