最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。
最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。
我们将以下面的带权连通图为例讲解这两种算法的实现：
Prim（普里姆）算法
时间复杂度：O（N^2）（N为顶点数）
prim算法又称“加点法”，用于边数较多的带权无向连通图
方法：每次找与之连线权值最小的顶点，将该点加入最小生成树集合中
注意：相同权值任选其中一个即可，但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树：
1.初始化：
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0表示i点加入了VEST。
vest[i]:表示对应lowcost[i]的起点，当vest[i]=0表示起点i加入VEST。
由于我们规定最开始的顶点是1，所以lowcost[1]=0，VEST[1]=0。即只需要对2~n进行初始化即可。
实现结果：
范例输入：
6 9
0 1 2 3 4 5
0 1 6
0 2 1
0 3 5
1 2 5
1 4 3
2 3 5
2 4 6
2 5 4
3 5 2
代码：
void prim(AMGraph G,int v,int &sum) //prim创建最小生成树
{
int lowcost[MaxSize],vest[MaxSize],v1;
int i,j,k,min;
v1 = v;
for(i=0;i<G.n;i++)
{
lowcost[i] = G.arcs[v1][i]; //lowcost保存与v连接的各顶点的权值，与v未连接的置为INF
vest[i] = 0; //vest数组初始化表示当前集合无顶点
}
vest[v] = 1; //将v顶点加入集合
sum = 0;
for(i=0;i<G.n-1;i++) //对剩下的n-1个顶点进行访问
{
min = INF;
for(j=0;j<G.n;j++) //选出与v连接的权值最小的顶点
{
if(vest[j]==0&&lowcost[j]<min)
{
min = lowcost[j];
k = j;
}
}
vest[k] = 1;
v1 = k;
sum+=min;
for(j=0;j<G.n;j++) //更新lowcost数组
{
if(vest[j]==0&&G.arcs[v1][j]<lowcost[j]) //生成树（树这一整体）到剩余各顶点最短边的权值
lowcost[j] = G.arcs[v1][j];
}
}
}
完整代码：
#include <stdio.h>
#include <stdlib.h>
#define MaxVertices 100
#define MaxSize 20
#define INF 100
typedef struct
{
int vexs[MaxVertices];
int arcs[MaxVertices][MaxVertices];
int n,e;
}AMGraph;
void CreateGraph(AMGraph &G) //生成邻接矩阵
{
int i,j,w,vi,vj;
printf("请输入总顶点数和边数:\n");
scanf("%d %d",&G.n,&G.e);
printf("创建顶点表:\n");
for(i=0;i<G.n;i++)
{
scanf("%d",&G.vexs[i]);
}
for(i=0;i<G.n;i++)
{
for(j=0;j<G.n;j++)
{
G.arcs[i][j] = INF;
}
}
printf("创建边表:\n");
for(i=0;i<G.e;i++)
{
scanf("%d %d %d",&vi,&vj,&w);
G.arcs[vi][vj] = w;
G.arcs[vj][vi] = w;
}
}
void prim(AMGraph G,int v,int &sum) //prim创建最小生成树
{
int lowcost[MaxSize],vest[MaxSize],v1;
int i,j,k,min;
v1 = v;
for(i=0;i<G.n;i++)
{
lowcost[i] = G.arcs[v1][i]; //lowcost保存与v连接的各顶点的权值，与v未连接的置为INF
vest[i] = 0; //vest数组初始化表示当前集合无顶点
}
vest[v] = 1; //将v顶点加入集合
sum = 0;
for(i=0;i<G.n-1;i++) //对剩下的n-1个顶点进行访问
{
min = INF;
for(j=0;j<G.n;j++) //选出与v连接的权值最小的顶点
{
if(vest[j]==0&&lowcost[j]<min)
{
min = lowcost[j];
k = j;
}
}
vest[k] = 1;
v1 = k;
sum+=min;
for(j=0;j<G.n;j++) //更新lowcost数组
{
if(vest[j]==0&&G.arcs[v1][j]<lowcost[j]) //生成树（树这一整体）到剩余各顶点最短边的权值
lowcost[j] = G.arcs[v1][j];
}
}
}
int main()
{
int sum;
AMGraph G;
CreateGraph(G);
prim(G,0,sum);
printf("最小生成树权值和为:%d\n",sum);
}
kruskal（克鲁斯卡尔）算法
时间复杂度：O（NlogN）（N为边数）
kruskal算法又称“加边法”，用于边数较少的稀疏图
方法：每次找图中权值最小的边，将边连接的两个顶点加入最小生成树集合中
注意：相同权值任选其中一个即可，但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树：
1.初始化：
构建边的结构体，包括起始顶点、终止顶点，边的权值
借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合
运行结果：
范例输入：
6 9
1 2 3 4 5 6
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
int getRoot(int a) //在并查集中查找根节点
{
while(a != v[a])
a = v[a];
return a;
}
void kruskal(AdjList *G,int &sum,Road road[])
{
int i;
int N,E,a,b;
N = G->n;
E = G->e;
sum = 0;
for(i=0;i<N;i++) v[i] = i; //并查集数组初始化为顶点序号
sort(road,E);
for(i=0;i<E;i++)
{
a = getRoot(road[i].v);
b = getRoot(road[i].x);
if(a!=b)
{
v[a] = b;
sum+=road[i].w;
}
}
}
完整代码：
#include <stdio.h>
#include <stdlib.h>
#define MaxVertices 100
#define MaxSize 20
typedef struct node
{
int adjvex;
node* next;
}ArcNode;
typedef struct
{
int data;
ArcNode* first;
}VerNode;
typedef struct
{
VerNode adjList[MaxVertices];
int n,e;
}AdjList;
typedef struct
{
int v,x; //v,x为一条边所连的两个顶点
int w; //边的权值
}Road;
Road road[MaxSize];
int v[MaxSize];
void CreateGraph(AdjList *G)
{
int i,a,b,w;
ArcNode *s;
printf("请输入总顶点数和边数:\n");
scanf("%d %d",&G->n,&G->e);
printf("创建顶点表:\n");
for(i=0;i<G->n;i++)
{
scanf("%d",&G->adjList[i].data);
G->adjList[i].first = NULL;
}
printf("创建边表:\n");
for(i=0;i<G->e;i++)
{
scanf("%d %d %d",&a,&b,&w);
road[i].v = a;
road[i].x = b;
road[i].w = w;
s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = b;
s->next = G->adjList[a].first;
G->adjList[a].first = s;
s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = a;
s->next = G->adjList[b].first;
G->adjList[b].first = s;
}
}
void sort(Road road[],int E) //权值排序，采用冒泡排序
{
int i,j,temp,temp1,temp2;
for(i=0;i<E;i++)
{
for(j=0;j<E-i-1;j++)
{
if(road[j].w > road[j+1].w)
{
temp1 = road[j+1].v;
temp2 = road[j+1].x;
temp = road[j+1].w;
road[j+1].v = road[j].v;
road[j].v = temp1;
road[j+1].x = road[j].x;
road[j].x = temp2;
road[j+1].w = road[j].w;
road[j].w = temp;
}
}
}
}
int getRoot(int a) //在并查集中查找根节点
{
while(a != v[a])
a = v[a];
return a;
}
void kruskal(AdjList *G,int &sum,Road road[])
{
int i;
int N,E,a,b;
N = G->n;
E = G->e;
sum = 0;
for(i=0;i<N;i++) v[i] = i; //并查集数组初始化为顶点序号
sort(road,E);
for(i=0;i<E;i++)
{
a = getRoot(road[i].v);
b = getRoot(road[i].x);
if(a!=b)
{
v[a] = b;
sum+=road[i].w;
}
}
}
int main()
{
int sum;
AdjList *G = (AdjList*)malloc(sizeof(AdjList));
CreateGraph(G);
kruskal(G,sum,road);
printf("最小生成树:%d\n",sum);
}