`
hufeng
  • 浏览: 104478 次
  • 性别: Icon_minigender_1
  • 来自: 江西
社区版块
存档分类
最新评论

克鲁斯卡尔法求最小生成树

阅读更多
#include "stdlib.h"
#include "stdio.h"
#define MAX 100
#define M (MAX*(MAX-1)/2)
/*
Test data:
6 0 1 1 0 2 33 0 3 43 0 4 5 0 5 32 1 2 3 1 3 4 1 4 5 1 5 76 2 3 2 2 4 5 2 5 6 3 4 5 3 5 665 4 5 4 -1 -1 -1
result:
(V0 ,V1 )(V2 ,V3 )(V1 ,V2 )(V4 ,V5 )(V0 ,V4 )
The sum is:15
*/
/*每次从边中选取最小边,直到领点都选取完,并输出T的各条边及各条边的权之和*/
/*无向图带权结构体*/
typedef struct
{
	int i,j,w;
}Edge;
/*按 权 排序*/
void bsort(Edge a[],int n)
{
	Edge t;
	int i,j,ok;
	for(i=1;i<n;i++)
	{
		ok=1;
		for(j=0;j<n-i;j++)
			if(a[j].w>a[j+1].w)
			{
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
				ok=0;
			}
			if(ok)break;
	}
}
/*读入权信息*/
void read(Edge a[],int *c,int n)
{
	int i,j,w;
	*c=0;
	do
	{
		scanf("%d%d%d",&i,&j,&w);
		if(i==-1||j==-1||w==-1)break;
		if(i<0||i>=n||j<0||j>=n||w<=0||i==j) continue;
		if(*c>=M)
		{
			exit(-2);
		}
		a[*c].i=i;a[*c].j=j;a[*c].w=w;(*c)++;
	}while(9);
}
/*sameTree链表功能 表示两个顶点是否在一棵树下,初始化为-1,*/
int sameTree[MAX];
int inSameTree(int i,int j)
{
	int s;
	if(sameTree[i]==-1)
	{
		if(sameTree[j]==-1)
		{
			sameTree[i]=j;
			sameTree[j]=i;
		}
		else
		{
			sameTree[i]=sameTree[j];
			sameTree[j]=i;
		}
		return 0;
	}
	else
	{
		if(sameTree[j]==-1)
		{
			sameTree[j]=sameTree[i];
			sameTree[i]=j;
			return 0;
		}
		else
		{
			s=i;
			//循环判定该两点的边
			while(sameTree[s]!=i)
			{
				if(sameTree[s]==j)return 1;
				s=sameTree[s];
			}
			//如果i j存在 没有连通
			sameTree[s]=sameTree[j];
			sameTree[j]=i;
			return 0;
		}
	}
}
void MST(Edge a[],int n,int vnum)
{
	int c=0,i,sum=0;
	//从n条边中选取vnum-1条边
	for(i=0;i<n;i++)
	{
		if(inSameTree(a[i].i,a[i].j))continue;
		sum+=a[i].w;
		printf("(V%-2d,V%-2d)",a[i].i,a[i].j);
		if(++c%8==0)printf("\n");
		if(c>=vnum-1)
		{
			printf("\nThe sum is:%d\n",sum);
			return;
		}
	}
	if(c<vnum-1)printf("\nThe graph is not connect\n");
}

void main()
{
	Edge a[M];
	int i,n,vnum;//n边数 vnum顶点个数
	printf("enter verxnum and edges with weight:\n");
	scanf("%d",&vnum);
	if(vnum<1||vnum>MAX)
	{
		printf("error:vnum mun must be in [1..%d]\n",MAX);
		return;
	}
	read(a,&n,vnum);
	bsort(a,n);
	for(i=0;i<vnum;i++)
	{
		sameTree[i]=-1;
	}
	MST(a,n,vnum);
}
分享到:
评论

相关推荐

    克鲁斯卡尔法求最小生成树.zip

    《克鲁斯卡尔法求最小生成树》 在图论领域,寻找最小生成树是解决网络连接问题的一个重要算法。最小生成树问题旨在找到一个无向加权图的边子集,这些边连接了所有顶点,且总权重尽可能小。克鲁斯卡尔(Kruskal)...

    3.0最小生成树之克鲁斯卡尔算法(添加生成树,添加画图).zip

    克鲁斯卡尔算法(Kruskal's Algorithm)是求解最小生成树的一种经典方法,由约瑟夫·克鲁斯卡尔在1956年提出。本项目以Java编程语言实现了这一算法,并结合图形界面,使得理解和应用更加直观。 首先,我们要理解...

    卡尔法奇

    卡尔法奇(Carlfudge)在IT领域中可能是指一种特定的技术、工具或者是一个开发者的名字。由于提供的信息有限,我会假设“卡尔法奇”与CSS(层叠样式表)有关,因为标签指明了这个主题。CSS是网页设计中用于控制布局...

    RoabatModel.zip_SIMULINK_The Robot_XM77_matlab_robot manipulator

    2. **动力学模型**:模型会包含描述机器人运动的数学方程,如牛顿-欧拉或迪卡尔法。这些方程会考虑到重力、惯性、摩擦和关节驱动力等因素。 3. **控制器模块**:可能有一个简单的PID控制器或者更复杂的控制策略,...

    《数据结构》(02331)基础概念

    内容概要:本文档《数据结构》(02331)第一章主要介绍数据结构的基础概念,涵盖数据与数据元素的定义及其特性,详细阐述了数据结构的三大要素:逻辑结构、存储结构和数据运算。逻辑结构分为线性结构(如线性表、栈、队列)、树形结构(涉及根节点、父节点、子节点等术语)和其他结构。存储结构对比了顺序存储和链式存储的特点,包括访问方式、插入删除操作的时间复杂度以及空间分配方式,并介绍了索引存储和散列存储的概念。最后讲解了抽象数据类型(ADT)的定义及其组成部分,并探讨了算法分析中的时间复杂度计算方法。 适合人群:计算机相关专业学生或初学者,对数据结构有一定兴趣并希望系统学习其基础知识的人群。 使用场景及目标:①理解数据结构的基本概念,掌握逻辑结构和存储结构的区别与联系;②熟悉不同存储方式的特点及应用场景;③学会分析简单算法的时间复杂度,为后续深入学习打下坚实基础。 阅读建议:本章节内容较为理论化,建议结合实际案例进行理解,尤其是对于逻辑结构和存储结构的理解要深入到具体的应用场景中,同时可以尝试编写一些简单的程序来加深对抽象数据类型的认识。

    【工业自动化】施耐德M580 PLC系统架构详解:存储结构、硬件配置与冗余设计

    内容概要:本文详细介绍了施耐德M580系列PLC的存储结构、系统硬件架构、上电写入程序及CPU冗余特性。在存储结构方面,涵盖拓扑寻址、Device DDT远程寻址以及寄存器寻址三种方式,详细解释了不同类型的寻址方法及其应用场景。系统硬件架构部分,阐述了最小系统的构建要素,包括CPU、机架和模块的选择与配置,并介绍了常见的系统拓扑结构,如简单的机架间拓扑和远程子站以太网菊花链等。上电写入程序环节,说明了通过USB和以太网两种接口进行程序下载的具体步骤,特别是针对初次下载时IP地址的设置方法。最后,CPU冗余部分重点描述了热备功能的实现机制,包括IP通讯地址配置和热备拓扑结构。 适合人群:从事工业自动化领域工作的技术人员,特别是对PLC编程及系统集成有一定了解的工程师。 使用场景及目标:①帮助工程师理解施耐德M580系列PLC的寻址机制,以便更好地进行模块配置和编程;②指导工程师完成最小系统的搭建,优化系统拓扑结构的设计;③提供详细的上电写入程序指南,确保程序下载顺利进行;④解释CPU冗余的实现方式,提高系统的稳定性和可靠性。 其他说明:文中还涉及一些特殊模块的功能介绍,如定时器事件和Modbus串口通讯模块,这些内容有助于用户深入了解M580系列PLC的高级应用。此外,附录部分提供了远程子站和热备冗余系统的实物图片,便于用户直观理解相关概念。

    某型自动垂直提升仓储系统方案论证及关键零部件的设计.zip

    某型自动垂直提升仓储系统方案论证及关键零部件的设计.zip

    2135D3F1EFA99CB590678658F575DB23.pdf#page=1&view=fitH

    2135D3F1EFA99CB590678658F575DB23.pdf#page=1&view=fitH

    agentransack文本搜索软件

    可以搜索文本内的内容,指定目录,指定文件格式,匹配大小写等

    Windows 平台 Android Studio 下载与安装指南.zip

    Windows 平台 Android Studio 下载与安装指南.zip

    Android Studio Meerkat 2024.3.1 Patch 1(android-studio-2024.3.1.14-windows-zip.zip.002)

    Android Studio Meerkat 2024.3.1 Patch 1(android-studio-2024.3.1.14-windows.zip)适用于Windows系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/90557033 part2: https://download.csdn.net/download/weixin_43800734/90557035

    4-3-台区智能融合终端功能模块技术规范(试行).pdf

    国网台区终端最新规范

    4-13-台区智能融合终端软件检测规范(试行).pdf

    国网台区终端最新规范

    【锂电池剩余寿命预测】Transformer-GRU锂电池剩余寿命预测(Matlab完整源码和数据)

    1.【锂电池剩余寿命预测】Transformer-GRU锂电池剩余寿命预测(Matlab完整源码和数据) 2.数据集:NASA数据集,已经处理好,B0005电池训练、B0006测试; 3.环境准备:Matlab2023b,可读性强; 4.模型描述:Transformer-GRU在各种各样的问题上表现非常出色,现在被广泛使用。 5.领域描述:近年来,随着锂离子电池的能量密度、功率密度逐渐提升,其安全性能与剩余使用寿命预测变得愈发重要。本代码实现了Transformer-GRU在该领域的应用。 6.作者介绍:机器学习之心,博客专家认证,机器学习领域创作者,2023博客之星TOP50,主做机器学习和深度学习时序、回归、分类、聚类和降维等程序设计和案例分析,文章底部有博主联系方式。从事Matlab、Python算法仿真工作8年,更多仿真源码、数据集定制私信。

    基于android的家庭收纳App的设计与实现.zip

    Android项目原生java语言课程设计,包含LW+ppt

    大学生入门前端-五子棋vue项目

    大学生入门前端-五子棋vue项目

    二手车分析完整项目,包含源代码和数据集,包含:XGBoost 模型,训练模型代码,数据集包含 10,000 条二手车记录的数据集,涵盖车辆品牌、型号、年份、里程数、发动机缸数、价格等

    这是一个完整的端到端解决方案,用于分析和预测阿联酋(UAE)地区的二手车价格。数据集包含 10,000 条二手车信息,覆盖了迪拜、阿布扎比和沙迦等城市,并提供了精确的地理位置数据。此外,项目还包括一个基于 Dash 构建的 Web 应用程序代码和一个训练好的 XGBoost 模型,帮助用户探索区域市场趋势、预测车价以及可视化地理空间洞察。 数据集内容 项目文件以压缩 ZIP 归档形式提供,包含以下内容: 数据文件: data/uae_used_cars_10k.csv:包含 10,000 条二手车记录的数据集,涵盖车辆品牌、型号、年份、里程数、发动机缸数、价格、变速箱类型、燃料类型、颜色、描述以及销售地点(如迪拜、阿布扎比、沙迦)。 模型文件: models/stacking_model.pkl:训练好的 XGBoost 模型,用于预测二手车价格。 models/scaler.pkl:用于数据预处理的缩放器。 models.py:模型相关功能的实现。 train_model.py:训练模型的脚本。 Web 应用程序文件: app.py:Dash 应用程序的主文件。 callback

    《基于YOLOv8的船舶航行违规并线预警系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的工业布匹瑕疵分类系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    CodeCount.exe

    此为代码审查工具 可查 文件数,字节数,总行数,代码行数,注释行数,空白行数,注释率等

Global site tag (gtag.js) - Google Analytics