最小生成樹
什么是最小生成樹：
1.生成樹：
在一張無向連通有權圖中，我們要從一個節點出發，找到一組有權邊，將所有節點都連接起來，這樣的一組節點和邊將構成一顆樹，也就是生成樹，這顆樹是根據圖而生成的，
2.最小生成樹：
在所有生成樹中，如果其中一棵樹的所有邊的權值和最小，那么就成為最小生成樹，不過最小生成樹可能不是唯一的，下圖中加粗的邊就構成了一顆最小生成樹，
獲得最小生成樹的兩種演算法
1.Kruskal演算法
Kruskal演算法使用的是一種貪婪策略，首先對于V個節點，我們初始生成包含V棵樹的森林，森林中的每一棵樹初始本身就是其單個節點，接下來我們將所有邊E從小到大排序，并由小到達對其進行遍歷，如若找到的一條邊（u，v）中u，v不屬于同一棵樹，那么我們將這個邊（u，v）加入到最小生成樹的邊當中，并將u，v分別所在的兩棵樹a，b進行合并，合并成同一顆樹c，如果u，v所在同一棵樹上，那么我們就不對（u，v）進行上述操作，而將其舍棄，重復上述程序，可以不斷將森林中的樹合并，并不斷將遍歷到的一些邊加入到最小生成樹的邊當中，當森林中的所有樹被合并成一棵樹時，這棵樹就是最小生成樹，演算法結束，
用上面的圖來描述Kruskal演算法的程序：
遍歷邊的順序大致如下：
（u,v） weight decision
0,1 1 加入
0,3 2 加入
1,2 3 加入
4,5 4 加入
0,2 5 舍棄
2,5 6 加入
1,4 7 舍棄
3,5 8 舍棄
下面給出完整的用c實作的Kruskal演算法(基于上面給出的圖獲得最小生成樹)：
#include <stdio.h>
#include <stdlib.h>
//Kruskal演算法獲得最小生成樹
# define N 6
//定義鄰接表
int map[N][N]={
0,1,5,2,0,0,
1,0,3,0,7,0,
5,3,0,0,0,6,
2,0,0,0,0,8,
0,7,0,0,0,4,
0,0,6,8,4,0
};
//設定鄰接表
set_map()
{
int i,j,k;
for(i=0;i<N;i++)
{
printf("請輸入第%d個節點的鄰接關系：\n",i);
for(j=0;j<N;j++)
{
printf("通向節點%d的邊的權值： ",j) ;
scanf("%d",&map[i][j]);
}
}
printf("\n鄰接表設定完畢\n");
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
}
//定義邊
typedef struct edge
{
int u;
int v;
int weight;
} edge;
//定義存放邊的集合
typedef struct edgeList
{
int size;
edge edges[N*N];
} edgeList;
//初始化邊的集合
Init_edgeList(edgeList ** eL)
{
(*eL)=(edgeList *)malloc(sizeof(edgeList));
(*eL)->size=0;
int i,j,k;
//獲得所有邊的資訊并加入到表中
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
if(map[i][j]!=0)
{
(*eL)->edges[(*eL)->size].weight=map[i][j];
(*eL)->edges[(*eL)->size].u=i;
(*eL)->edges[(*eL)->size].v=j;
(*eL)->size++;
}
}
}
//對所有邊按權值從小到大進行排序,即對結構體陣列進行排序
edge t;
for(i=1;i<=(*eL)->size;i++)
{
for(j=0;j<(*eL)->size-i;j++)
{
if((*eL)->edges[j].weight>(*eL)->edges[j+1].weight)
{
t=(*eL)->edges[j];
(*eL)->edges[j]=(*eL)->edges[j+1];
(*eL)->edges[j+1]=t;
}
}
}
}
//定義樹
typedef struct tree
{
edge edges[N-1];
int vertexs[N];
int edge_num;
int flag;
} tree;
//定義森林
typedef struct forest
{
tree trees[N];
int tree_num;
} forest;
//初始化森林和樹
forest* Init_forest()
{
int i,j,k;
forest *f=(forest*)malloc(sizeof(forest));
f->tree_num=N;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++) f->trees[i].vertexs[j]=0;
f->trees[i].vertexs[i]=1;
f->trees[i].edge_num=0;
f->trees[i].flag=1;
}
return f;
}
Union(tree *t1,tree *t2)//合并兩棵樹
{
int i,j;
//將t2中的邊加入到t1當中
for(i=0;i<t2->edge_num;i++)
{
t1->edges[t1->edge_num]=t2->edges[i];
t1->edge_num++;
}
//將t2中的節點加入到t1當中
for(i=0;i<N;i++)
{
if(t2->vertexs[i]==1)
{
t1->vertexs[i]=1;
}
}
//將t2標記為舍棄
t2->flag=0;
}
Kruskal(edgeList *eL,forest *f)
{
int i,j,k,n=1;//n表示最小生成樹中已經存在的節點數
int u,v,t1=-1,t2=-1;
edge e;
while(n!=N)
{
for(i=0;i<N;i++)
{
e=eL->edges[i];
u=e.u;
v=e.v;
//找到u和v分別在哪一棵樹當中
for(j=0;j<N;j++)
{
if(f->trees[j].vertexs[u]==1&&f->trees[j].flag)
{
t1=j;
}
if(f->trees[j].vertexs[v]==1&&f->trees[j].flag)
{
t2=j;
}
}
if(t1!=t2)//如果兩節點不在同一棵樹當中，則將這條邊加入最小生成樹，并將兩棵樹進行合并
{
//將這條邊加入到樹t1中
f->trees[t1].edges[f->trees[t1].edge_num]=e;
f->trees[t1].edge_num++;
f->trees[t1].vertexs[v]=1;
//將t1和t2進行合并
Union(&f->trees[t1],&f->trees[t2]);
f->trees[t2].flag=0;
n++;
}
}
}
}
int main()
{
//set_map();
tree MinTree;
int i,j,k,min_p=0;
edgeList *eL;
Init_edgeList(&eL);
printf("圖的鄰接關系及邊的權重表示如下：\n") ;
for(i=0;i<eL->size;i++)
{
printf("u=%d v=%d weight=%d\n",eL->edges[i].u,eL->edges[i].v,eL->edges[i].weight);
}
forest * f=Init_forest();
Kruskal(eL,f);
//找到最小生成樹的所在
for(i=0;i<N;i++)
{
if(f->trees[i].flag!=0)
{
MinTree=f->trees[i];
}
}
//列印最小生成樹中的每一條邊
printf("\n最小生成樹中的所有邊：\n");
for(i=0;i<MinTree.edge_num;i++)
{
printf("(%d,%d) weight=%d\n",MinTree.edges[i].u,MinTree.edges[i].v,MinTree.edges[i].weight);
min_p+=MinTree.edges[i].weight;
}
printf("\n最小生成樹所有邊的權值之和為:%d\n",min_p);
}
程式運行后結果顯示如下：
上面這段用c語言實作的Kruskal演算法只是我初學Kruskal演算法時按照書上給出的演算法邏輯寫出的，并不是很高效很正統的演算法，但我認為是對于初學者來說是好理解并且形象的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/280962.html
標籤：區塊鏈
下一篇：JAVA基礎匯總:第一章