标准最小生成树kruskal程序,熟记

2024-05-03 11:58

本文主要是介绍标准最小生成树kruskal程序,熟记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

#include <stdio.h>
#include <stdlib.h>#define MAX 100/* 定义边(x,y),权为w */
typedef struct
{int x, y;int w;
}edge;edge e[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
int sum;/* 比较函数,按权值(相同则按x坐标)非降序排序 */
int cmp(const void *a, const void *b)
{if ((*(edge *)a).w == (*(edge *)b).w){return (*(edge *)a).x - (*(edge *)b).x;}return (*(edge *)a).w - (*(edge *)b).w;
}/* 初始化集合 */
void Make_Set(int x)
{father[x] = x;rank[x] = 0;
}/* 查找x的父节点 */
int Find_Set(int x)
{if (x != father[x]){father[x] = Find_Set(father[x]);}return father[x];
}/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{sum += w;if (x == y) return;/* 将秩较小的树连接到秩较大的树后 */if (rank[x] > rank[y]){father[y] = x;}else{if (rank[x] == rank[y]){rank[y]++;}father[x] = y;}
}/* 主函数 */
int main()
{int i, p, n;int x, y;char chx, chy;/* 读取顶点和边的数目 */scanf("%d %d", &p, &n);getchar();/* 读取边信息并初始化集合 */for (i = 0; i < n; i++){scanf("%c %c %d", &chx, &chy, &e[i].w);getchar();e[i].x = chx - 'A';e[i].y = chy - 'A';Make_Set(i);}/* 将边排序 */qsort(e, n, sizeof(edge), cmp);sum = 0;for (i = 0; i < n; i++){x = Find_Set(e[i].x);y = Find_Set(e[i].y);if (x != y){printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);Union(x, y, e[i].w);}}printf("Total:%d\n", sum);system("pause");return 0;
}


 

这篇关于标准最小生成树kruskal程序,熟记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/956693

相关文章

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》:本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

基于Python开发PDF转Doc格式小程序

《基于Python开发PDF转Doc格式小程序》这篇文章主要为大家详细介绍了如何基于Python开发PDF转Doc格式小程序,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用python实现PDF转Doc格式小程序以下是一个使用Python实现PDF转DOC格式的GUI程序,采用T

C++ Primer 标准库vector示例详解

《C++Primer标准库vector示例详解》该文章主要介绍了C++标准库中的vector类型,包括其定义、初始化、成员函数以及常见操作,文章详细解释了如何使用vector来存储和操作对象集合,... 目录3.3标准库Vector定义和初始化vector对象通列表初始化vector对象创建指定数量的元素值

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch