最小生成树and最短路径
最小生成树and 最短路径
无独有偶，在两个学期的期末中两门不同的科目《离散数学》和《数据结构》中都谈到了图及其衍生的最小生成树、最短路径问题，并给出了相应的算法——克鲁斯卡尔、普林、迪杰斯特拉、沃舍尔算法。这无疑是释放了一个很大的信号——这些内容很重要。由于之前学《离散数学》时只要求在思想上理解，并没要求程序实现，所以学起来也挺吃力的。而现在来到了《数据结构》的课程上，我觉得还是有必要写写理解与体会，好让以后用起来没那么难。
最小生成树（Minimum Spanning Tree,MST ）
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。即是在原图上删除边，直到剩余n-1条边，保证n 个结点连通且边的权值加起来最小。
简单图示：
1
1
3 2 MST
2
5
4
4
克鲁斯卡尔（Kruskal ）算法
克鲁斯卡尔算法从边的角度来解决问题，即在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。然而，图的存贮结构采用边集数组，且权值相等的边在数组中排列次序可以是任意的，该方法对于边数相对比较多的图不是很实用，浪费时间。可以说克鲁斯卡尔算法是很直观的算法，适合人的直观思考方式，但是因为上面论述的缘故，克鲁斯卡尔算法比较适用在稀疏图（边的数目不是很多的图）上。
边集数组：
从图变为程序需要的数据，需要采用合适的数据结构。由算法的核心思想上看，我们需要存储的数据为边，而边的要素包括三点：连接的两个结点、边的权值。然而边并不需要具有什么操作来改变自身或者做些什么，所以用struct 来自定义就合适不过了。
struct edge{ int node_1; int node_2; int value ; };
1 2
3 4 1
2
3
4
另外，文中提及了最小边、次小边，这就暗示了应该对所有的边进行排序（sort）。
比较函数应以value作衡量。
bool cmp(edge a , edge b)
{
return a.value < b.value ;
}
现在剩余最后的问题——回路的避免。其实这个也很容易避免，我们可以定义一个数组used[max]，它记录了每一个结点是否被应用的情况，当要加入的一条边中used[a.node_1]和used[a.node_2]都已被应用，那么加入的这条边必然造成回路，否则不会。若造成回路，则舍弃这条边，转而观察加入次小边。
排序后的情况
edge数组node_1 node_2 value
0 1 2 1
1 2 4 2
2 2 4 3
3 3
4 4
4 2 3 5
用红线将舍弃的边删除后，剩余的就成为了最小生成树了。
时间复杂度
若e表示图的边数，那么，排序过程将有O(eloge)，生成过程则是O(e)，故总的来说，时间复杂度为O(eloge)。
普林（Prim）算法
克鲁斯卡尔算法以边为出发点，相应地，普林算法则以点为出发点。从指定顶点开始将它加入集合中，然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边，并将集合外的那个顶点加入到集合中，表示该顶点已连通。再用集合内的顶点与集合外的顶点构成的边中找最小的边，并将相应的顶点加入集合中。如此下去直到全部顶点都加入到集合中，即得最小生成树。以点作为出发点很好地解决了克鲁斯卡尔算法解决边数很多的图的可怕时间复杂度的问题。边数不是制约普林算法的因素，结点才是。
普林算法的简单演算步骤：
（1）初始化集合A()，表示没有点以加入到生成结点中，初始化集合B，使B包含所有结点；
（2）从B中选择一个点作为始加入到A中并从B中剔除；
（3）选择A中所有的点中能到达B的最小权值边，将这条边的另一个点加入到A中并从B 中剔除；
（4）重复（3）操作直至B为NULL，则为最小生成树。
邻接矩阵
如果说克鲁斯卡尔算法使用自定义的边集数组存储图是直观的，那么普林算法采用自定义的点集数组也是合适的？如果以某一点作为单独的数据结构，那么这一数据结构应当包含有与这个点有关的边的所有信息——权值和对应点。但事前我们并不知道这个图的点的最大度数为多少，带着这种未知来定义struct是危险的，所以我们应当采用邻接矩阵——一个存放顶点间关系（边或弧）的数据的二维矩阵，即有一个二维矩阵data，data[a][b]=c表示a 结点和b结点有一条长为c的边，相应地，data[b][a]=c。当a,b之间没有边的时候，应当使data[a][b] = INF（INF表示无穷）。
集合
由演算步骤中得知我们需要抽象出一个集合的概念，用以分开集合A和集合B。对于这种简单的区分，大可不必抽象出对象出来。运用克鲁斯卡尔中used数组的概念也可模拟出这种集合，当used[i]等于特定值代表结点i在哪个集合中即可。
初始化used状态（等于0代表在B中）
memset(used,0,sizeof(used));
然后选取第一结点来实现（2）操作
used[0] = 1 ;
优化（3）
（3）选择A中所有的点中能到达B的最小权值边，将这条边的另一个点加入到A中并从B中剔除；
如何寻找最小权值边？如果直观地去做，从A中各点遍历，那么每加入一个点到A所费的时间也是惊人的，所以也引入两个数组来作优化。
lowcost数组：lowcost[i]表示A集合中到结点i(I必然在集合B中)的权值；
closest数组：对应与lowcost，表示结点i到集合A的用最小权值边连通的点。
所以当（2）中采用了第一结点，那么这个数组应当被初始化为
for(int kn = 1; kn < n ; ++kn ){
lowcost[kn] = data[0][kn];
closest[kn] = 0 ;
}
当进行（3）时只需这样寻找
for(int i = 0 ; i < n ;++i ){
if( !used[i] && lowcost[i] < min ) {
min = lowcost[i] ;
min_site = i ;
}
}
每执行一次（3）都需要对着两个数组进行更新
for (int ks = 0 ; ks < n ; ks++){
if (!used[ks] && (data[min_site][ks] < lowcost[ks])){
owcost[ks] = data[min_site][ks]; closest[ks] = min_site ; } }
时间复杂度
若n 表示图的结点数，那么初始化需要O(n)，找出最小边O(n)，更新为O(n)，需要找出与更新n 次，总的为O(n*(2n)+n)，即O(n*n)。
最短路径
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 18 5
10 7 30 从1到4最短路径
10
9
9
1
1
迪杰斯特拉（Dijkstra ）算法
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解。但是，由于它遍历计算的节点很多，所以效率低。
基本思想
设置顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。
初始时，S 中仅含有源。设u 是G 的某一个顶点，把从源到u 且中间只经过S 中顶点的路称为从源到u 的特殊路径，并用数组dist 记录当前每个顶点所对应的最短特殊路径长度。迪杰斯特拉算法每次从所有特殊路径中取出最短特殊路径及其顶点u ，将u 添加到S 中，同时对数组dist 作必要的修改。一旦S 包含了所有V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。
1 2
3 5
4 1
3
5
4
简单模拟
沿用克鲁斯卡尔算法used 数组来模拟集合S 。
初始化：结点1作为源点，此时的特殊路径有{1-2、1-3、1-4}，最短特殊路径为1-3 10
明显结点3到源点的最短路径已定，则结点3也在S 集合中，dist[3]被赋值为10。 S 加入结点3后，特殊路径有{1-2、1-3、1-4、1-3-2、1-3-5}，最短特殊路径为1-3-5 10
1
明显结点5到源点的最短路径已定，则结点5也在S 集合中，dist[5]被赋值为11。 以此类推，直到所有的点的dist 被计算出来。
难点
无论是边集数组还是邻接矩阵来存储图，对迪杰斯特拉算法来说影响不大，或者说各有各的优劣，视问题分析而定。由上面的分析可以看出，迪杰斯特拉算法的难点在于在特殊路径中找出最短的那条并最后将它删除。对于这种情况，其实我们可以构造一个类来存储最短特殊路径，并使它对特殊路径具有push 、pop 、sort 等的功能。不过STL 也提供了类似的类——priority_queue 。
弗洛伊德沃舍尔（Warshall ）算法
沃舍尔算法只需要使用2n^3次位运算就可以求出传递闭包。
传递闭包
在数学中，在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。当图中点边关系以邻接矩阵给出时，利用沃舍尔算法能够在O(n^3)内算出每点到各个点的最短路径，并以邻接矩阵形式给出。
五行代码之美
共有num_pl 个结点，place[i][j]表示结点i 到结点j 的边权值为place[i][j]，不存在边时则赋值INF 标志。
for(int med = 1 ; med <= num_pl ; ++med) for(int i = 1 ; i <= num_pl ; ++i) for(int j = 1 ; j <= num_pl ; ++j) if(place[i][j] > place[i][med] + place[med][j]) place[i][j] = place[i][med] + place[med][j] ;
1 3
1 5
3
如果结点i 与j 之间能通
过介质点med 来获得更短路径，则更新
place[i][j]的值
最小生成树问题
榆林学院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 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
最小生成树实验报告
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 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 )
最小生成树算法分析
最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）
分别利用prim算法和kruskal算法实现求图的最小生成树
/*分别利用prim算法和kruskal算法实现求图的最小生成树*/ #include if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; printf("输入%d条无向带权边",e); for(k=0;k 最小生成树的两种经典算法的分析及实现 摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。 关键词：连通图，赋权图，最小生成树，算法，实现 1 前言 假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。 2图的概念 2.1 定义 无序积 在无序积中， 无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。 有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。 有时，泛指有向图或无向图。 2.2 图的表示法 有向图，无向图的顶点都用小圆圈表示。 无向边——连接顶点的线段。 有向边——以为始点，以为终点的有向线段。 2.3 概念 (1)有限图——都是有限集的图。 阶图——的图。 零图——的图。特别，若又有，称平凡图。 (2)关联 (边与点关系)——设边(或)，则称与(或)关联。 无环 孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。 (3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。 2.4 完全图 设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则 称为阶无向完全图，记作。 若有向图的任一对顶点，既有有向边，又有有向边，则 称为有向完全图。 例如： 一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。 编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 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 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。 实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U={} 不属于最小生成树的顶点V={1，2，3，4，5，6} 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树 的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6} 3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5} 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5} 5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5} 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成 求出下图的最小生成树 解：MATLAB程序： % 求图的最小生成树的prim算法。 % result的第一、二、三行分别表示生成树边的起点、终点、权集合 % p——记录生成树的的顶点，tb=V\p clc;clear; % 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)]; e=[1 2 20;1 4 7;2 3 18;2 13 8;3 5 14;3 14 14;4 7 10;5 6 30;5 9 25;5 10 9;6 10 30;6 11 30;7 8 2;7 13 5;8 9 4;8 14 2;9 10 6;9 14 3;10 11 11;11 12 30]; n=max([e(:,1);e(:,2)]); % 顶点数 m=size(e,1); % 边数 M=sum(e(:,3)); % 代表无穷大 a=zeros(n,n); for k=1:m a(e(k,1),e(k,2))=e(k,3); end a=a+a'; a(find(a==0))=M; % 形成图的邻接矩阵 result=[];p=1; % 设置生成树的起始顶点 tb=2:length(a); % 设置生成树以外顶点 while length(result)~=length(a)-1 % 边数不足顶点数-1 temp=a(p,tb);temp=temp(:); % 取出与p关联的所有边 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 % 显示生成树（点、点、边长） weight=sum(result(3,:)) % 计算生成树的权 程序结果： result = 1 4 7 8 14 7 9 13 10 10 14 10 11 4 7 8 14 9 13 10 2 5 11 3 6 12 7 10 2 2 3 5 6 8 9 11 1 4 30 30 weight = 137 附图 最小生成树的权是137 一、实验目的：掌握图的存储表示和以及图的最小生成树算法。 二、实验内容： 1.实现图的存储，并且读入图的内容。 2.利用克鲁斯卡尔算法求网络的最小生成树。 3.实现构造生成树过程中的连通分量抽象数据类型。 4.以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求： 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 需求分析： 1、利用克鲁斯卡尔算法求网的最小生成树； 2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩 阵以及按权排序后的边和最后得到的最小生成树； 克鲁斯卡尔算法：假设WN=(V,{E}) 是一个含有n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。 测试数据： 自行指定图进行运算 四、详细设计 源程序 #include Kruskal算法求最小生成树（JA V A） 代码： package homework; import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge { public int start;//始边 public int end;//终边 public double cost;//权重 } public class MinSpanningTree_Kruskal{ private static int MAX = 100; private ArrayList 实验三最小生成树问题 班级：计科1101班 学号：05 姓名：杜茂鹏 2013年5月23日 一、实验目的 掌握图的存储表示和以及图的最小生成树算法。 二、实验内容 1.实现图的存储，并且读入图的内容。 2.利用普里姆算法求网络的最小生成树。 3.实现构造生成树过程中的连通分量抽象数据类型。 4.以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计、 首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件中。 然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点 最后建立此图的最小生成树，并将对应的边及权值写入文件中。 六、详细设计 实验内容(原理、操作步骤、程序代码) #include<> #include<> #include<> #define INFINITY INT_MAX owcost!=0&&mini>cld[i].lowcost) { mini=cld[i].lowcost; s1=i; } } return s1; } void CreateUDN(MGraph &G) { int IncInfo; printf("请分别输入顶点数/弧数/以及弧所含信息:"); scanf("%d %d %d",&,&,&IncInfo); getchar(); for(int i=0;i<;i++){ dj=INFINITY; [i][j].info=NULL; } for(int k=0;k<;k++) { char v1,v2; int w,i,j; printf("输入一条边依附的顶点及权值:"); dj=w; if(IncInfo) *[i][j].info=IncInfo; [j][i]=[i][j]; getchar(); } } dj!=INFINITY) DFS(G,j); } void BFSTraverse(MGraph G,void(*Visit)(MGraph G,int v)) { LinkQueue Q; for(int v=0;v<;v++) visited[v]=0; InitQueue(Q); for(int v=0;v<;v++) if(!visited[v]) { visited[v]=1; Visit(G,v); EnQueue(Q,[v]); while(!QueueEmpty(Q)) { DeQueue(Q); for(int j=0;j<;j++) if(!visited[j]&&[v][j].adj!=INFINITY) { visited[j]=1; Visit(G,j); EnQueue(Q,[j]); } } } } void MiniSpanTree_PRIM(MGraph G,char u) 开题报告 信息与计算科学 最小生成树算法及其应用 一、综述本课题国内外研究动态, 说明选题的依据和意义 最小生成树(minimum spanning tree,MST)是计算机学科中一重要内容, 其算法也是重要的计算方法, 是现代科学中比较热门的研究方向. 一个有个结点的连通图的生成树是原图的极小连通子图, 且包含原图中的所有个n n 结点, 并且有保持图联通的最少的边. 许多应用问题都是一个求五项连通图的最小生成树问题. 例如: 要在个城市之间铺设n 光缆, 主要目标是要使这个城市的任意两个之间都可以通信, 但铺设光缆的费用很高, n 且各个城市之间铺设光缆的费用不同; 另一个目标是要使铺设光缆的总费用最低. 这就需要找到带权的最小生成树. MST 性质: 最小生成树性质: 设是一个连通网络, 是顶点集的一个真(,)G V E =U V 子集. 若是中一条“一个端点在中(例如: ), 另一个端点不在中”的边(,)n u v G U u U ∈U (例如:), 且具有最小权值, 则一定存在的一棵最小生成树包括此边v V U ∈-(,)u v G . (,)u v 求MST 的一般算法可描述为: 针对图, 从空树开始, 往集合中逐条选择并G T T 加入条安全边, 最终生成一棵含条边的MST. 1n -(,)u v 1n -当一条边加入时, 必须保证仍是MST 的子集, 我们将这样的边称(,)u v T {}(,)T u v 为的安全边. 其中主要有两种算法: Prim 算法和Kruskal 算法. T Prim 算法: 该算法由Prim 提出, 但事实上Jarnik 于1930年更早提出. 用于求无向图的最小生成树. 设图 . (),G V E =步骤1: 取一个顶点, 则, . 1v {}1V v ={}E = 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：最小生成树Kruskal算法 院（系）： 专业： 班级： 学号： 姓名： 指导教师： 目录 1 课程设计介绍 (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (4) 2.2.1 功能模块图 (4) 2.2.2 流程图分析 (5) 3 数据结构分析 (11) 3.1存储结构 (11) 3.2算法描述 (11) 4 调试与分析 (13) 4.1调试过程 (13) 4.2程序执行过程 (13) 参考文献 (16) 附录（关键部分程序清单） (17) 1 课程设计介绍 1.1 课程设计内容 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。 1.2 课程设计要求 1.顶点信息用字符串，数据可自行设定。 2.参考相应的资料，独立完成课程设计任务。 3.交规范课程设计报告和软件代码。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析： 1.要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2.Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。 3.Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（d j,p j）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j则是从s到j 的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下： 1）初始化。起源点设置为：①d s=0,p s为空；②所有其它点：d i=∞,p i=？； ③标记起源点s，记k=s，其他所有点设为未标记的。 2）k到其直接连接的未标记的点j的距离，并设置： d j=min[d j, d k+l kj] 数据结构课程设计 系别电子信息系 专业计算机科学与技术 班级学号 姓名 指导教师 成绩 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＝{ 目录 1.需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程 (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (4) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (5) 3.详细设计 (7) 3.1程序 (7) 4.调试与操作说明 (10) 4.1测试结果 (10) 4.2调试分析 (11) 5.课程设计总结与体会 (11) 5.1总结 (11) 5.2体会 (11) 6. 致谢 (12) 7. 参考文献 (12) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计 2.1流程图 图1流程图 2.2抽象数据类型MFSet的定义： ADT MFSet { 数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。 数据关系： S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank 数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 }最小生成树经典算法
最小生成树(Prim、Kruskal算法)整理版
最小生成树在旅游路线选择中的应用概况
(完整word版)实验5 最小生成树算法的设计与实现(报告)
求出下图的最小生成树
离散数学--最小生成树实验报告
Kruskal算法求最小生成树(java)
图的遍历及最小生成树实验报告
【开题报告】最小生成树算法及其应用
数据结构课程设计报告最小生成树Kruskal算法[1]4545
最小生成树问题,图形输出最小生成树
克鲁斯卡尔算法求最小生成树
- 最小生成树算法详解.ppt
- 数据结构课程设计报告最小生成树Kruskal算法[1]4545
- 数学建模-最小生成树-kruskal算法及各种代码
- 最小生成树算法详解
- 最小生成树算法及应用
- (完整word版)实验5 最小生成树算法的设计与实现(报告)
- Prim算法求无向图的最小生成树
- 最小生成树概念回顾习题七讲解最小生成树的生成算法习题(1)正面
- 最小生成树的Kruskal算法
- 最小生成树算法分析
- 最小生成树(Kruskal算法)
- 最小生成树算法详解ppt课件
- 算法合集之《最小生成树问题的拓展》
- 最小生成树的几个算法
- 最小生成树(Prim、Kruskal算法)整理版
- 最小生成树的算法
- 数学建模-最小生成树-kruskal算法及各种代码
- 算法合集之《最小生成树算法及其应用》
- 最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
- Kruskal算法求最小生成树(java)