KruskalAlgorithm.h
/*****************************************************************//**
* \file KruskalAlgorithm.h
* \brief Kruskal Algorithm克鲁斯卡尔算法
* IDE: VSCODE c11 https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md
* https://www.programiz.com/dsa/counting-sort
* https://www.geeksforgeeks.org/sorting-algorithms/
* \author geovindu,Geovin Du 涂聚文
* \date 2023-09-19
***********************************************************************/
#ifndef KRUSKALALGORITHM_H
#define KRUSKALALGORITHM_H
#include <stdio.h>
#include <stdlib.h>
#define MAX 30
typedef struct Kruskaledge {
int u, v, w;
} Kruskaledge;
typedef struct edge_list {
Kruskaledge data[MAX];
int n;
} edge_list;
/**
* @brief
*
*/
void KruskalAlgo(int KruskalGraph[MAX][MAX],edge_list elist,edge_list spanlist);
/**
* @brief
*
* @param belongs
* @param vertexno
* @return int
*/
int Kruskalfind(int belongs[], int vertexno);
/**
* @brief
*
* @param belongs
* @param c1
* @param c2
*/
void KruskalapplyUnion(int belongs[], int c1, int c2);
/**
* @brief
*
*/
void Kruskalsort(edge_list elist);
/**
* @brief
*
*/
void Kruskalprint(edge_list spanlist);
/**
* @brief
*
*/
struct edge {
//一条边有 2 个顶点
int initial;
int end;
//边的权值
int weight;
};
/**
* @brief 图中边的数量
*
*/
#define N 9 //
/**
* @brief 图中顶点的数量
*
*/
#define P 6
/**
* @brief 构建表示边的结构体
*
*/
/**
* @brief Kruskal Algorithm
* @param edge INT 数组
* @param edge 搜索的关键数字
*
* @return 返回
*/
void KruskalMinTree(struct edge edges[], struct edge minTree[]);
/**
* @brief
*
* @param minTree
*/
void KruskalDisplay(struct edge minTree[]);
/**
* @brief
*
* @param a
* @param b
* @return int
*/
int Kruskalcmp(const void* a, const void* b);
#endif //KRUSKALALGORITHM
KruskalAlgorithm.c
/**
* *****************************************************************************
* @file KruskalAlgorithm.c
* @brief Kruskal Algorithm kruskal算法（克鲁斯卡尔算法）
* @author (geovindu,Geovin Du,涂聚文) http://c.biancheng.net/algorithm/kruskal.html
* https://www.programiz.com/dsa/kruskal-algorithm
* https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
* @date 2023-09-26
* @copyright geovindu
* *****************************************************************************
*/
#include <stdio.h>
#include <stdlib.h>
#include "include/KruskalAlgorithm.h"
int n=6;
// Applying Krushkal Algo
/**
* @brief
*
* @param KruskalGraph
*/
void KruskalAlgo(int KruskalGraph[MAX][MAX],edge_list elist,edge_list spanlist) {
int belongs[MAX], i, j, cno1, cno2;
elist.n = 0;
for (i = 1; i < n; i++)
for (j = 0; j < i; j++) {
if (KruskalGraph[i][j] != 0) {
elist.data[elist.n].u = i;
elist.data[elist.n].v = j;
elist.data[elist.n].w = KruskalGraph[i][j];
elist.n++;
}
}
Kruskalsort(elist);
for (i = 0; i < n; i++)
belongs[i] = i;
spanlist.n = 0;
for (i = 0; i < elist.n; i++) {
cno1 = Kruskalfind(belongs, elist.data[i].u);
cno2 = Kruskalfind(belongs, elist.data[i].v);
if (cno1 != cno2) {
spanlist.data[spanlist.n] = elist.data[i];
spanlist.n = spanlist.n + 1;
KruskalapplyUnion(belongs, cno1, cno2);
}
}
Kruskalprint(spanlist);
}
int Kruskalfind(int belongs[], int vertexno) {
return (belongs[vertexno]);
}
void KruskalapplyUnion(int belongs[], int c1, int c2) {
int i;
for (i = 0; i < n; i++)
if (belongs[i] == c2)
belongs[i] = c1;
}
// Sorting algo
/**
* @brief
*
*/
void Kruskalsort(edge_list elist) {
int i, j;
Kruskaledge temp;
for (i = 1; i < elist.n; i++)
for (j = 0; j < elist.n - 1; j++)
if (elist.data[j].w > elist.data[j + 1].w) {
temp = elist.data[j];
elist.data[j] = elist.data[j + 1];
elist.data[j + 1] = temp;
}
}
// Printing the result
/**
* @brief
*
*/
void Kruskalprint(edge_list spanlist) {
int i, cost = 0;
printf("克鲁斯卡尔算法 Kruskal Algorithm\n");
for (i = 0; i < spanlist.n; i++) {
printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
cost = cost + spanlist.data[i].w;
}
printf("\nSpanning tree cost: %d\n", cost);
}
/**
* @brief qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序
*
*
* @param a
* @param b
* @return int
*/
int Kruskalcmp(const void* a, const void* b) {
return ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}
/**
* @brief Kruskal Algorithm克鲁斯卡尔算法寻找最小生成树，edges 存储用户输入的图的各个边，minTree 用于记录组成最小生成树的各个边
* @param edge INT 数组
* @param edge 搜索的关键数字
*
* @return 返回
*/
void KruskalMinTree(struct edge edges[], struct edge minTree[]) {
int i, initial, end, elem, k;
//每个顶点配置一个标记值
int assists[P];
int num = 0;
//初始状态下，每个顶点的标记都不相同
for (i = 0; i < P; i++) {
assists[i] = i;
}
//根据权值，对所有边进行升序排序
qsort(edges, N, sizeof(edges[0]), Kruskalcmp);
//遍历所有的边
for (i = 0; i < N; i++) {
//找到当前边的两个顶点在 assists 数组中的位置下标
initial = edges[i].initial - 1;
end = edges[i].end - 1;
//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
if (assists[initial] != assists[end]) {
//记录该边，作为最小生成树的组成部分
minTree[num] = edges[i];
//计数+1
num++;
elem = assists[end];
//将新加入生成树的顶点标记全部改为一样的
for (k = 0; k < P; k++) {
if (assists[k] == elem) {
assists[k] = assists[initial];
}
}
//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
if (num == P - 1) {
break;
}
}
}
KruskalDisplay(minTree);
}
/**
* @brief
*
* @param minTree
*/
void KruskalDisplay(struct edge minTree[]) {
int cost = 0, i;
printf("克鲁斯卡尔算法 Kruskal Algorithm 最小生成树为:\n");
for (i = 0; i < P - 1; i++) {
printf("%d-%d 权值：%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
cost += minTree[i].weight;
}
printf("总权值为：%d\n", cost);
}
调用：
//13 kruskal算法
printf("\n13.kruskal算法,请输入三个数字一行，输完一个数字时，按一个空格分开：\n");
int ki;
struct edge edges[N], minTree[P - 1];
for (ki = 0; ki < N; ki++) {
scanf("%d %d %d", &edges[ki].initial, &edges[ki].end, &edges[ki].weight);//每行输入3个数字 输入一个数字时，按空格键
}
KruskalMinTree(edges, minTree);
//n = 6;
int KruskalGraph[MAX][MAX];
KruskalGraph[0][0] = 0;
KruskalGraph[0][1] = 4;
KruskalGraph[0][2] = 4;
KruskalGraph[0][3] = 0;
KruskalGraph[0][4] = 0;
KruskalGraph[0][5] = 0;
KruskalGraph[0][6] = 0;
KruskalGraph[1][0] = 4;
KruskalGraph[1][1] = 0;
KruskalGraph[1][2] = 2;
KruskalGraph[1][3] = 0;
KruskalGraph[1][4] = 0;
KruskalGraph[1][5] = 0;
KruskalGraph[1][6] = 0;
KruskalGraph[2][0] = 4;
KruskalGraph[2][1] = 2;
KruskalGraph[2][2] = 0;
KruskalGraph[2][3] = 3;
KruskalGraph[2][4] = 4;
KruskalGraph[2][5] = 0;
KruskalGraph[2][6] = 0;
KruskalGraph[3][0] = 0;
KruskalGraph[3][1] = 0;
KruskalGraph[3][2] = 3;
KruskalGraph[3][3] = 0;
KruskalGraph[3][4] = 3;
KruskalGraph[3][5] = 0;
KruskalGraph[3][6] = 0;
KruskalGraph[4][0] = 0;
KruskalGraph[4][1] = 0;
KruskalGraph[4][2] = 4;
KruskalGraph[4][3] = 3;
KruskalGraph[4][4] = 0;
KruskalGraph[4][5] = 0;
KruskalGraph[4][6] = 0;
KruskalGraph[5][0] = 0;
KruskalGraph[5][1] = 0;
KruskalGraph[5][2] = 2;
KruskalGraph[5][3] = 0;
KruskalGraph[5][4] = 3;
KruskalGraph[5][5] = 0;
KruskalGraph[5][6] = 0;
edge_list spanlist;
edge_list elist;
KruskalAlgo(KruskalGraph,spanlist,spanlist);
输出：
