问题出发点： 对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。
条件控制
1.任意定点之间只有一条通路，不能产生环
2.对于n个顶点的生成树只有n-1条通路即可
具体思路
1.先将边按照边的权值排序
2.从小到大依次判断边,若加入该边不形成环,则将该边加入其中,反之,继续扫描下一条边
3.判断结束条件:加入的边为n-1条
具体实现 【最小生成树-克鲁斯卡尔算法(Kruskal算法)】如何判断是否成环?
//parent[i]表示i结点在已经生成树中可到达结点;
int Find(int x){
while(parent[x]>0){
x=parent[x];
} return x;
}
void Kruskal(){
int k=0,i=0;
printf("The lostpath:\n");
while(k算法实现源码
#include
#include
#define N 20
#define inex 1001
int c[7][7]={//用邻接表存储图结构，inex表示两端点不可达
{},
{inex,0,6,1,5,inex,inex},
{inex,6,0,5,inex,3,inex},
{inex,1,5,0,5,4,6},
{inex,5,inex,5,inex,inex,2},
{inex,inex,3,6,inex,0,6},
{inex,inex,inex,2,4,6,0},
};
typedef struct edge{ //构造有序图标数据结构
int form;
//起始端点
int to;
//目标端点
int weight;
//两端点边的权值
}E;
E sortedge[101],t[101];
//t用于排序，将结果赋值给sortedge
int parent[101]={};
//判断是否成环的数据结构
int n=6;
//端点数
int em(int k,int i,int j){//因为图为无相图，该函数判断是否该边已经加入变表
for(int z=0;
z0&&c[i][j]0){
x=parent[x];
} return x;
}
void Kruskal(){
int k=0,i=0;
printf("The lostpath:\n");
while(k 运行结果
文章图片
推荐阅读
- leetcode刷题记录|轮转数组——LeetCode198题
- IB2070数学分析
- 笔记|BYOL(Bootstrap your own latent A new approach to self-supervised Learning)算法笔记
- 37242 Optimisation
- 数据结构与算法|大数据算法题目及其解题技巧
- LeetCode编程题解法汇总|力扣解法汇总432-全 O(1) 的数据结构
- 蓝桥杯|蓝桥杯31天冲刺打卡（Day3）
- 蓝桥杯冲刺题解|蓝桥杯31日冲刺 Day 3
- #|蓝桥杯31天冲刺打卡题解（Day6）