数据结构（C实现）------- 最小生成树之Kruskal算法
程序员文章站
2022-06-02 22:28:47
算法描述：
kruskal算法是按权值递增的次序来构造最小生成树的方法。
假设g(v,e)最一个具有n个顶点的连通网，顶点集v={v1,v2,....,vn}。设所求的最...
算法描述：
kruskal算法是按权值递增的次序来构造最小生成树的方法。
假设g(v,e)最一个具有n个顶点的连通网，顶点集v={v1,v2,....,vn}。设所求的最小生成树为t={u,te},其中u是t的顶点集，te是ｔ的边集，u和te的初始值为空集。kruskal算法的基本思想如下：将最小生成树初始化为t=(v,te),仅包含 g的全部顶点，不包含g的任一条边，此时，t由n 个连通分量组成，每个分量只有一个顶点；将图中g中的边按权值从小到大排序，选择代价最小了一条边，若该边所依附的顶点分属于t中的不同的连通分量，则将此边加入到te中，否则，舍弃此边而选择下一条代价最小的边。依次类推，直至te中包含n-1条边（即t中所有的顶点都在同一连通分量上）为止。
算法实现：
设置一个edge数组存储连通网中所有的边，为了便于选择当前权值最小的边，需要将edge中的边按权值从小到大进行排列。
而在连通分量的合并上，可以采用集合的合并方法，对于有n个顶点的连通网，设置一个数组father[0...n-1]，其初始值为-1,表示n个顶点在不同的连通分量上。然后，依次扫描edge数组中的每一条边，并查找相关联的两个顶点所属的连通分量，假设vf1和vf2为两个顶点的所在树的根节点的序号，若vf1不等于vf2，则表明这条边的两个顶点不属于同一个连通分量，则将这条边作为最小生成树的边并输出，然后合并它们所属的两个连通分量。
算法代码：
int findfather(int father[],int v){
int t = v;
while(father[t] != -1)
t = father[t];
return t;
}
/* *
*kruskal算法求最小生成树
* */
void kruskal_mg(mgraph mg,edge edge[]){
int father[max_vex_num];
int i,count,vf1,vf2;
// 初始化father数组
for(i = 0;i < max_vex_num;i++){
father[i] = -1;
}
i = 0;
count = 0; // 统计加入最小生树中的边数
// 遍历任意两个结点之间的边
while(i < mg.arcnum && count < mg.arcnum){
vf1 = findfather(father,edge[i].start);
vf2 = findfather(father,edge[i].end);
// 如果这两个节点不属于同一个连通分量，则加入同一个连通分量
if (vf1 != vf2){
father[vf2] = vf1;
count++;
printf(%c,%c,%d
,mg.vexs[edge[i].start],mg.vexs[edge[i].end],edge[i].cost);
}
i++;
}
}
其中，函数findfather的作用就是找指定节点所属的连通分量，在这里也就是找其所在树的根节点在数组中的序号。
算法说明：
对于带权图g中e条边的权值的排序方法可以有多种，这里采用的是最简单的冒泡排序法，时间复杂度为o(n^2)。而判断新选择的边的两个顶点是否在同一个连通分量中，这个问题等价于一个在最多有n 个顶点的生成树中遍历寻找新选择的边的两个节点是否存在的问题，所以此算法的复杂度最坏情况下是o(n^2)。
注意：一般来讲，prim算法的时间复杂度为o(n^2),因此适合于稠密图，而kruskal算法需要对e条边进行排序，最快的情况下复杂度为o(elog2e)，因此对于稀疏图，采用kruskal算法比较合适。
完整代码：
/*
* =====================================================================================
*
* filename: kruskal.c
*
* description: 最小生成树之kruskal算法
*
* version: 1.0
* created: 2015年05月06日 21时25分12秒
* revision: none
* compiler: gcc
*
* author: jesson20121020 (), 997287955@qq.com
* organization:
*
* =====================================================================================
*/
#include
#include
#define max_vex_num 50
#define max_arc_num 100
#define un_reach 1000
typedef char vertextype;
typedef enum {
dg, udg
} graphtype;
typedef struct {
vertextype vexs[max_vex_num];
int arcs[max_vex_num][max_vex_num];
int vexnum, arcnum;
graphtype type;
} mgraph;
/**
* 根据名称得到指定顶点在顶点集合中的下标
* vex 顶点
* return 如果找到，则返回下标，否则，返回０
*/
int getindexofvexs(char vex, mgraph *mg) {
int i;
for (i = 1; i <= mg->vexnum; i++) {
if (mg->vexs[i] == vex) {
return i;
}
}
return 0;
}
/**
* 创建邻接矩阵
*/
void create_mg(mgraph *mg) {
int i, j, k,weight;
int v1, v2, type;
char c1, c2;
printf(please input graph type dg(0) or udg(1) :);
scanf(%d, &type);
if (type == 0)
mg->type = dg;
else if (type == 1)
mg->type = udg;
else {
printf(please input correct graph type dg(0) or udg(1)!);
return;
}
printf(please input vexmun : );
scanf(%d, &mg->vexnum);
printf(please input arcnum : );
scanf(%d, &mg->arcnum);
getchar();
for (i = 1; i <= mg->vexnum; i++) {
printf(please input %dth vex(char):, i);
scanf(%c, &mg->vexs[i]);
getchar();
}
//初始化邻接矩阵
for (i = 1; i <= mg->vexnum; i++) {
for (j = 1; j <= mg->vexnum; j++) {
if(i == j)
mg->arcs[i][j] = 0;
else
mg->arcs[i][j] = un_reach;
}
}
//输入边的信息，建立邻接矩阵
for (k = 1; k <= mg->arcnum; k++) {
printf(please input %dth arc v1(char) v2(char) weight(int): , k);
scanf(%c %c %d, &c1, &c2,&weight);
v1 = getindexofvexs(c1, mg);
v2 = getindexofvexs(c2, mg);
if (mg->type == 1)
mg->arcs[v1][v2] = mg->arcs[v2][v1] = weight;
else
mg->arcs[v1][v2] = weight;
getchar();
}
}
/**
* 打印邻接矩阵和顶点信息
*/
void print_mg(mgraph mg) {
int i, j;
if(mg.type == dg){
printf(graph type: direct graph
);
}
else{
printf(graph type: undirect graph
);
}
printf(graph vertex number: %d
,mg.vexnum);
printf(graph arc number: %d
,mg.arcnum);
printf(vertex set:
);
for (i = 1; i <= mg.vexnum; i++)
printf(%c , mg.vexs[i]);
printf(
adjacency matrix:
);
for (i = 1; i <= mg.vexnum; i++) {
j = 1;
for (; j < mg.vexnum; j++) {
printf(%d , mg.arcs[i][j]);
}
printf(%d
, mg.arcs[i][j]);
}
}
// 定义边结构体
typedef struct{
int start;
int end;
int cost;
}edge;
/* *
* 由邻接矩阵得到边的信息
*
* */
void init_edge(mgraph mg,edge edge[]){
int i,j;
int count = 0;
if(mg.type == 0){
for(i = 1; i <= mg.vexnum;i++){
for (j = 1;j <= mg.vexnum;j++){
if(mg.arcs[i][j] != 0 && mg.arcs[i][j] != un_reach){
edge[count].start = i;
edge[count].end = j;
edge[count].cost = mg.arcs[i][j];
count++;
}
}
}
}
else{
for(i = 1; i <= mg.vexnum;i++){
for (j = i;j <= mg.vexnum;j++){
if(mg.arcs[i][j] != 0 && mg.arcs[i][j] != un_reach){
edge[count].start = i;
edge[count].end = j;
edge[count].cost = mg.arcs[i][j];
count++;
}
}
}
}
}
/* *
* 将边按权值从大到小排序
* */
void sort_edge(edge edge[],int arcnum){
int i,j;
edge temp;
for(i = 0; i < arcnum - 1;i++){
for (j = i+1;j < arcnum;j++){
if(edge[i].cost > edge[j].cost){
temp = edge[i];
edge[i] = edge[j];
edge[j] = temp;
}
}
}
}
/* *
* 输出边的信息
* */
void print_edge(edge edge[],int arcnum){
int i = 0;
while(i < arcnum){
printf(%d,%d,%d
,edge[i].start,edge[i].end,edge[i].cost);
i++;
}
}
/**
* 找出指定节点的所属的连通分量，这里是找出其根节点在father数组中下标。
**/ int findfather(int father[],int v){
int t = v;
while(father[t] != -1)
t = father[t];
return t;
}
/* *
*kruskal算法求最小生成树
* */
void kruskal_mg(mgraph mg,edge edge[]){
int father[max_vex_num];
int i,count,vf1,vf2;
// 初始化father数组
for(i = 0;i < max_vex_num;i++){
father[i] = -1;
}
i = 0;
count = 0; // 统计加入最小生树中的边数
// 遍历任意两个结点之间的边
while(i < mg.arcnum && count < mg.arcnum){
vf1 = findfather(father,edge[i].start);
vf2 = findfather(father,edge[i].end);
// 如果这两个节点不属于同一个连通分量，则加入同一个连通分量
if (vf1 != vf2){
father[vf2] = vf1;
count++;
printf(%c,%c,%d
,mg.vexs[edge[i].start],mg.vexs[edge[i].end],edge[i].cost);
}
i++;
}
}
/**
* 主函数
*/
int main(void) {
mgraph mg;
edge edge[max_arc_num];
create_mg(&mg);
print_mg(mg);
init_edge(mg,edge);
sort_edge(edge,mg.arcnum);
printf(the result of kruskal:
);
kruskal_mg(mg,edge);
return exit_success;
}
运行演示：
jesson@jesson-k43sv:~/develop/worksapce/c_learning/最小生成树$ gcc -o kruskal kruskal.c jesson@jesson-k43sv:~/develop/worksapce/c_learning/最小生成树$ ./kruskal please input graph type dg(0) or udg(1) :0 please input vexmun : 4 please input arcnum : 5 please input 1th vex(char):a please input 2th vex(char):b please input 3th vex(char):c please input 4th vex(char):d please input 1th arc v1(char) v2(char) weight(int): a b 1 please input 2th arc v1(char) v2(char) weight(int): a c 3 please input 3th arc v1(char) v2(char) weight(int): a d 4 please input 4th arc v1(char) v2(char) weight(int): b c 2 please input 5th arc v1(char) v2(char) weight(int): c d 3 graph type: direct graph graph vertex number: 4 graph arc number: 5 vertex set: a b c d adjacency matrix: 0 1 3 4 1000 0 2 1000 1000 1000 0 3 1000 1000 1000 0 the result of kruskal: a,b,1 b,c,2 c,d,3