图论最小生成树
最小生成树问题
问题描述：
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题
基本要求：
从文件中读入图的信息。
（2）利用克鲁斯卡尔算法求网的最小生成树。
（3）以文本形式生成树中各条边以及他们的权值。
需求分析：
1、输入形式：
每组数据第一行是两个整数m和n，表示所描述的图有m条边，n 个
结点；接下来是m行数据，每行有三个整数s,t,w，分别表示边的
起点、终点和边权；当输入的数据中n=0作为输入结束的标志。 2、输出形式：
如果所输入的有向图可有构造出生成树，输出其最小生成树的边；
每条边占据一行；最后输出最小生成树的权值。如果不能构成树，
则输出“Input Error!”提示用户重新输入。
3、功能描述：
判断图中是否可以构造出一颗最小生成树，若能相应的输出其边集
和最小的生成树的边权之和。
4、样例输入输出：
输入：
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
输出：
1 2
1 3
3
Input Error！
5、效率分析：O(n*longn)
抽象数据结构类型（ADT）：
克鲁斯卡尔算法只需记录边集即可，不需要采用邻接表或者邻接矩阵
进行存储；
抽象数据结构描述：
Typedef struct{
Int s,t; //s和t分别表示起点和终点
Int w; // w表示边相应的权值
}Edge;
概要设计：
基于克鲁斯卡尔算法的思想，首先要对边集按照权值的大小进行排序；
结合并查集的思想来判断加入新的边集的时候是否会生成“环”；
详细设计：
1、输入数据；
2、调用快排函数进行按照边权对边进行排序；
3、结合并查集的思想实现克鲁斯卡尔；
4、输出结果
调试分析：
在并查集的union()操作的时候，最终总是会忘了写"renturn true;"这样的语句，导致最后
将自己的算法在HDOJ上提交的时候ＷＡ了两次！
测试结果：
用户使用说明：
输入的边数最大不能超过10001，顶点数不能超过100！
C++代码详见 code 12.cpp
#include
using namespace std;
#define Max 1001
#define INF 10000001
int adj[Max][Max],dis[Max];
void shift(int n)
{
for(int i=0;i for(int j=0;j { if(i==j) adj[i][j]=0; else if(adj[i][j]==-1) adj[i][j]=INF; } } void Dijkstra(int n,int s,int t) { bool b[Max]; for(int i=0;i { b[i]=0; dis[i]=adj[s][i]; } b[s]=1; for(int i=1;i { int tmp=INF,u=s; for(int j=0;j if(b[j]==0 && dis[j] {tmp=dis[j];u=j;} b[u]=1; for(int j=0;j if(b[j]==0 && adj[u][j] { int tt=dis[u]+adj[u][j]; if(dis[j]>tt) dis[j]=tt; } } if(b[t]) return ; } int main() { int n; cin>>n; for(int i=0;i for(int j=0;j shift(n); int s,t; cout<<"起点：";cin>>s; cout<<"终点：";cin>>t; Dijkstra(n,s,t); cout< return 0; } /* 5 -1 10 3 20 -1 -1 -1 -1 5 -1 -1 2 -1 -1 15 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 4 */ 实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。 Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 Prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: 1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。 榆林学院12届课程设计 《最小生成树问题》 课程设计说明书 学生姓名：赵佳 学号： 1412210112 院系：信息工程学院 专业：计算机科学与技术 班级：计14本1 指导教师： 答辩时间：年月日 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方 法。存储结构采用多种。求解算法多种。 二、需求分析 1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。 3.采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 2、功能描述 （1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。 （2) Switch() 功能选择：给用户提示信息，让用户选择相应功能。 （3) Adjacency_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 （4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 （5) MiniSpanTree_KRSL() kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。 （6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。 四、详细设计 本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的 数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (1) 三．概要设计 (1) 1、功能模块图 (1) 2、各个模块详细的功能描述 (2) 四．详细设计 (3) 1．主函数和其他函数的伪码算法 (3) 2、主要函数的程序流程图 (7) 3、函数之间的调用关系图 (15) 五．测试数据及运行结果 (15) 1．正常测试数据及运行结果 (16) 2、非正常测试数据及运行结果 (17) 六．调试情况，设计技巧及体会 (18) 七．参考文献 (19) 八．附录：源代码 (19) 一. 设计目的 课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 二. 设计内容 最小生成树问题: 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 三．概要设计 1、功能模块图 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={ 初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w ) 最小生成树模型与实验 第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §6.1树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。 例6.1 已知有五个城市，要在它们之 间架设电话线，要求任何两个城市都可以互相 通话（允许通过其它城市），并且电话线的根 数最少。 用五个点54321,,,,v v v v v 代表五个城市，如果 在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。 定义6.1 一个无圈的连通图称为树. 例6.2 某大学的组织机构如下所示: v 5v 4v 图 教务处 研究处 校行政办公室 研究生院 财务科 行政科 理工学院 人事学院 外语学院 …… 如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。 树的性质： （1） 树必连通，但无回路（圈）； （2） n 个顶点的树必有1-n 条边； （3） 树中任意两点间，恰有一条初等链； （4） 树连通，但去掉任一条边，必变为不连通； （5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。 生成树与最小树 定义6.2 设图),(11E V G =是图},{E V G =的生成子图，如果1G 是一棵树，记),(1E V T =，则称T 是G 的一棵生成树。 定理6.1 图G 有生成树的充分必要条件是图G 的连通的。 数学物理文科 理校教学校长 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日 题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 数据结构实验报告 姓名：邱金梁 班级：rJBJava101 学号：201007092137指导老师：杨关 时间：2012年6月13日 一、最小生成树#include ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout< 编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用 学院名称： 学生姓名： 专业： 学号： 指导教师： 重庆邮电大学教务处制 摘要 随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。 图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。 文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。 关键词：旅游路线问题 Kruskal算法最优路线最小生成树 一、引言 旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。 旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。 二、背景知识 1、图和树 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。 2、生成树 连通图G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 3、最小生成树 对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。 三、最小生成树的求解方法 构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。 数据结构与算法 课程设计报告 课程设计题目：最小生成树问题 专业班级： 姓名：学号： 设计室号： 设计时间： 2011-12-26 批阅时间：指导教师：成绩： 《数据结构与算法》课程设计报告 姓名：学号：专业： 一、课题：最小生成树问题 设计要求： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 问题分析: 在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网中各点之间的权值。 二、功能、算法、体会描述： 系统有一个主界面,是选择界面。本系统一共有两种选择，克鲁斯卡尔算法求解和普利姆算法求解。根据提醒，输入相应数据，选择你想要的求解方式。第一种方式是克鲁斯卡尔算法。输入你想要建立网络的城市数量，然后输入它们两两之间的建设成本，运行得到网络的建立方式。第二种方式是普利姆算法，操作方法和第一种一致。 １．克鲁斯卡尔算法： 基本思想： 假设WN=（V, {E}）是一个含有N个顶点的连通网。则按照克鲁斯卡 尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集 为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它 是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值 最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也 就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条 边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最 prim算法 设置两个集合P和Q，其中P 用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P={V1}（假设构造最小生成树时，从顶点V1出发），集合Q的初值为 。Prime算法的思想是，从所有p ∈P，v∈V-P的边中，选取具有最小权值的边pv,将顶点v加入集合P中，将边pv 加入集合Q中，如此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成的所有边。（找最小的权，不连成圈即可） ?clc;clear; ?M=1000; ?a(1,2)=50; a(1,3)=60; ?a(2,4)=65; a(2,5)=40; ?a(3,4)=52;a(3,7)=45; ?a(4,5)=50; a(4,6)=30;a(4,7)=42; ?a(5,6)=70; ?a=[a;zeros(2,7)]; ?a=a+a';a(find(a==0))=M; ?result=[];p=1;tb=2:length(a); ?while length(result)~=length(a)-1 ?temp=a(p,tb);temp=temp(:); ?d=min(temp); ?[jb,kb]=find(a(p,tb)==d); ?j=p(jb(1));k=tb(kb(1)); ?result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; ?end ?result ?例、一个乡有7个自然村，其间道路如图所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？ Kruskal算法 每步从未选的边中选取边e，使它与已选边不构成圈，且e 是未选边中的最小权边，直到选够n-1条边为止。 ?clc;clear; ?M=1000; ?a(1,2)=50; a(1,3)=60; ?a(2,4)=65; a(2,5)=40; ?a(3,4)=52;a(3,7)=45; ?a(4,5)=50; a(4,6)=30;a(4,7)=42; ?a(5,6)=70; ?[i,j]=find((a~=0)&(a~=M)); ?b=a(find((a~=0)&(a~=M))); ?data=[i';j';b'];index=data(1:2,:); ?loop=max(size(a))-1; ?result=[]; ?while length(result) 第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §6.1树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。 例6.1 已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。 用五个点54321,,,,v v v v v 代表五个城市，如果 在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。 定义6.1 一个无圈的连通图称为树. 例6.2 某大学的组织机构如下所示: v 5v 4 v 图 6.1 教务处 研究处 校行政办公室 研究生院 财务科 行政科 理工学院 人事学院 外语学院 …… 如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。 树的性质： （1） 树必连通，但无回路（圈）； （2） n 个顶点的树必有1-n 条边； （3） 树中任意两点间，恰有一条初等链； （4） 树连通，但去掉任一条边，必变为不连通； （5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。 生成树与最小树 定义6.2 设图),(11E V G =是图},{E V G =的生成子图，如果1G 是一棵树，记),(1E V T =，则称T 是G 的一棵生成树。 定理6.1 图G 有生成树的充分必要条件是图G 的连通的。 数学系 物理系 文科办公 理科办校教学办公室 校长 数据结构上机实验报告题目：两种算法实现最小生成树 学生姓名 学生学号 学院名称计算机学院 专业计算机科学与技术 时间 2014.12.9 目录 第一章需求分析 (1) 1.1 原题表述 (1) 1.2 问题解决方案 (1) 第二章概要设计 (2) 2.1 抽象数据类型 (2) 2.2 主要算法描述 (2) 2.1.1 Prim算法实现 (2) 2.1.2 Kruskal算法实现 (3) 2.3 主要算法分析 (3) 第三章概要设计 (4) 3.1 程序代码 (4) 3.1.1 Prim算法实现 (4) 3.1.2 Kruskal算法实现 (6) 第四章调试分析 (9) 4.1 出现的问题及解决方法 (9) 第五章测试分析 (10) 5.1 测试样例 (10) 第一章需求分析 1.1 原题表述 某市为实现交通畅行，计划使全市中的任何两个村庄之间都实现公路互通，虽然不需要直接的公路相连，只要能够间接可达即可。现在给出了任意两个城镇之间修建公路的费用列表，以及此两个城镇之间的道路是否修通的状态，要求编写程序求出任意两村庄都实现公路互通的最小成本。 输入参数：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。当N为0时输入结束。 输出参数：每个测试用例占输出的一行，输出实现后所需的最小成本值 1.2 问题解决方案 第一种方案：使用Prim算法 首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。 第二种方案：使用kruskal算法 算法过程：1.将图各边按照权值进行排序2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。 河南城建学院 课程设计报告书 专业：计算机科学与技术 课程设计名称：《数据结构课程设计》 题目：最小生成树问题 班级： 学号： 姓名： 同组人员: 指导老师： 完成时间：2012年2月17日 摘要 本课程设计主要解决图的关键路径的实现。在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。 在本程序设计中，要求实现图的关键路径，最小生成树，判断两点之间是否有路径，程序由2个模块组成，分别为主函数的创建及其他相关函数的设计。程序通过调试运行，初步实现了设计目标。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。 关键词程序设计； C++；图；关键路径 目录 目录 .................................................................................................................................. - 3 - 第一章开发环境和开发工具 (4) 1.1 C/ C ++语言简介 (4) 1.1 开发背景 (4) 1.3 开发环境 (5) 第二章算法思想 (6) 2.1 系统需求分析 (6) 2.2 系统总体设计 (7) 2.2.1 系统设计目标 (7) 2.2.2 开发设计思想 (7) 2.2.3 系统功能模块设计 (9) 2.3 算法思想描述 (9) 第三章算法实现 (11) 3.1 数据结构 (11) 3.2 程序模块 (12) 1.insertsort函数 (12) 3.3 各模块之间的调用关系 (17) 3.4 源程序代码 (17) 第四章测试与分析 (27) 4.1 测试数据选择 (27) 总结 (30) 心得体会 (31) 参考文献 (32) 实验报告六月 18 2015 姓名：陈斌学号：E 专业：13计算机科学与技术数据结构第八次实验 学号E专业计算机科学与技术姓名陈斌 实验日期教师签字成绩 实验报告 【实验名称】最小生成树和最短路径 【实验目的】 (1)掌握最小生成树以及最短路径的相关概念； (2)掌握Prim算法和Kruskal算法； (3)掌握Dijkstra算法 【实验内容】 采用普里姆算法求最小生成树 (1)编写一个算法，对于教材图(a)所示的无向带权图G采用普里姆算法输出从顶点 V1出发的最小生成树。图的存储结构自选。 (2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按 权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset 值都修改为与i的相同。c.重复b步直至输出n-1条边。） 源代码： : #include<> #include<> #include<> dj=INFINITY; /* 网 */ } printf("请输入%d条边的顶点1 顶点2 权值(用空格隔开): \n",; for(k=0;k<;++k) { scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */ i=LocateVex(G,va); j=LocateVex(G,vb); [i][j].adj=[j][i].adj=w; /* 无向 */ } =AN; return OK; } typedef struct { /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */ VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; int minimum(minside SZ,MGraph G) { /* 求的最小正值 */ int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; /* 第一个不为0的值 */ k=i; for(j=i+1;j<;j++) if(SZ[j].lowcost>0) 武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19 课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 - 生成树的计数及其应用 安徽周冬目录 生成树的计数及其应用 (1) 目录 (1) 摘要 (2) 关键字 (2) 问题的提出 (2) [例一]高速公路（SPOJ p104 Highways） (2) [分析] (2) 预备知识 (2) 排列 (3) 行列式 (4) 新的方法 (7) 介绍 (7) 证明 (9) 理解 (12) 具体应用 (12) [例二]员工组织（UVA p10766 Organising the Organisation） (13) [分析] (13) [例三]国王的烦恼（原创） (13) [分析] (14) 总结 (14) 参考文献 (14) 摘要 在信息学竞赛中，有关生成树的最优化问题如最小生成树等是我们经常遇到的，而对生成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面都有着广泛的应用。本文从一道信息学竞赛中出现的例题谈起，首先介绍了一种指数级的动态规划算法，然后介绍了行列式的基本概念、性质，并在此基础上引入Matrix-Tree定理，同时通过与一道数学问题的对比，揭示了该定理所包含的数学思想。最后通过几道例题介绍了生成树的计数在信息学竞赛中的应用，并进行总结。 关键字 生成树的计数Matrix-Tree定理 问题的提出 [例一]高速公路（SPOJ p104 Highways） 一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？ 数据规模：1≤n≤12。 [分析] 我们可以将问题转化到成图论模型。因为任意两点之间恰好只有一条路径，所以我们知道最后得到的是原图的一颗生成树。因此，我们的问题就变成了，给定一个无向图G，求它生成树的个数t(G)。这应该怎么做呢？ 经过分析，我们可以得到一个时间复杂度为O(3n*n2)的动态规划算法，因为原题的规模较小，可以满足要求。但是，当n再大一些就不行了，有没有更优秀的算法呢？答案是肯定的。在介绍算法之前，首先让我们来学习一些基本的预备知识。 预备知识 下面，我们介绍一种重要的代数工具——行列式。为了定义行列式，我们首先来看一下排列的概念。 最短路（djisktra）这个函数直接用就行！ #include for (j= 0; j <101; j++)a[i][j]=MAX; while (m--) { cin>>A>>B>>C; a[A][B]=a[B][A]=C; } v=1, d=n; //从1开始的最短路 ShortestPath(); cout< 数据结构课程设计 系别电子信息系 专业计算机科学与技术 班级学号 姓名 指导教师 成绩 2012年7 月12日 目录 1 需求分析 (2) 2 概要设计 (2) 2. 1抽象数据类型定义 (2) 2 . 2模块划分 (3) 3 详细设计 (4) 3. 1数据类型的定义 (4) 3. 2主要模块的算法描述 (6) 4 调试分析 (10) 5 用户手册 (10) 6 测试结果 (11) 7 附录(源程序清单） (13) 参考文献 (20) 一、需求分析 1.要在n个城市之间建设通信网络，只需要架设n-1条线路即可，而要以最低的经济代价建设这个通信网，就需要在这个网中求最小生成树。 (1)利用克鲁斯卡尔算法求网的最小生成树。 (2)实现教科书 6.5 节中定义的抽象数据类型 MFSet 。以此表示构造生成树过程中的连通分量。 (3)输入顶点个数，输入顶点序号（用整型数据[0，1，2，……，100]表示），输入定点之间的边的权值（整型数据）。系统构造无向图，并求解最小生成树。 (4)以图形和文本两种形式输出最小生成树。 2.程序执行的命令包括： (1)随机生成一个图； (2)输入图坐标信息； (3)以文本形式输出最小生成树； (4)以图形形式输出最小生成树； (5)以图形形式输出构造的图； (6)结束。 3.测试数据 (1)用户输入需要构造的图形顶点个数，假设顶点个数为4； (2)C语言函数随机生成的图形，顶点分别为a,b,c,d,权值分别为： ab=75,ac=99,ad=80,bc=33,bd=93,cd=19； (3)最小生成树边的权值分别为:ab=75,bc=33,cd=19; (4)结束。 二、概要设计 1. 图的抽象数据类型定义 ADT Gragh{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R＝{VR} VR＝{离散数学 最小生成树
最小生成树问题
最小生成树问题课程设计报告
最小生成树实验报告
最小生成树模型与实验
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
最短路径与最小生成树
最小生成树在旅游路线选择中的应用概况
最小生成树问题
最小生成树(MATLAB)
最小生成树模型与实验
两种算法实现最小生成树
最小生成树问题
最小生成树和最短路径数据结构实验
数据结构课程设计报告(最小生成树完整版)
算法合集之《生成树的计数及其应用》
最短路和最小生成树
最小生成树问题,图形输出最小生成树