1. 克鲁斯卡尔算法简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
克鲁斯卡尔算法是一种用来寻找最小生成树的算法（用来求加权连通图的最小生成树的算法）。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
而具体的操作过程为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
a) 将图的所有连接线去掉，只剩顶点文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
b) 从图的边集数组中找到权值最小的边，将边的两个顶点连接起来文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
c) 继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
d) 直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
2. 两个核心问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
问题一 对图的所有边按照权值大小进行排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
问题一直接采用排序算法进行排序即可。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
问题二的核心思想是记录处理，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
3. 代码实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
依旧是仅供参考文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25211.html
#include<stdio.h> #define MAXEDGE 100#define MAXVERTEX 100typedef struct Edge { int begin;//边的起点 int end; //边的终点 int wight;//边的权值} Edge; typedef struct Graph { char vertex[MAXVERTEX];//顶点 Edge edges[MAXEDGE];//边 int numvertex,numedges;//顶点和边的个数} MGraph; void CreateGraph(MGraph* G) { printf("请输入顶点和边的个数：\n"); scanf("%d%d", &G->numvertex, &G->numedges); printf("请输入顶点：\n"); getchar();//利用该函数除去上一系我们在输入结束时按得回车符 for (int i = 0; i < G->numvertex; i++) { scanf("%c", &G->vertex[i]); } printf("按权值从小到大输入边（vi,vj）对应的起点和终点的下标，begin，end以及权值wight:\n"); for (int k = 0; k < G->numedges; k++) { Edge e; scanf("%d%d%d", &e.begin, &e.end, &e.wight); G->edges[k] = e; }} int Find(int *parent, int f) { while (parent[f]>0) { f = parent[f]; } return f;} //最小生成树，克鲁斯卡尔算法void Kruskal(MGraph *G) { int parent[MAXVERTEX];//存放最小生成树的顶点 for (int i = 0; i < G->numvertex; i++) { parent[i] = 0; } int m, n; for (int i = 0; i < G->numedges; i++) { n = Find(parent, G->edges[i].begin); m = Find(parent, G->edges[i].end); if (n != m) { //m=n说明有环 parent[n] = m; printf("(%d,%d) %d\t", G->edges[i].begin, G->edges[i].end, G->edges[i].wight);//打印边和权值 } }} int main() { MGraph G; CreateGraph(&G); Kruskal(&G); return 0;} |