最小生成树之克鲁斯卡尔(kruskal)算法

2024-04-29 17:48

本文主要是介绍最小生成树之克鲁斯卡尔(kruskal)算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

#include <iostream>  
#include <string>  
using namespace std;  typedef struct MGraph{  string vexs[10];//顶点信息  int arcs[10][10];//邻接矩阵  int vexnum, arcnum;//顶点数和边数  
}MGraph;  int LocateVex(MGraph G, string u)//返回顶点u在图中的位置  
{  for(int i=0; i<G.vexnum; i++)  if(G.vexs[i]==u)  return i;  return -1;  
}  void CreateUDN(MGraph &G)//构造无向网  
{  string v1, v2;  int w;  int i, j, k;  cout<<"请输入顶点数和边数:";  cin>>G.vexnum>>G.arcnum;  cout<<"请输入顶点:";  for(i=0; i<G.vexnum; i++)  cin>>G.vexs[i];  for(i=0; i<G.vexnum; i++)  for(j=0; j<G.vexnum; j++)  G.arcs[i][j]=1000;//初始化权值  cout<<"请输入边和权值:"<<endl;  for(k=0; k<G.arcnum; k++)  {  cin>>v1>>v2>>w;  i=LocateVex(G, v1);  j=LocateVex(G, v2);  G.arcs[i][j]=G.arcs[j][i]=w;  }  
}  void Kruskal(MGraph G)//克鲁斯卡尔算法  
{  int set[10], i, j;  int k=0, a=0, b=0, min=G.arcs[a][b];  for(i=0; i<G.vexnum; i++)  set[i]=i;//初态,各顶点分别属于各个集合  cout<<"最小生成树的各条边为:"<<endl;  while(k < G.vexnum-1)//最小生成树的边数等于顶点数-1  {  for(i=0; i<G.vexnum; i++)//寻找最小权值的边,无向网,只在上三角形中查找  for(j=i+1; j<G.vexnum; j++)  if(G.arcs[i][j] < min)  {  min=G.arcs[i][j];//最小权值  a=i;//边的一个顶点  b=j;//边的另一个顶点  }  min=G.arcs[a][b]=1000;//避免下次查找  if(set[a]!=set[b])//边的两个顶点不属于同一集合  {  cout<<G.vexs[a]<<"-"<<G.vexs[b]<<endl;  k++;//边数加1  for(i=0; i<G.vexnum; i++)  if(set[i]==set[b])//将顶点b所在集合并入顶点a集合  set[i]=set[a];  }  }  
}  void main()  
{  MGraph G;  CreateUDN(G);  Kruskal(G);  
}  


 


这篇关于最小生成树之克鲁斯卡尔(kruskal)算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python如何生成指定文件大小

《python如何生成指定文件大小》:本文主要介绍python如何生成指定文件大小的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python生成指定文件大小方法一(速度最快)方法二(中等速度)方法三(生成可读文本文件–较慢)方法四(使用内存映射高效生成

Maven项目中集成数据库文档生成工具的操作步骤

《Maven项目中集成数据库文档生成工具的操作步骤》在Maven项目中,可以通过集成数据库文档生成工具来自动生成数据库文档,本文为大家整理了使用screw-maven-plugin(推荐)的完... 目录1. 添加插件配置到 pom.XML2. 配置数据库信息3. 执行生成命令4. 高级配置选项5. 注意事

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五

Android与iOS设备MAC地址生成原理及Java实现详解

《Android与iOS设备MAC地址生成原理及Java实现详解》在无线网络通信中,MAC(MediaAccessControl)地址是设备的唯一网络标识符,本文主要介绍了Android与iOS设备M... 目录引言1. MAC地址基础1.1 MAC地址的组成1.2 MAC地址的分类2. android与I

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

PyQt5+Python-docx实现一键生成测试报告

《PyQt5+Python-docx实现一键生成测试报告》作为一名测试工程师,你是否经历过手动填写测试报告的痛苦,本文将用Python的PyQt5和python-docx库,打造一款测试报告一键生成工... 目录引言工具功能亮点工具设计思路1. 界面设计:PyQt5实现数据输入2. 文档生成:python-