- 创建边集图（CreateEdgeGraph）
- 打印图（print）
- 排序函数（sort）
- 顶点下标查找函数（LocateVex）
- 查找双亲函数（FindRoot）
- 克鲁斯卡尔算法（MiniSpanTree_Kruskal）
克鲁斯卡尔算法
- 简单的来说就是：每次选取最短边，但不能构成回路。
克鲁斯卡尔算法的关键
1. 用哪一种方式存储图才合适？
- 如果用邻接矩阵和邻接表，每次寻找最短边都要搜索所有边，故邻接矩阵和邻接表均不合适！
- 改进图的存储：边集数组。
- EdgeGraph中包含了两个数组和顶点数、边数。两个数组分别是顶点数组Vertex[ ]和边集数组edge[ ]，其中边集数组edge是一个结构体数组，每一个单元包含起点、终点、权值。
typedef struct
{
VertexType begin;//起点
VertexType end;//终点
int weight;
}Edge;//边集数组edge[]的单元
typedef struct
{
VertexType Vertex[VertexMax];//顶点数组
Edge edge[VertexMax];//边集数组
int vexnum;//顶点数
int edgenum;//边数
}EdgeGraph;
2. 如何选取最短边？
- 排序。排序是克鲁斯卡尔算法的关键，是整个算法时间花费最多的部分，故排序算法决定了克鲁斯卡尔算法的时间复杂度。若采用插入排序，时间复杂度为O(e2) ，若采用堆排序或者快速排序，那么时间复杂度为O(elog2e) [注：e为边数]
- 此处用的是简单选择排序：
void sort(EdgeGraph *E)
{
int i,j;
Edge temp;
for(i=0;i<E->edgenum-1;i++)
{
for(j=i+1;j<E->edgenum;j++)
{
if(E->edge[i].weight>E->edge[j].weight)
{
temp=E->edge[i];
E->edge[i]=E->edge[j];
E->edge[j]=temp;
}
}
}
}
- 排序结果：
3. 如何确定当前所选最短边是否会构成回路？
- 考察两个顶点之间是否会构成回路，只需要看两个顶点所属的树是否有相同的根节点。
int FindRoot(int t,int parent[])//t接收到是结点在Vertex数组中的下标
{
while(parent[t]>-1)//parent=-1表示没有双亲，即没有根节点
{
t=parent[t];//逐代查找根节点
}
return t;//将找到的根节点返回，若没有根节点返回自身
}
4. 克鲁斯卡尔算法代码：
void MiniSpanTree_Kruskal(EdgeGraph *E)
{
int i;
int num;//生成边计数器，当num=顶点数-1 就代表最小生成树生成完毕
int root1,root2;
int LocVex1,LocVex2;
int parent[VertexMax];//用于查找顶点的双亲，判断两个顶点间是否有共同的双亲，来判断生成树是否会成环
//1.按权值从小到大排序
sort(E);
print(E);
//2.初始化parent数组
for(i=0;i<E->vexnum;i++)
{
parent[i]=-1;
}
printf("\n 最小生成树(Kruskal):\n\n");
//3.
for(num=0,i=0;i<E->edgenum;i++)
{
LocVex1=LocateVex(E,E->edge[i].begin);
LocVex2=LocateVex(E,E->edge[i].end);
root1=FindRoot(LocVex1,parent);
root2=FindRoot(LocVex2,parent);
if(root1!=root2)//若不会成环，则在最小生成树中构建此边
{
printf("\t\t%c-%c w=%d\n",E->edge[i].begin,E->edge[i].end,E->edge[i].weight);//输出此边
parent[root2]=root1;//合并生成树
num++;
if(num==E->vexnum-1)//若num=顶点数-1，代表树生成完毕，提前返回
{
return;
}
}
}
}
- 需要注意的是我这里采用的顶点元素是字符型，所以在找祖先（FindRoot）的时候需要将顶点元素对应Vertex数组中的下标传入，故需要用LocateVex函数获取下标[见上代码第22-25行]
- 此代码还加入了生成边计数器num，统计当前最小生成树的边数，当num达到顶点数-1（n-1）的时候，可以提前返回结束，省去后面可能会有多余的步骤。[见上代码第34-37行]
完整源代码
#include <stdio.h>
#include <stdlib.h>
#define VertexMax 20 //最大顶点数为20
typedef char VertexType;
typedef struct
{
VertexType begin;
VertexType end;
int weight;
}Edge;//边集数组edge[]的单元
typedef struct
{
VertexType Vertex[VertexMax];//顶点数组
Edge edge[VertexMax];//边集数组
int vexnum;//顶点数
int edgenum;//边数
}EdgeGraph;
void CreateEdgeGraph(EdgeGraph *E)
{
int i;
printf("请输入顶点数和边数:\n");
printf("顶点数 n=");
scanf("%d",&E->vexnum);
printf("边 数 e=");
scanf("%d",&E->edgenum);
printf("\n");
//printf("\n");
printf("输入顶点(无需空格隔开):");
scanf("%s",E->Vertex);
printf("\n\n");
printf("输入边信息和权值(如：AB,15):\n");
for(i=0;i<E->edgenum;i++)
{
printf("请输入第%d边的信息:",i+1);
scanf(" %c%c,%d",&E->edge[i].begin,&E->edge[i].end,&E->edge[i].weight);
}
}
void print(EdgeGraph *E)
{
int i;
printf("\n-----------------------------------\n");
printf(" 顶点数组Vertex:");
for(i=0;i<E->vexnum;i++)
{
printf("%c ",E->Vertex[i]);
}
printf("\n\n");
printf(" 边集数组edge:\n\n");
printf("\t\tBegin End Weight\n");
for(i=0;i<E->edgenum;i++)
{
printf("\tedge[%d] %c %c %d\n",i,E->edge[i].begin,E->edge[i].end,E->edge[i].weight);
}
printf("\n-----------------------------------\n");
}
void sort(EdgeGraph *E)
{
int i,j;
Edge temp;
for(i=0;i<E->edgenum-1;i++)
{
for(j=i+1;j<E->edgenum;j++)
{
if(E->edge[i].weight>E->edge[j].weight)
{
temp=E->edge[i];
E->edge[i]=E->edge[j];
E->edge[j]=temp;
}
}
}
}
int LocateVex(EdgeGraph *E,VertexType v)//查找元素v在一维数组 Vertex[] 中的下标，并返回下标
{
int i;
for(i=0;i<E->vexnum;i++)
{
if(v==E->Vertex[i])
{
return i;
}
}
printf("No Such Vertex!\n");
return -1;
}
int FindRoot(int t,int parent[])//t接收到是结点在Vertex数组中的下标
{
while(parent[t]>-1)//parent=-1表示没有双亲，即没有根节点
{
t=parent[t];//逐代查找根节点
}
return t;//将找到的根节点返回，若没有根节点返回自身
}
void MiniSpanTree_Kruskal(EdgeGraph *E)
{
int i;
int num;//生成边计数器，当num=顶点数-1 就代表最小生成树生成完毕
int root1,root2;
int LocVex1,LocVex2;
int parent[VertexMax];//用于查找顶点的双亲，判断两个顶点间是否有共同的双亲，来判断生成树是否会成环
//1.按权值从小到大排序
sort(E);
print(E);
//2.初始化parent数组
for(i=0;i<E->vexnum;i++)
{
parent[i]=-1;
}
printf("\n 最小生成树(Kruskal):\n\n");
//3.
for(num=0,i=0;i<E->edgenum;i++)
{
LocVex1=LocateVex(E,E->edge[i].begin);
LocVex2=LocateVex(E,E->edge[i].end);
root1=FindRoot(LocVex1,parent);
root2=FindRoot(LocVex2,parent);
if(root1!=root2)//若不会成环，则在最小生成树中构建此边
{
printf("\t\t%c-%c w=%d\n",E->edge[i].begin,E->edge[i].end,E->edge[i].weight);//输出此边
parent[root2]=root1;//合并生成树
num++;
if(num==E->vexnum-1)//若num=顶点数-1，代表树生成完毕，提前返回
{
return;
}
}
}
}
int main()
{
EdgeGraph E;
CreateEdgeGraph(&E);
MiniSpanTree_Kruskal(&E);
return 0;
}
执行结果
克鲁斯卡尔算法的时间复杂度
- 上文已经提到，克鲁斯卡尔算法主要时间耗费在排序算法中，整个算法的时间复杂度取决于排序算法，若采用插入排序，时间复杂度为O(e2) ，若采用堆排序或者快速排序，那么时间复杂度为O(elog2e)，此处的e为边，那么也就是说，克鲁斯卡尔算法的时间复杂度与边数有关，故适用于稀疏图。
参考：
1.部分文图来自 懒猫老师
