#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);
}
分享到:
相关推荐
《克鲁斯卡尔法求最小生成树》 在图论领域,寻找最小生成树是解决网络连接问题的一个重要算法。最小生成树问题旨在找到一个无向加权图的边子集,这些边连接了所有顶点,且总权重尽可能小。克鲁斯卡尔(Kruskal)...
克鲁斯卡尔算法(Kruskal's Algorithm)是求解最小生成树的一种经典方法,由约瑟夫·克鲁斯卡尔在1956年提出。本项目以Java编程语言实现了这一算法,并结合图形界面,使得理解和应用更加直观。 首先,我们要理解...
卡尔法奇(Carlfudge)在IT领域中可能是指一种特定的技术、工具或者是一个开发者的名字。由于提供的信息有限,我会假设“卡尔法奇”与CSS(层叠样式表)有关,因为标签指明了这个主题。CSS是网页设计中用于控制布局...
2. **动力学模型**:模型会包含描述机器人运动的数学方程,如牛顿-欧拉或迪卡尔法。这些方程会考虑到重力、惯性、摩擦和关节驱动力等因素。 3. **控制器模块**:可能有一个简单的PID控制器或者更复杂的控制策略,...
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
《基于YOLOv8的智慧社区独居老人生命体征监测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计
Android Studio Meerkat 2024.3.1 Patch 1(android-studio-2024.3.1.14-mac.dmg)适用于macOS Intel系统,文件使用360压缩软件分割成两个压缩包,必须一起下载使用: part1: https://download.csdn.net/download/weixin_43800734/90557060 part2: https://download.csdn.net/download/weixin_43800734/90557056
侧轴承杯加工工艺编制及夹具设计.zip
NASA数据集锂电池容量特征提取(Matlab完整源码和数据) 作者介绍:机器学习之心,博客专家认证,机器学习领域创作者,2023博客之星TOP50,主做机器学习和深度学习时序、回归、分类、聚类和降维等程序设计和案例分析,文章底部有博主联系方式。从事Matlab、Python算法仿真工作8年,更多仿真源码、数据集定制私信。
板料折弯机液压系统设计.zip
C6150车床的设计.zip
机器学习之KNN实现手写数字
python爬虫;智能切换策略,反爬检测机制
mpls-vpn-optionA-all
56tgyhujikolp[
GB 6442-86企业职工伤亡事故调查分析规则.pdf
汽车液压式主动悬架系统的设计().zip
2000-2024年各省专利侵权案件结案数数据 1、时间:2000-2024年 2、来源:国家知识产权J 3、指标:专利侵权案件结案数 4、范围:31省 5、用途:可用于衡量知识产权保护水平
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
内容概要:本文档详细复现了金融数学课程作业,涵盖欧式看涨期权定价和投资组合优化两大部分。对于欧式看涨期权定价,分别采用Black-Scholes模型和蒙特卡洛方法进行了计算,并对彩虹期权进行了基于最大值的看涨期权定价。投资组合优化部分则探讨了最小方差组合、给定收益的最小方差组合、最大效用组合以及给定风险的最大收益组合四种情形,还对比了拉格朗日乘数法和二次规划求解器两种方法。文中不仅提供了详细的MATLAB代码,还有详尽的中文解释,确保每一步骤清晰明了。 适合人群:金融工程专业学生、量化分析师、金融数学爱好者。 使用场景及目标:①帮助学生理解和掌握金融衍生品定价的基本原理和方法;②为从事量化分析的专业人士提供实用工具和技术支持;③作为教学材料辅助高校教师讲授相关内容。 其他说明:文档还包括了完整的论文结构建议,从封面页到结论,再到附录,涵盖了所有必要元素,确保提交的作业符合学术规范。此外,还特别强调了数据预处理步骤,确保代码可以顺利运行。