[TOC]
# 介紹
設G=(V,E)是無向連通帶權圖（connected，weighted，undirected），即一個網絡。E中的每條邊(v,w)的權為c[v][w]。如果G的一個子圖G'是一棵包含G的所有頂點的一棵樹，則稱，G'為G的生成樹。生成樹上各邊權的總和稱為該樹的費用。
在G的所有的生成樹中，耗費最小的生成樹稱為G的最小生成樹。
網絡的最小生成樹在實際中有廣泛應用，如快遞員在進行送信的時候能夠選擇花費代價最小的通路來完成需求。
# 最小生成樹的性質
#### MST性質
設G=(V,E)是連通帶權圖，U是V的一個真子集。如果(u,v)∈E,且u∈U,v∈V-U,
且在所有這樣的邊里，(u,v)的權c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中的一條邊。這個性質叫做MST性質。
#### 證明
# 窮舉法
如圖所示，假設用窮舉法來解決這個問題，對于4結點的圖來說，一共用16種可能，我們需要列舉出所有的可能性，并選擇花費代價最小的一種。
# Prim算法
### 算法描述
### 實現
### 算法過程
```
void Prim(int n,Type **c) {
T = {};
S = {1};
while(S!=V) {
(i,j)=i∈S且j∈V-S的最小權邊;
T = T∪{(i,j)};
S =S∪{j};
}
}
```
### 復雜度分析
時間復雜度為n^2
### 代碼實現-1（not finished）
```
/*
Program for finding minimum Spanning Tree using Prim's Algorithm
Author: PracsPedia www.pracspedia.com
*/
#include<stdio.h>
#include<conio.h>
int n, cost[10][10];
void prim()
{
int i,j,k,l,x,nr[10],temp,min_cost=0,tree[10][3];
/* For first smallest edge */
temp=cost[0][0];
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
if(temp > cost[i][j])
{
temp=cost[i][j];
k=i;
l=j;
}
}
}
/* Now we have fist smallest edge in graph */
tree[0][0]=k;
tree[0][1]=l;
tree[0][2]=temp;
min_cost=temp;
/* Now we have to find min dis of each
vertex from either k or l
by initialising nr[] array */
for(i=0;i< n;i++)
{
if(cost[i][k]< cost[i][l])
nr[i]=k;
else
nr[i]=l;
}
/* To indicate visited vertex initialise nr[] for them to 100 */
nr[k]=100;
nr[l]=100;
/* Now find out remaining n-2 edges */
temp=99;
for(i=1;i< n-1;i++)
{
for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] < temp)
{
temp=cost[j][nr[j]];
x=j;
}
}
/* Now i have got next vertex */
tree[i][0]=x;
tree[i][1]=nr[x];
tree[i][2]=cost[x][nr[x]];
min_cost=min_cost+cost[x][nr[x]];
nr[x]=100;
/* Now find if x is nearest to any vertex
than its previous near value */
for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])
nr[j]=x;
}
temp=99;
}
/* Now i have the answer, just going to print it */
printf("\n The min spanning tree is:- \n");
for(i=0;i < n-1;i++)
{
for(j=0;j < 3;j++)
printf("%d\t", tree[i][j]);
printf("\n");
}
printf("\n Min cost:- %d", min_cost);
}
void main()
{
int i,j;
clrscr();
printf("\n Enter the no. of vertices:- ");
scanf("%d", &n);
printf ("\n Enter the costs of edges in matrix form:- ");
for(i=0;i< n;i++)
for(j=0;j< n;j++)
scanf("%d",&cost[i][j]);
printf("\n The matrix is:- \n");
for(i=0;i< n;i++)
{
for(j=0;j < n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
prim();
getch();
}
```
# Kruskal算法
### 算法描述和實現
### 算法過程
### 代碼實現-1（not finished）
