数据结构（C）:最小生成树Prim算法和Kruscal算法
1.Prim算法（选点）
思想：①设置一个点集合V，表示最小生成树中已经确定的点的集合；设置一个边集合U,表示最小生成树中已经确定的边的集合；（U和V是对应起来的)，
②在V中点，和剩余点中找权值最小的边，将边并入U,对应的另一个端点并入V.(注意在找边的时候避免和原来的边产生环)
③重复步骤②，直到V中的顶点为所有的顶点，U中的边则为最小生成树上的边。
时间复杂度O(n^2),适用于点少的图
例如：下图
先找{1}和{2，3，4，5，6}中权最小的边为（1，3）
再找{1,3}和{2，4，5，6}中权最小的边为（3，6）
······
代码：
#include<stdio.h>
#define MAX_VERTEX_NUM 100
#define MAX 1e10
typedef struct{
int vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}MGraph;
struct{
int adjvex;
int lowcost;
}closedge[MAX_VERTEX_NUM];
bool inU[MAX_VERTEX_NUM]; //如果值为1表示vex【i】顶点在U中
int LocateVex(MGraph G,int v){//返回顶点在图中的位置
for(int i=0;i<G.vexnum;i++){
if(G.vexs[i]==v)return i;
}
}
void CreateUDN(MGraph &G){//构造无向网的邻接矩阵
int i,j,k,v1,v2,weight;
printf("分别输入顶点个数和边的个数：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("输入各个顶点:\n");
for(i=0;i<G.vexnum;i++)
scanf("%d",&G.vexs[i]);
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=MAX;//初始化图，如果两点不通则把值赋为MAX
printf("分别输入各条边的两个顶点和边的权值：\n");
for(k=0;k<G.arcnum;k++){
scanf("%d%d%d",&v1,&v2,&weight);
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j]=weight;
G.arcs[j][i]=weight;
}
}
int minmum(MGraph G){//返回low_cost最小的
int min_cost=MAX;
int temp;
for(int i=0;i<G.vexnum;i++)
if(closedge[i].lowcost<min_cost&&closedge[i].lowcost!=0&&inU[LocateVex(G,closedge[i].adjvex)]){
min_cost=closedge[i].lowcost;temp=i;
}
return temp;
}
void MiniSpanTree_PRIM(MGraph G,int u){//找到最小生成树的边并输出
int i,j,k;
k=LocateVex(G,u);
inU[k]=1;// 表示把vex[k]加入到U集合中
for(j=0;j<G.vexnum;j++)//初始化，即有一个顶点时U集 到V-U集的最小权值
if(j!=k){
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j];
}
closedge[k].lowcost=0;
printf("最小生成树的边为：\n");
for(i=1;i<G.vexnum;i++){//U集总共还要加入vexnum-1个顶点
k=minmum(G);//当前U到 V-U集最小的一个权值为closedge[k].lowcost
inU[k]=1; //将vex[k]加入U集合
printf("%d %d\n",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++){//当有新的顶点加入U集时，每个顶点到V-U集的lowcost都要重新赋值
if(G.arcs[k][j]<closedge[j].lowcost)//如果新的顶点到j的权值小与未加入新顶点之前的lowcost，则重新赋值
{closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j];}
}
}
}
int main(){
MGraph G;
CreateUDN(G);
int u;//最小生成树的起点为u
printf("输入生成树的出发点：\n");
scanf("%d",&u);
MiniSpanTree_PRIM(G,u);
return 0;
}
2.Kruskal（选边）
思想：
从原图中依次选择权值最小且不与已选的边构成环的边，直到所有顶点都连通
时间复杂度：O( e * loge )
适合于求边稀疏的网的最小生成树
代码：
/* 最小生成树的Kruskal算法 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 20
typedef char VertexType;
typedef struct Graph { //定义图的邻接矩阵表示法结构
VertexType ver[MaxSize+1];
int edg[MaxSize][MaxSize];
}Graph;
typedef struct gEdge { //定义一个边集结构，用来存储图的所有边信息
int begin;
int end;
int weight;
}gEdge;
void CreateGraph( Graph *g ) //邻接矩阵法图的生成函数
{
int i = 0;
int j = 0;
int VertexNum;
VertexType Ver;
printf("请输入图的顶点:\n");
while( '\n' != (Ver=getchar()) ) {
g->ver[i++] = Ver;
}
g->ver[i] = '\0';
VertexNum = strlen(g->ver);
printf("请输入相应的的邻接矩阵:\n");
for( i=0; i<VertexNum; i++ )
for( j=0; j<VertexNum; j++ )
scanf("%d", &g->edg[i][j]);
}
void PrintGraph( Graph g ) //打印图的结点标识符和邻接矩阵
{
int i, j;
int VertexNum = strlen(g.ver);
printf("图的顶点为:\n");
for( i=0; i<VertexNum; i++ )
printf("%c ", g.ver[i]);
printf("\n");
printf("图的邻接矩阵为:\n");
for( i=0; i<VertexNum; i++ ) {
for( j=0; j<VertexNum; j++ )
printf("%d ", g.edg[i][j]);
printf("\n");
}
}
int CalVerNum( Graph g ) //求图的顶点数
{
return strlen(g.ver);
}
int CalEdgNum( Graph g ) //获取图的边数
{
Graph p = g;
int count = 0;
int VertexNum = CalVerNum( p );
for( int i=0; i<VertexNum; i++ )
for( int j=i; j<VertexNum; j++ ) //邻接矩阵对称，计算上三角元素和即可
if( 0 != p.edg[i][j] )
count++;
return count;
}
gEdge *CreateEdges( Graph g ) //生成图的排序过的边集数组
{
int i, j;
int k = 0;
int EdgNum = CalEdgNum( g );
int VertexNum = CalVerNum( g );
gEdge temp;
gEdge *p = (gEdge *)malloc(sizeof(gEdge)*EdgNum);
for( i=0; i<VertexNum; i++ ) //边集数组初始化,同样只考虑上三角矩阵
for( j=i; j<VertexNum; j++ )
if( 0 != g.edg[i][j] ) {
p[k].begin = i;
p[k].end = j;
p[k].weight = g.edg[i][j];
k++;
}
for( i=0; i<EdgNum-1; i++ ) //对边集数组进行选择排序
for( j=i+1; j<EdgNum; j++ )
if( p[i].weight > p[j].weight ) {
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
return p;
}
//Kruskal算法生成MST
void Kruskal( Graph g )
{
int VertexNum = CalVerNum( g );
int EdgNum = CalEdgNum( g );
gEdge *p = CreateEdges( g );
int *index = (int *)malloc(sizeof(int)*VertexNum);
//index数组，其元素为连通分量的编号，index[i] = index[j] 表示编号为i 和 j的顶点在同一个连通分量中，反之则不在同一个连通分量
int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum-1); //MSTEdge数组，用来存储已确定的MST的边的编号，共VertexNum-1条边
int k= 0;
int WeightSum = 0;
int IndexBegin, IndexEnd;
for(int i=0; i<VertexNum; i++ ) //初始化所有index = -1
index[i] = -1;
for( i=0; i<VertexNum-1; i++ ) {
for(int j=0; j<EdgNum; j++ ) {
if( !(index[p[j].begin]>=0 && index[p[j].end]>=0 && index[p[j].begin]==index[p[j].end]) ) { //找到当前还没加入到同一个连通分量且权值最下的边
MSTEdge[i] = j; //将其加入到MST中去
if( (-1 == index[p[j].begin]) && (-1 == index[p[j].end]) ) //该边的两个顶点都没加入过任何一个连通分量
index[p[j].begin] = index[p[j].end] = i;
else if( (-1 == index[p[j].begin]) && (index[p[j].end] >= 0) ) { //该边的尾end已在一个连通分量，头begin未加入过任何连通分量
index[p[j].begin] = i;
IndexEnd = index[p[j].end];
for(int n=0; n<VertexNum; n++ )
if( index[n] == IndexEnd )
index[n] = i;
}
else if( (-1 == index[p[j].end]) && (index[p[j].begin] >= 0) ) { //该边的头begin已在一个连通分量，尾end未加入过任何连通分量
index[p[j].end] = i;
IndexBegin = index[p[j].begin];
for(int n=0; n<VertexNum; n++ )
if( index[n] == IndexBegin )
index[n] = i;
}
else {
IndexEnd = index[p[j].end];
IndexBegin = index[p[j].begin];
for(int n=0; n<VertexNum; n++ ) //该边的两个顶点都已经存在于两个不同的连通分量中
if( index[n] == IndexBegin || index[n] == IndexEnd )
index[n] = i; //将该连通分量编号全部修改为相同的值
}
break;
}
}
}
printf("MST的边为:\n"); //输出MST的边
for( i=0; i<VertexNum-1; i++ ) {
printf("%c--%c\n", g.ver [p[MSTEdge[i]].begin] , g.ver [p[MSTEdge[i]].end] );
WeightSum+=p[MSTEdge[i]].weight;
}
printf("MST的权值为:%d\n", WeightSum); //输出MST的权值
}
int main()
{
Graph g;
CreateGraph( &g );
PrintGraph( g );
Kruskal( g );
return 0;
}