一、基础知识
二、代码要求
邻接矩阵、邻接表中任选一种作为图的存储结构，采用克鲁斯卡尔（Kruskal）算法，实现按权值递增的次序选择合适的边来构造最小生成树（2学时）
三、算法思路分析
Kruskal算法思路 输入： 图G 输出： 图G的最小生成树 具体流程： (1)将图G看做一个森林，每个顶点为一棵独立的树 (2)将所有的边加入集合S，即一开始S = E (3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E’ (4)重复(3)直到所有点属于同一棵树，边集E’就是一棵最小生成树
四、算法反思
五、代码实现
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
int vex1;//边的起始顶点
int vex2;//边的终止顶点
int weight;//边的权值
}KEdge;
typedef struct
{
VertexType vexs[MaxVertexNum];//顶点表
EdgeType edges[MaxVertexNum][MaxVertexNum];//边表，邻接矩阵
int n,e;//顶点数和边数
}MGraph;//以邻接矩阵存储图类型
int visited[MaxVertexNum];
/*int CreateMGraph(MGraph *G,KEdge E[])//建立图的邻接矩阵
{
int i, j, k;
printf("请输入顶点数和边数（输入格式为：顶点数，边数）：\n");
scanf("%d,%d",&(G->n),&(G->e));//输入顶点数和边数 /*这G->n不加括号括起来有无影响？*/
/* printf("请输入顶点信息（输入格式为：<回车>顶点号）：\n");
for(i=0; i<G->n; i++)
{
scanf("\n%c",&(G->vexs[i]));
}
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
G->edges[i][j]=0;//初始化邻接矩阵
}
}
printf("请输入每条边对应的两个顶点的序号（输入格式为：i,j）：\n");
for(k=0; k<G->e; k++)
{
scanf("%d,%d",&i,&j);
G->edges[i][j]=1;//若此处加入G->deges[j][i]=1,则为无向图的邻接矩阵存储建立
G->edges[j][i]=1;
}
}*/
int CreateMGraph(MGraph *G, KEdge E[])
{
int i, j, k;
printf("请输入顶点数和边数（输入格式为：顶点数，边数）：\n");
scanf("%d,%d",&(G->n),&(G->e));//输入顶点数和边数 /*这G->n不加括号括起来有无影响？*/
printf("请输入顶点信息（输入格式为：<回车>顶点号）：\n");
for(i=0; i<G->n; i++)
{
scanf("\n%c",&(G->vexs[i]));
}
for(i=0; i<G->n; i++)
{
for(j=0; j<G->n; j++)
{
G->edges[i][j]=0;//初始化邻接矩阵
}
}
printf("请输入每条边对应的两个顶点的序号和对应的权值（输入格式为：i,j,weight）：\n");
for(k=0; k<G->e; k++)
{
scanf("%d,%d,%d",&(E[k].vex1),&(E[k].vex2),&E[k].weight);
i=E[k].vex1; j=E[k].vex2;
G->edges[i][j]=1;//若此处加入G->deges[j][i]=1,则为无向图的邻接矩阵存储建立
G->edges[j][i]=1;
}
}
/*创建由小到大的边数组算法*/
void sort(KEdge E[], int n, int e)
{
int i,j;
for(i=0; i<e-1; i++)
{
for(j=i; j<e-1; j++)
{
if(E[j].weight>E[j+1].weight)
{
KEdge temp=E[j];
E[j]=E[j+1];
E[j+1]=temp;
}
}
}
}
void Kruskal(KEdge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MaxVertexNum];//用于记录顶点是否属于同一集合的辅助数组
for(i=0; i<n; i++)//初始化辅助数组
vset[i]=i;
k=0; //表示当前中构造最小生成树的第k条边，初值为0
j=0; //E中边的下标，初值为0
for(j=0; j<e; j++)
{
m1=E[j].vex1;
m2=E[j].vex2; //取一条边的两个邻接点
sn1=vset[m1]; //分别得到两个顶点所属的集合编号
sn2=vset[m2];
if(sn1!=sn2) //两个顶点不属于同一棵树，则添加到边表里
{
printf("(%d,%d):%d\n",m1,m2,E[j].weight);
k++; //生成边数增加1
if(k==n-1)
break;
for(i=0; i<n; i++) //修改集合边数相同
if(vset[i]==sn1)
vset[i]=sn2;
}
}
}
int main()
{
MGraph x;
// int *e1,*n1;
KEdge A[MaxVertexNum];
CreateMGraph(&x,A);
sort(A,(x.n),(x.e));
Kruskal(A,(x.n),(x.e));
return 0;
}
六、代码反思
1、书上的创建邻接矩阵的创建函数没有返回值，导致e，n创建完就释放掉了， 没有供下边的克鲁斯卡尔算法使用 改正思路： 2、一开始没写排序并把边由小到大放入辅助数组 3、一开始套用图的邻接矩阵书上代码过于僵硬，套用了还需要把边涉及的顶点的权值 通过某种方式传到辅助数组E[]里边，所以直接改写了创建的边表矩阵，直接把 图的边涉及到的顶点和边对应的权值写进辅助数组E里边， 由于题目问题，其他地方不受影响
