求最小生成树——kruskal算法（邻接矩阵）
#include<stdio.h>
#include<stdlib.h>
#define MAXLEAF 100
#define INF 100000
#define EDGENUMBER MAXLEAF*MAXLEAF/2
typedef int EdgeType; /*边的类型*/
typedef int VertexType; /*结点的类型*/
typedef struct{ /*邻接矩阵*/
EdgeType val[MAXLEAF][MAXLEAF];
VertexType ves[MAXLEAF];
int v;
int e;
}MGraph;
typedef struct{ /*存放边和边所关联的两个结点的结构体*/
int vex1,vex2; /*vex1小于vex2,分别表示边所在的两个结点的序号*/
int w;
}kedge; /*存放含权值的边的集合*/
void creat_MGraph(MGraph *M){ /*创建邻接矩阵*/
int i,j,k;
int w;
//printf("请输入图的顶点个数及边数：\n");
scanf("%d%d",&(M->v),&(M->e));
//printf("请依次填充顶点信息：\n");
for(i=0;i<M->v;i++)
scanf("%d",&(M->ves[i]));
for(i=0;i<M->v;i++)
for(j=0;j<M->v;j++)
if(i==j) M->val[i][j]=0; /*初始化邻接矩阵*/
else M->val[i][j]=INF; /*将关联的结点之间的权值更新为INF(表示无穷)*/
//printf("请依次输入图的边两个顶点顶点的权值：(格式：i,j,w)\n");
for(k=0;k<M->e;k++)
{
scanf("%d%d%d",&i,&j,&w);
M->val[i-1][j-1]=w;
M->val[j-1][i-1]=w;
}
}
VertexType kruskal(MGraph M){ /*克鲁斯卡尔算法-邻接矩阵*/
int tag[MAXLEAF];
kedge Ke[EDGENUMBER]; /*用来存放读取到的所有边*/
int i,j;
VertexType length=0;
int n=0; //n表示ke[]中的边数
for(i=0;i<M.v;i++) tag[i]=i; /*初始化tag标签数组*/
for(i=0;i<M.v;i++)
for(j=i+1;j<M.v;j++)
if(M.val[i][j]!=INF){ /*导入边表*/
Ke[n].vex1=i;
Ke[n].vex2=j;
Ke[n++].w=M.val[i][j];
}
kedge temp;
for(i=0;i<n-1;i++) /*冒泡将边的集合按权值递增排序*/
for(j=0;j<n-i-1;j++)
if(Ke[j].w>Ke[j+1].w){
temp=Ke[j+1];
Ke[j+1]=Ke[j];
Ke[j]=temp;
}
for(i=0;i<n;i++){ /*选则最短边*/
int first,second;
first = tag[Ke[i].vex1]; /*first表示当前边的第一个结点的标记集合*/
second = tag[Ke[i].vex2]; /*second表示当前边的第二个结点的标记集合*/
if(first!=second){
length+=Ke[i].w; /*计算最小生成树的总权值*/
printf("%d->%d: %d\n",Ke[i].vex1,Ke[i].vex2,Ke[i].w);
tag[Ke[i].vex2]=first; /*将该边纳入集合*/
for(j=0;j<M.v;j++){ /*两个集合统一编号*/
if(second==tag[j])
tag[j]=first;
}
}
}
return length;
}
int main(){
MGraph M;
int len;
creat_MGraph(&M);
printf("最小生成树：\n");
len=kruskal(M);
printf("最小成本：%d",len);
return 0;
}
/*
输入格式
7 10
1 2 3 4 5 6 7
1 3 60
1 2 50
3 7 45
2 5 40
5 6 50
2 4 65
3 4 52
4 7 42
4 5 50
4 6 30
*/