[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）
