本篇主要圖文講解最小生成樹的實現(xiàn)和算法。

一、最小生成樹

最小生成樹（minimum spanning tree）是由n個頂點，n-1條邊，將一個連通圖連接起來，且使權(quán)值最小的結(jié)構(gòu)。最小生成樹可以用Prim（普里姆）算法或kruskal（克魯斯卡爾）算法求出。

此外還可以用bfs和dfs生成，分別叫bfs生成樹和dfs生成樹。

例：

二、Prim（普里姆）算法

這里就采用的是鄰接矩陣存儲的，Prim和最短路中的dijkstra很像，方法：

（1）先建立一個只有一個結(jié)點的樹，這個結(jié)點可以是原圖中任意的一個結(jié)點。

（2）使用一條邊擴展這個樹，要求這條邊一個頂點在樹中另一 個頂點不在樹中，并且這條邊的權(quán)值要求最小。

（3）重復(fù)步驟（2）直到所有頂點都在樹中。

如圖：

#include<stdio.h>
#define MAX 100
#define MAXCOST 100000

int graph[MAX][MAX];

void prim(int graph[][MAX], int n)
{
    int lowcost[MAX];//lowcost[i]:表示以i為終點的邊的最小權(quán)值,當(dāng)lowcost[i]=0表示i點加入了MST
    int mst[MAX];//表示對應(yīng)lowcost[i]的起點，當(dāng)mst[i]=0表示起點i加入MST
    int i, j, min, minid, sum = 0;
    for (i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i];//lowcost存放頂點1可達點的路徑長度
        mst[i] = 1;//初始化以1位起始點
    }
    mst[1] = 0;
    for (i = 2; i <= n; i++)
    {
        min = MAXCOST;
        minid = 0;
        for (j = 2; j <= n; j++)
        {
            if (lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];//找出權(quán)值最短的路徑長度
                minid = j; //找出最小的ID
            }
        }
        printf("V%d-V%d=%d\n",mst[minid],minid,min);
        sum += min;//求和
        lowcost[minid] = 0;//該處最短路徑置為0
        for (j = 2; j <= n; j++)
        {
            if (graph[minid][j] < lowcost[j])//對這一點直達的頂點進行路徑更新
            {
                lowcost[j] = graph[minid][j];
                mst[j] = minid;
            }
        }
    }
    printf("最小權(quán)值之和=%d\n",sum);
}
int main()
{
    int i, j, k, m, n;
    int x, y, cost;
    scanf("%d%d",&m,&n);//m=頂點的個數(shù)，n=邊的個數(shù)

    for (i = 1; i <= m; i++)//初始化圖
    {
        for (j = 1; j <= m; j++)
        {
            graph[i][j] = MAXCOST;
        }
    }
    for (k = 1; k <= n; k++)
    {
    scanf("%d%d%d",&i,&j,&cost);
        graph[i][j] = cost;
        graph[j][i] = cost;
    }

    prim(graph, m);
    return 0;
}

三、kruskal（克魯斯卡爾）算法

Kruskal 算法是能夠在O(mlogm) 的時間內(nèi)得到一個最小生成樹的算 法。它主要是基于貪心的思想：

（1）將邊按照邊權(quán)從小到大排序，并建立一個沒有邊的圖T。

（2）選出一條沒有被選過的邊權(quán)最小的邊。

（3）如果這條邊兩個頂點在T 中所在的連通塊不相同，那么將 它加入圖T， 相同就跳過。

（4）重復(fù)（2）和（3）直到圖T連通為止。

其實這里只需要維護連通性，可以不需要真正建立圖T，還可以用并查集來維護。

這里用鄰接表（不是鏈表）進行操作：

#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct{
	int vex1;                     //邊的起始頂點
	int vex2;                      //邊的終止頂點
	int weight;                    //邊的權(quán)值
}Edge;
void kruskal(Edge E[],int n,int e)
{
	int i,j,m1,m2,sn1,sn2,k,sum=0;
	int vset[n+1];
	//借用一個輔助數(shù)組vset[i]用來判斷某邊是否加入了最小生成樹集合
	//就是把每個頂點都看成一個連通分量，并查集數(shù)組初始化
	for(i=1;i<=n;i++)        //初始化輔助數(shù)組
		vset[i]=i;
	k=1;//表示當(dāng)前構(gòu)造最小生成樹的第k條邊，初值為1
  	j=0;//E中邊的下標(biāo)，初值為0
   while(k<e)//生成的邊數(shù)小于e時繼續(xù)循環(huán)
   {
       m1=E[j].vex1;
       m2=E[j].vex2;//取一條邊的兩個鄰接點
       sn1=vset[m1];
       sn2=vset[m2];
	       //分別得到兩個頂點所屬的集合編號
	    if(sn1!=sn2)//兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊
	    {//防止出現(xiàn)閉合回路
			printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
			sum+=E[j].weight;
			k++;                //生成邊數(shù)增加
			if(k>=n)
				break;
			for(i=1;i<=n;i++)    //兩個集合統(tǒng)一編號
				if (vset[i]==sn2)  //集合編號為sn2的改為sn1
					vset[i]=sn1;
	    }
     j++;                  //掃描下一條邊
   }
    printf("最小權(quán)值之和=%d\n",sum);
}
//以下為快排
int fun(Edge arr[],int low,int high)
 {
 	int key;
 	Edge lowx;
 	lowx=arr[low];
 	key=arr[low].weight;
 	while(low<high)
 	{
 		while(low<high && arr[high].weight>=key)
 			high--;
 		if(low<high)
 			arr[low++]=arr[high];

 		while(low<high && arr[low].weight<=key)
 			low++;
 		if(low<high)
 			arr[high--]=arr[low];
	 }
	 arr[low]=lowx;
	 return low;
  }
void quick_sort(Edge arr[],int start,int end)
{
	int pos;
	if(start<end)
	{
	pos=fun(arr,start,end);
	quick_sort(arr,start,pos-1);
	quick_sort(arr,pos+1,end);
	}
}
int main()
{
	Edge E[MAXE];
	int nume,numn;
    //freopen("1.txt","r",stdin);//文件輸入
	printf("輸入頂數(shù)和邊數(shù):\n");
	scanf("%d%d",&numn,&nume);
	for(int i=0;i<nume;i++)
		scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);
	quick_sort(E,0,nume-1);
	kruskal(E,numn,nume);
}