无向连通网的最小生成树算法[第3部分]

2024-05-15 21:32
文章标签 算法 最小 生成 部分 连通 无向

本文主要是介绍无向连通网的最小生成树算法[第3部分]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 

普利姆算法的测试数据如下：每行数据表示边的两个端点和权值
10 13
1 0 4
2 1 2
3 0 3
4 3 8
5 1 2
5 2 2
5 4 1
6 3 10
7 4 4
8 5 4
8 7 6
9 6 5
9 7 2

普利姆最小生成树算法：

/*时间：2017.1.1描述：普利姆算法求解最小生成树
*/
#include<iostream>
#include<climits>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<fstream>
#define INF INT_MAX
#define FILEINPUT 1
using namespace std;typedef struct edgeNode
{int from,to;int cost;
}
EDGENODE;void creatMatrix(int **AdjMatrix,int n,int e);                              //构建无向图的邻接矩阵
void printMatrix(int **AdjMatrix,int n);                                    //输出图的邻接矩阵
void initEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int start);        //初始化边集
int  chooseEdge(EDGENODE *edgeSet,int n,int index);                         //从候选边集中选取权重最小的边
void modfiyEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int index,int to);//调整候选边集
void primMst(int **AdjMatrix,EDGENODE *edgeSet,int n,int start);            //普利姆算法
void printMst(EDGENODE *edgeSet,int n);                                     //输出最小生成树选举结果int main()
{//freopen("data.txt","r",stdin);#if FILEINPUT                                           //条件编译：输入重定向到文件(输入邻接矩阵数据)ifstream fin("data.txt");streambuf *strm_buf=cin.rdbuf();cin.rdbuf(fin.rdbuf());#endifint i,n,e,start;int **AdjMatrix;                                        //存储邻接矩阵EDGENODE *edgeSet;                                      //存储最小生成树选的边集cout<<"Enter the number of nodes and edges:"<<endl;cin>>n>>e;AdjMatrix=(int **)malloc(sizeof(int *)*n);              //为邻接矩阵分配存储空间for(i=0;i<n;i++)AdjMatrix[i]=(int *)malloc(sizeof(int)*n);edgeSet=(EDGENODE *)malloc(sizeof(EDGENODE)*n);         //为最小生成树边集合配存储空间creatMatrix(AdjMatrix,n,e);                             //构建无向图的邻接矩阵printMatrix(AdjMatrix,n);                               //输出图的邻接矩阵#if FILEINPUT                                           //条件编译：输入重定向到键盘(输入普利姆算法的起始顶点)cin.rdbuf(strm_buf);#endifwhile(1){cout<<"Enter the start position of the Graph: ";cin>>start;primMst(AdjMatrix,edgeSet,n,start);printMst(edgeSet,n);}#if FILEINPUT                                           //条件编译：输入重定向到键盘(输入普利姆算法的起始顶点)fin.close();#endifreturn 0;
}void creatMatrix(int **AdjMatrix,int n,int e)
{int i,j,from,to,cost;for(i=0;i<n;i++)for(j=0;j<n;j++)AdjMatrix[i][j]=INF;cout<<"<from----to----cost>"<<endl;for(i=0;i<e;i++){cin>>from>>to>>cost;AdjMatrix[from][to]=cost;AdjMatrix[to][from]=cost;}
}void printMatrix(int **AdjMatrix,int n)
{int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)if(AdjMatrix[i][j]==INF)cout<<setiosflags(ios::left)<<setw(6)<<"INF";elsecout<<setiosflags(ios::left)<<setw(6)<<AdjMatrix[i][j];cout<<endl;}
}void initEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int start)
{int i,index=0;for(i=0;i<n;i++)if(i!=start){edgeSet[index].from=start;edgeSet[index].to=i;edgeSet[index].cost=AdjMatrix[start][i];index++;}
}int chooseEdge(EDGENODE *edgeSet,int n,int index)
{int minCost=INF,minPos,i;for(i=index;i<n-1;i++)if(edgeSet[i].cost<minCost){minCost=edgeSet[i].cost;minPos=i;}if(minCost==INF){cout<<"The Graph is disconnected!"<<endl;exit(1);//图不连通,程序结束}return minPos;
}void modfiyEdgeSet(int **AdjMatrix,EDGENODE *edgeSet,int n,int index,int to)
{int i,cost;for(i=index;i<n-1;i++){cost=AdjMatrix[to][edgeSet[i].to];if(cost<edgeSet[i].cost){edgeSet[i].cost=cost;edgeSet[i].from=to;}}
}void primMst(int **AdjMatrix,EDGENODE *edgeSet,int n,int start)
{int iter,minPos,to;EDGENODE edge;initEdgeSet(AdjMatrix,edgeSet,n,start);     //初始化边集合for(iter=0;iter<n-1;iter++){minPos=chooseEdge(edgeSet,n,iter);      //从边集中选择取值最小边edge=edgeSet[minPos];                   //将选择的最小边edgeSet[iter]edgeSet[minPos]=edgeSet[iter];          edgeSet[iter]=edge;to=edgeSet[iter].to;                    //将选择的边结点加入U集合modfiyEdgeSet(AdjMatrix,edgeSet,n,iter,to);//调整候选边结点}
}void printMst(EDGENODE *edgeSet,int n)
{int index;int totalCost=0;for(index=0;index<n-1;index++){cout<<"("<<edgeSet[index].from<<","<<edgeSet[index].to<<") "<<edgeSet[index].cost<<endl;totalCost+=edgeSet[index].cost;}cout<<"totalCost: "<<totalCost<<endl;
}
克鲁斯科尔算法的测试数据：第一行表示图的顶点数和边数；从第二行开始表示表的顶点编号和权值
10 13
0 1 4
1 2 2
0 3 3
3 4 8
1 5 2
2 5 2
4 5 1
3 6 10
4 7 4
5 8 4
7 8 6
6 9 5
7 9 2

克鲁萨卡尔算法：

/*时间：2017.1.1描述：结合并查集实现克鲁斯卡尔算法求最小生成树
*/
#include<iostream>
#include<climits>
#include<iomanip>
#include<cstring>
#include<fstream>
#include<algorithm>
#define INF INT_MAX
#define FILEINPUT 1
using namespace std;typedef struct edgeNode
{int from,to;int cost;
}
EDGENODE;bool operator<(const EDGENODE &a,const EDGENODE &b)
{if(a.cost!=b.cost)return a.cost<b.cost;else if(a.from!=b.from)return a.from<b.from;else return a.to<b.to;
}int flag[512];void creatMatrix(int **AdjMatrix,EDGENODE *edgeSet,int n,int e);
void printMatrix(int **AdjMatrix,int n);
void printEdgeSet(EDGENODE *edgeSet,int e);
void kruskalMst(EDGENODE *edgeSet,int n,int e);
int findRootEdge(int nodeNumber);
int mergeEdge(int nodeFrom,int nodeTo);int main()
{//freopen("data.txt","r",stdin);#if FILEINPUT                                           //条件编译：输入重定向到文件(输入邻接矩阵数据)ifstream fin("data.txt");streambuf *strm_buf=cin.rdbuf();cin.rdbuf(fin.rdbuf());#endifint i,n,e;int **AdjMatrix;                                        //存储邻接矩阵EDGENODE *edgeSet;                                      //边集合cout<<"Enter the number of nodes and edges:"<<endl;     cin>>n>>e;AdjMatrix=(int **)malloc(sizeof(int *)*n);              //为邻接矩阵分配存储空间for(i=0;i<n;i++)AdjMatrix[i]=(int *)malloc(sizeof(int)*n);edgeSet=(EDGENODE *)malloc(sizeof(EDGENODE)*e);         //为边集合分配存储空间for(i=0;i<n;i++)                                        //初始化并查集flag[i]=i;creatMatrix(AdjMatrix,edgeSet,n,e);printMatrix(AdjMatrix,n);kruskalMst(edgeSet,n,e);#if FILEINPUT                                           //条件编译：输入重定向到键盘(输入普利姆算法的起始顶点)cin.rdbuf(strm_buf);fin.close();#endifreturn 0;
}void creatMatrix(int **AdjMatrix,EDGENODE *edgeSet,int n,int e)
{int i,j,from,to,cost;EDGENODE edge;for(i=0;i<n;i++)for(j=0;j<n;j++)AdjMatrix[i][j]=INF;cout<<"<from----to----cost>"<<endl;for(i=0;i<e;i++){cin>>from>>to>>cost;AdjMatrix[from][to]=cost;AdjMatrix[to][from]=cost;edge.from=from;edge.to=to;edge.cost=cost;edgeSet[i]=edge;}
}void printMatrix(int **AdjMatrix,int n)
{int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++){if(AdjMatrix[i][j]==INF)cout<<setiosflags(ios::left)<<setw(6)<<"INF";elsecout<<setiosflags(ios::left)<<setw(6)<<AdjMatrix[i][j];}cout<<endl;}
}void printEdgeSet(EDGENODE *edgeSet,int e)
{int index=0;for(index=0;index<e;index++)cout<<"("<<edgeSet[index].from<<","<<edgeSet[index].to<<") "<<edgeSet[index].cost<<endl;
}int findRootEdge(int nodeNumber) 
{int i,j,root;root=nodeNumber;while (flag[root]!=root)                //循环结束，则找到同一边集中的最小结点编号root= flag[root];       i=nodeNumber;while(i!=root)                          //本循环修改查找路径中所有边结点编号{j=flag[i];flag[i]=root;i=j;}return root;
}int mergeEdge(int nodeFrom,int nodeTo)      //边结点合并到连通图中
{int indexFrom=findRootEdge(nodeFrom);int indexTo=findRootEdge(nodeTo);if(flag[indexFrom]<flag[indexTo])flag[indexTo]=indexFrom;elseflag[indexFrom]=indexTo;if(indexFrom==indexTo)return 1;elsereturn 0;
}void kruskalMst(EDGENODE *edgeSet,int n,int e)
{int index=0;int countEdge=0;int minCost=0;//cout<<"------------------------------------"<<endl;//printEdgeSet(edgeSet,e);sort(edgeSet,edgeSet+e);                            //对边集进行快速排序//cout<<"------------------------------------"<<endl;//printEdgeSet(edgeSet,e);//cout<<"------------------------------------"<<endl;while(index<e){int from=edgeSet[index].from;int to=edgeSet[index].to;int cost=edgeSet[index].cost;if(mergeEdge(from,to)==0)                       //利用并查集判断环路,同时对查找路径进行压缩合并{countEdge++;minCost+=cost;cout<<"("<<from<<","<<to<<") "<<cost<<endl;index++;}else{index++;}if(countEdge==n-1){break;}}if(index<e)                                             cout<<"minCost: "<<minCost<<endl;else{cout<<"The Graph is disconnected!"<<endl;       //index>=e则不能构造最小生成树}
}

这篇关于无向连通网的最小生成树算法[第3部分]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/992978。

相关文章

Python从Word文档中提取图片并生成PPT的操作代码

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中，我们经常需要从 W
阅读更多...
C#使用Spire.XLS快速生成多表格Excel文件

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压：从3秒到0.5秒的质变1.2 批量操作的优雅
阅读更多...
Python使用python-pptx自动化操作和生成PPT

Python使用python-pptx自动化操作和生成PPT

《Python使用python-pptx自动化操作和生成PPT》这篇文章主要为大家详细介绍了如何使用python-pptx库实现PPT自动化,并提供实用的代码示例和应用场景,感兴趣的小伙伴可以跟随小编... 目录使用python-pptx操作PPT文档安装python-pptx基础概念创建新的PPT文档查看
阅读更多...
在ASP.NET项目中如何使用C#生成二维码

在ASP.NET项目中如何使用C#生成二维码

《在ASP.NET项目中如何使用C#生成二维码》二维码（QRCode）已广泛应用于网址分享,支付链接等场景,本文将以ASP.NET为示例,演示如何实现输入文本/URL,生成二维码,在线显示与下载的完整... 目录创建前端页面（Index.cshtml）后端二维码生成逻辑（Index.cshtml.cs）总结
阅读更多...
Python实现数据可视化图表生成(适合新手入门)

Python实现数据可视化图表生成(适合新手入门)

《Python实现数据可视化图表生成(适合新手入门)》在数据科学和数据分析的新时代,高效、直观的数据可视化工具显得尤为重要,下面：本文主要介绍Python实现数据可视化图表生成的相关资料,文中通过... 目录前言为什么需要数据可视化准备工作基本图表绘制折线图柱状图散点图使用Seaborn创建高级图表箱线图热
阅读更多...
SQLServer中生成雪花ID(Snowflake ID)的实现方法

SQLServer中生成雪花ID(Snowflake ID)的实现方法

《SQLServer中生成雪花ID(SnowflakeID)的实现方法》：本文主要介绍在SQLServer中生成雪花ID(SnowflakeID)的实现方法,文中通过示例代码介绍的非常详细,... 目录前言认识雪花ID雪花ID的核心特点雪花ID的结构（64位）雪花ID的优势雪花ID的局限性雪花ID的应用场景
阅读更多...
Django HTTPResponse响应体中返回openpyxl生成的文件过程

Django HTTPResponse响应体中返回openpyxl生成的文件过程

《DjangoHTTPResponse响应体中返回openpyxl生成的文件过程》Django返回文件流时需通过Content-Disposition头指定编码后的文件名,使用openpyxl的sa... 目录Django返回文件流时使用指定文件名Django HTTPResponse响应体中返回openp
阅读更多...
python生成随机唯一id的几种实现方法

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1：使用 UUID 模块（推荐）方法 2：使用 Secrets 模块（安全敏感场景）方法
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
Python实现自动化Word文档样式复制与内容生成

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2