下载文档原格式
数学帮你优化旅行路线旅行是一种令人兴奋的体验，而优化旅行路线可以让我们更好地利用时间和资源，获得更好的旅行体验。
数学作为一门科学，可以帮助我们解决旅行中的路线规划问题，使我们的旅行更加高效和便捷。
本文将介绍数学在优化旅行路线中的应用，并提供一些实用的方法和技巧。
一、旅行销售员问题旅行销售员问题是一个经典的数学问题，它要求找到一条最短的路径，使得旅行员可以经过所有的城市并回到起点。
这个问题在实际生活中有很多应用，比如快递员送货、旅行路线规划等。
解决旅行销售员问题的方法有很多，其中最常用的是蛮力法和动态规划法。
蛮力法是一种穷举所有可能路径的方法，然后找到最短路径。
虽然这种方法可以得到最优解，但是当城市数量增加时，计算量会急剧增加，不适用于大规模问题。
动态规划法则通过将问题分解为子问题，并利用子问题的最优解来求解整个问题。
这种方法可以大大减少计算量，适用于中等规模的问题。
二、最小生成树算法最小生成树算法是另一种常用的优化旅行路线的方法。
最小生成树是指连接所有城市的最短路径，它可以帮助我们找到一条经济、高效的旅行路线。
常用的最小生成树算法有普里姆算法和克鲁斯卡尔算法。
普里姆算法从一个起始城市开始，逐步选择与当前路径最短的城市进行连接，直到所有城市都被连接为止。
克鲁斯卡尔算法则是先将所有城市看作独立的树，然后逐步合并树，直到所有城市都在同一棵树中。
三、模拟退火算法模拟退火算法是一种基于概率的优化算法，它可以帮助我们找到一个接近最优解的旅行路线。
这种算法模拟了金属退火的过程，通过不断降低温度来减少能量，最终达到稳定状态。
在旅行路线优化中，模拟退火算法可以通过随机交换城市的顺序来搜索更优的解。
算法开始时，会以一定的概率接受较差的解，以避免陷入局部最优解。
随着温度的降低，算法会逐渐减少接受较差解的概率，最终得到一个较优的旅行路线。
四、遗传算法遗传算法是一种模拟生物进化过程的优化算法，它可以帮助我们找到一个较优的旅行路线。
最小生成树算法的优化与应用最小生成树算法是图论中一种常用的算法，用于在具有权值的连通图中，选择一棵权值之和最小的生成树。
在实际应用中，最小生成树算法有着广泛的应用场景，例如网络规划、电力传输、城市道路规划等领域。
为了提高算法的效率和适应不同的应用需求，研究者们不断对最小生成树算法进行优化和改进。
本文将对最小生成树算法的优化与应用进行探讨。
一、最小生成树算法概述最小生成树算法用于寻找连通图中的一棵生成树，使得生成树的所有边的权值之和最小。
常用的最小生成树算法有Prim算法和Kruskal算法。
Prim算法是一种贪心算法，从一个任意节点出发，逐步扩展生成树，每次选择与生成树连接的权值最小的边，直到所有的节点都被加入生成树中。
Prim算法的时间复杂度为O(V^2)，其中V为节点的数量。
Kruskal算法是一种基于边的贪心算法，首先对边进行排序，然后按照权值从小到大的顺序逐个加入生成树的边，同时判断是否构成环。
直到生成树的边数等于节点数减一，生成树构建完成。
Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。
二、最小生成树算法的优化为了提高最小生成树算法的效率，在实际应用中，研究者们对其进行了多种优化。
1. 堆优化Prim算法中，每次需要找到与生成树连接的权值最小的边，可以使用堆（最小堆或最大堆）来存储边的权值和对应的节点信息。
这样可以使得查找最小权值的边的时间复杂度降低为O(logV)，从而提高算法的效率。
2. Kruskal算法的优化在Kruskal算法中，每次都要判断当前边是否与已选中的边构成环。
通过使用并查集（Disjoint Set）数据结构，可以快速判断两个节点是否属于同一连通分量，从而优化Kruskal算法中环的判断过程。
并查集可以将节点分为若干个不相交的集合，并支持快速查找集合的代表元素以及合并两个集合的操作。
这样可以将判断环的时间复杂度降低为O(α(V))，其中α为Ackermann函数的反函数，其增长极其缓慢，几乎可以视为常数。
解释最小生成树最小生成树（Minimum Spanning Tree，简称MST）是一种图论中的算法，用于在一个加权连通图中找到一棵包含所有顶点且边权值之和最小的生成树。
生成树是指一个连通图的生成树是指保留图中所有的节点，但只保留足以保持这些节点连通的边的集合。
在实际应用中，我们常常需要找到一个最优的生成树来解决问题。
最小生成树算法可以用于寻找最短路径、最小费用最大匹配等问题。
本文将详细介绍最小生成树的算法及其应用。
一、算法原理最小生成树的算法基于贪心策略。
在生成树中，边的权值表示为边的邻接顶点之间的权值。
边的权值之和反映了边的权值大小。
因此，我们需要寻找的边的权值之和最小的生成树就是一棵最优的生成树。
算法的基本思想是首先将图中的节点按照权值从小到大排序。
然后，从权值最小的节点开始，不断地寻找一个未访问过的节点。
当找到一个未访问过的节点时，将其加入到生成树中，并将其与原图中所有已访问过的节点建立边联系。
这样，生成树中就有了一个未访问过的节点。
接下来，我们继续寻找下一个未访问过的节点。
如果找到了一个节点，我们继续寻找与该节点相邻的节点。
如果找到了一个已访问过的节点，我们继续寻找下一个未访问过的节点。
重复以上步骤，直到所有节点都被正确地加入到生成树中。
二、应用场景最小生成树算法在实际应用中具有广泛的应用，以下列举了几个典型的应用场景：1.最短路径问题：最小生成树算法可以用于寻找一个图中所有节点之间的最短路径。
通过构建最小生成树，我们可以得到图中所有节点之间的最短距离。
在实际应用中，我们可以使用最小生成树算法来找到一个城市的最佳路线，或者找到一个公司的最短路径。
2.最小费用最大匹配问题：最小生成树算法可以用于寻找一个图中所有节点之间的最小费用最大匹配。
在最小费用最大匹配问题中，我们需要找到一个图中所有节点之间的最小费用，使得这些费用之和最大化。
最小生成树算法可以帮助我们找到一个最优的解，从而实现最小费用最大匹配。
最小生成树的优势和好处
最小生成树是一种常用的图论算法，它可以在一个连通的无向图中找到一棵生成树，使得这棵生成树的所有边的权值之和最小。
最小生成树算法的优势和好处是显而易见的，下面我们来详细探讨一下。
最小生成树算法可以用来解决许多实际问题。
例如，在城市规划中，我们需要在城市中建立一些道路，使得任意两个地点之间都可以通过道路到达，同时要求建造的道路总长度最小。
这个问题可以转化为一个无向图，其中每个地点是一个节点，每条道路是一条边，边的权值表示道路的长度。
通过最小生成树算法，我们可以找到一种最优的道路建设方案，从而实现城市规划的目标。
最小生成树算法具有高效性。
最小生成树算法的时间复杂度为O(ElogE)，其中E表示边的数量。
这个时间复杂度比许多其他图论算法都要低，因此最小生成树算法可以在较短的时间内处理大规模的图。
这使得最小生成树算法在实际应用中具有广泛的适用性。
最小生成树算法还具有良好的可扩展性。
最小生成树算法可以通过一些优化技巧来提高算法的效率，例如Kruskal算法和Prim算法。
这些算法可以根据实际情况进行选择，从而实现更好的性能和效率。
最小生成树算法还具有较好的可视化效果。
最小生成树算法可以将生成树以图形的形式展示出来，使得人们可以直观地了解生成树的结构和特点。
这对于理解算法的原理和应用具有重要的意义。
最小生成树算法具有许多优势和好处，它可以用来解决许多实际问题，具有高效性、可扩展性和良好的可视化效果。
因此，在实际应用中，最小生成树算法是一种非常有用的工具，它可以帮助我们更好地理解和解决各种问题。
最小生成树的优势和好处
最小生成树是一种用于解决连通图最短路问题的算法。
它可以帮助我们找到连接一个连通图中所有点的最小边权总和的子图。
最小生成树的优势和好处如下：
1. 算法简单易实现
最小生成树的算法思想简单明了，易于理解和实现。
基本上任何人都可以通过几行代码来实现它。
这样做使得最小生成树成为了一个非常实用的算法，它被广泛应用于实际生活中各种各样的问题中。
2. 计算效率高
最小生成树算法有很好的计算效率。
它可以处理大规模的数据集，而不会因为数据集过大而降低计算速度。
这使得我们可以在较短的时间内得到一个最小生成树，从而对一些实际问题提供有效的解决方案。
3. 可以帮助我们优化路线
使用最小生成树算法可以帮助我们优化路线。
对于一组给定的点，我们可以先用最小生成树算法找出它们之间最短的路径，然后再根据需要设定一些条件来进一步优化这条路径。
这样做可以大大提高我们在实际生活中旅游、交通等方面的效率。
4. 减少成本
最小生成树也可以用于减少成本。
它可以帮助我们找到一组连接点的最小边权总和，从而使我们在完成任务时尽可能的节省时间和成本。
例如，在通信网络的建设中，使用最小生成树算法可以有效地降低网络建设的成本。
5. 能帮助我们更好地理解图论
最小生成树算法是图论中的重要算法。
通过学习最小生成树算法，我们能够更好地理解图论的基础知识和主流算法。
这将有助于我们更深入地学习并掌握相关的技术和数据结构。
编号：审定成绩：重庆邮电大学研究生堂下考试答卷2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用学院名称：学生姓名：专业：学号：指导教师：重庆邮电大学教务处制摘要随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。
很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。
图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。
我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。
本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。
文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。
关键词：旅游路线问题 Kruskal算法最优路线最小生成树一、引言旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。
与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。
道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。
最小生成树的作用和意义
嘿，朋友们！今天咱来聊聊最小生成树，这玩意儿可有意思啦！
你想想看啊，最小生成树就像是一个超级会省钱的购物专家！比如说你要在好多地方之间修路，怎样修才能花最少的钱让所有地方都连通起来呢？这就是最小生成树要解决的问题呀！
它就像是一个巧妙的设计师，能在复杂的网络中找到那条最经济实惠的连线方案。
好比你要给几个村子通水、通电，怎么布置管道、电线才能既搞定问题又不浪费资源呢？最小生成树就能告诉你答案！
这可不是随便说说的哦！在现实生活中，它的作用可大了去了。
比如在城市规划中，要铺设各种管网，用最小生成树的方法就能节省大量的成本呢！难道不是吗？
再想想物流运输，怎么安排路线才能让运输成本最低呢？最小生成树就能帮上大忙呀！它能让那些货车司机少跑冤枉路，多省些油钱，这可不是小数目呢！
而且啊，最小生成树还特别靠谱！它不会乱出主意，总是能找到最优的方案。
就像一个经验丰富的老工匠，每一次出手都恰到好处。
在网络通信中，它也能让信号传输更高效，让我们的上网速度更快，聊天更顺畅，这多棒啊！
你说，要是没有最小生成树，那得浪费多少资源，多花多少冤枉钱啊！它就像是我们生活中的小助手，默默地帮我们把事情做得又好又省。
所以啊，可别小瞧了最小生成树，它虽然不声不响的，但却有着大大的能量呢！它能让我们的生活更便利，让资源得到更合理的利用。
难道你不想拥有这样一个神奇的小助手吗？反正我是觉得它超级厉害的啦！。
数学与旅行数学在旅行规划和导航中的应用数学与旅行：数学在旅行规划和导航中的应用旅行是人们生活中常常会遇到的一种活动。
而在现代社会中，随着科技的不断发展，数学在旅行规划和导航中的应用也愈发重要和广泛。
本文将探讨数学在旅行规划和导航中的应用，并介绍其中一些常见的数学模型和算法。
一、地理位置与坐标系在旅行规划和导航中，准确的地理位置信息是至关重要的。
为了能够在地图上精确标识位置，人们使用了各种坐标系统和地理信息系统（GIS）。
其中，经纬度坐标系统是最常用的系统之一。
经纬度得以建立是依赖于数学几何中的球面三角学理论，具体通过纬度（Latitude）和经度（Longitude）来表示一个地点的位置，帮助人们在旅行中准确导航。
二、路径规划算法旅行规划是旅行的基础，而现代旅行规划又离不开数学中的路径规划算法。
路径规划算法可以帮助人们找到最优的行驶路线，节省时间和资源。
其中，最著名的算法之一是迪杰斯特拉算法（Dijkstra's algorithm），该算法基于图论原理，通过计算节点间的距离来寻找最短路径，被广泛应用于现代导航软件中。
三、图论及网络流问题图论是研究图以及与图相关的算法的一个分支学科，而旅行规划和导航中的路径搜索可以归结为图论问题。
人们通过将地理信息转化为图的节点和边，然后运用图论的算法和模型来解决旅行中的路径规划和导航问题。
在图论中，还涉及到诸如最小生成树（Minimum Spanning Tree）和网络流问题（Network Flow Problem）等模型和算法，它们在旅行规划和导航中起到了重要作用。
四、拓扑学与地图连通性拓扑学是数学中的一个重要分支，它研究的是空间中的相容关系。
在旅行规划和导航中，人们通常希望能够得知某个地区的连通性，即该地区中的任意两点是否能够通过路径相连。
拓扑学的概念和算法可以帮助人们分析地图中的连通性，确定最佳的行驶路线，提供更加准确的旅行建议。
五、统计学在旅行数据分析中的应用除了路径规划和导航，数学在旅行中还有着其他重要的应用领域。
第24卷湖北师范学院学报(自然科学版)Vol124第4期Journal of Hubei Normal University(Natural Science)No14,2004用最小生成树解决TSP问题姚建华,杨成涛(济南94534部队,山东济南 250002)摘要:旅行商问题(Traveling Salesman Problem,TSP问题)是组合优化领域中研究最多的问题之一,是一个经典的NP难题,也是目前优化领域里的研究热点。
目前解决旅行商问题有诸多算法,神经网络、遗传算法、免疫算法等,在各种解决旅行商问题的算法中,还是存在很多问题。
本文用最小化生成树来求解旅行商问题。
在对题目要求进行深入分析的基础上,对原有算法进行了多方面改进,并用C语言进行了实现。
采用选取排除最长路径顶点的方法降低时间复杂度、采用比较顶点次序的方法提高算法准确性、通过自动产生顶点坐标降低输入复杂性和测试的准确性,实验结果表明该算法可以取得较好的效果。
关键词:TSP;最小生成树;最短路径;组合优化中图分类号:TP301.6,TP312 文献标识码:A 文章编号:100922714(2004)0420052205 旅行商问题(Traveling Salesman Problem,TSP问题)就是一个销售商从n个城市中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能的路径中求出路径长度最短的一条,是组合优化领域中研究最多的问题之一。
从50年代中起,出版了大量关于本问题的文献。
Lawler编辑的书对到当时为止的所有主要研究成果作了全面深入的综述。
对于求解旅行商问题,有许多方法和思路,目前最流行的是神经网络算法与遗传算法,在本次设计中,应用最小生成树的解题思路,来解决旅行商问题。
本文中包括了对旅行商问题和最小生成树解题思路的论述,给出了解决旅行商问题的算法设计。
由题目要求可知,对于旅行商问题,城市的数目是根据用户的需求而改变的,而对于所确定数目的n个城市来说,每两个城市之间都有相互连通的路径,且路径的长度是不尽相同的。
编号：审定成绩：重庆邮电大学研究生堂下考试答卷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 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。
1、Prim 算法算法思想：普里姆算法通过逐个往生成树上添加顶点来构造连通网的最小生成树。
算法具体步骤：（1）开始：选取连通网中的任意一个顶点添加到最小生成树中。
（2）重复执行以下操作：➢连通网的顶点集合分成两个部分：已经添加到最小生成树中的顶点集合和尚未添加到最小生成树中的顶点集合；➢找出所有连通这两个集合中顶点的边；➢从中选取一条权值最小的边添加到生成树中，同时将与这条边相连的顶点也添加到生成树中。
（3）结束：所有的顶点都被添加到最小生成树中。
2 、Kruskal 算法算法思想：通过逐个往生成树上添加边来构造连通网的最小生成树。
算法具体步骤：（1）将连通网中的所有顶点添加到最小生成树中，构造一个森林；（2）将各边按照权值从小到大排序；（3）按照排好的顺序向生成树中添加不使森林中产生回路的边(若构成回路则不添加，继续考察下一条边)。
直至该森林变成一棵树为止。
3、破圈法算法思想：通过逐个从连通网中删除边来构造最小生成树。
算法具体步骤：（1）将连通网中各边按照权值从大到小排序；（2）按照排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删除下一条边)。
直至子图中任何一条边都不能删除（即删除任意一条边都会造成该子图不连通）为止。
4 、三种算法的比较（1）普里姆算法：主要是对顶点进行操作；采用邻接矩阵作为存储结构，在行过程中对连通网中的每一个顶点都考察到了。
普里姆算法适用于求边稠密的连通网的最小生成树。
（2）克鲁斯卡尔算法：主要是对边进行操作，时间复杂度主要取决于对边按照权值进行排序的时间，边的个数为e，排序的时间复杂度可以做到O (eloge)，因此算法的时间复杂度为O(eloge)。
克鲁斯卡尔算法适用于求边稀疏的连通网的最小生成树。
（3）破圈法：主要是对边进行操作，时间复杂度主要取决于对边按照权值进行排序的时间，边的个数为e，排序的时间复杂度可以做到O (eloge)，因此算法的时间复杂度为O(eloge)。
该算法适用于求边稀疏的连通网的最小生成树[5]。
四、应用利用最小生成树来解决旅游路线问题，将旅游路线问题中的旅游景点看做图中的顶点，各个景点之间的路线看做图中顶点之间的边，景点之间路线的长度看做图中各边上的权值。
这样，我们就把旅游路线问题转换成了求一个有向连通网的最小生成树问题。
此时，假设景点个数为6，分别为v1,v2,v3,v4,v5,v6。
并设其对应景点之间的路线距离权值及初始状态的连通加权无向图如下图所示。
以下是用Kruskal算法求解最小生成树（1）实现步骤：根据前文介绍的Kruskal算法步骤依次添加边（1,3）, （4,5）, （2,6）, （3,6）, （3,4），并依次添加对应节点，各个步骤结果如下图：v1v31v1v4v3v512第一步 第二步v1v2v4v3v5v6123v1v2v4v3v5v61243第三步 第四步v1v2v4v3v5v651243第五步（2） 仿真及结果分析在vc++6.0环境下，首先输入图的顶点数和边数，然后输入第一条边的起始点和终点，以及这条边的权值，直到输完为止自动将权从小到大排序，并且得出最小生成树，如下图运行结果所示。
五、总结本文首先将实际的旅游路线选择问题转化成了图论的最小生成树问题，然后选用Kruskal算法编写相应的C语言程序最终实现。
这样一方面可以得到一条最有效的路线，使得路途观赏性和时间效率都得到提高，另一方面还可以增加景点（顶点数），改变边的权值（景点之间的距离）等等，具有灵活、准确、简便等特点，由于它的一般性，不仅仅解决了旅游路线选择的问题，同时还适用于其他问题的解决。
参考文献[1]鲍捷.基于最小生成树Kruskal 算法的皖北地区旅游交通优化与线路组织[J].人文地理.2010,03.[2]严蔚敏，吴伟民.数据结构（C语言版）[M] .北京：清华大学出版社，2003，11.[3]谭浩强. C程序设计（第三版）[M] . 北京：清华大学出版社，2005.[4]殷剑宏，吴开亚.图论及其算法[M].北京：中国科学技术大学出版社，2006[5]李晓莉，王发曾，罗军.中原城市群轨道交通干线选择研究[J].2008,10附录Kruskal算法程序：#include<stdio.h>#include<stdlib.h>#define M 20#define MAX 20typedef struct //构造边{int begin;int end;int weight; //权值}edge;typedef struct{int adj;int weight;}AdjMatrix[MAX][MAX];typedef struct{AdjMatrix arc;int vexnum, arcnum; //顶点数和边数}MGraph;void CreatGraph(MGraph *); //函数申明构造图void sort(edge* ,MGraph *); //函数申明对边的排序void MiniSpanTree(MGraph *); //最小生成树int Find(int *, int );void Swapn(edge *, int, int); //交换两条边的权值和它们的起点和终点void CreatGraph(MGraph *G) //构件图G{int i, j,n, m;printf("请输入图的顶点数和边数:");scanf("%d %d",&G->vexnum,&G->arcnum);for (i = 1; i <= G->vexnum; i++) //初始化图{for ( j = 1; j <= G->vexnum; j++){G->arc[i][j].adj = G->arc[j][i].adj = 0;}}for ( i = 1; i <= G->arcnum; i++) //输入边和权值{printf("\n请输入边的起始点和终点:");scanf("%d %d",&n,&m);while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum) {printf(" \n");printf(" \n");printf("输入的数字不符合要求请重新输入:");scanf("%d%d",&n,&m);}G->arc[n][m].adj = G->arc[m][n].adj = 1;getchar();printf("\n请输入%d与%d之间的权值: ", n, m);scanf("%d",&G->arc[n][m].weight); //输入权值}}void sort(edge edges[],MGraph *G) //对权值进行排序{int i, j;for ( i = 1; i < G->arcnum; i++){for ( j = i + 1; j <= G->arcnum; j++){if (edges[i].weight > edges[j].weight){Swapn(edges, i, j);}}}printf(" \n");printf(" \n");printf(" \n");printf(" 权从小到大排序之后为:\n");printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");printf(" 起点终点权\n");for (i = 1; i <= G->arcnum; i++){printf(" <<%d %d>> %d\n", edges[i].begin, edges[i].end, edges[i].weight);}}void Swapn(edge *edges,int i, int j) //交换权值以及头和尾{ int temp;temp = edges[i].begin;edges[i].begin = edges[j].begin;edges[j].begin = temp;temp = edges[i].end;edges[i].end = edges[j].end;edges[j].end = temp;temp = edges[i].weight;edges[i].weight = edges[j].weight;edges[j].weight = temp;}void MiniSpanTree(MGraph *G)//生成最小生成树{int i, j, n, m;int k = 1;int parent[M];edge edges[M];for ( i = 1; i < G->vexnum; i++){for (j = i + 1; j <= G->vexnum; j++){if (G->arc[i][j].adj == 1){edges[k].begin = i;edges[k].end = j;edges[k].weight = G->arc[i][j].weight;k++;}}}sort(edges, G);for (i = 1; i <= G->arcnum; i++){parent[i] = 0;}printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");printf(" \n");printf(" \n");printf(" \n");printf(" 最小生成树为:\n");printf("==================================\n");printf(" 起点终点权\n");for (i = 1; i <= G->arcnum; i++)//核心部分{n = Find(parent, edges[i].begin);m = Find(parent, edges[i].end);if (n != m){parent[n] = m;printf(" << %d %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);}}printf("**********************************\n");}int Find(int *parent, int f)//找尾{while ( parent[f] > 0){f = parent[f];}return f;}int main(void)//主函数{MGraph *G;G = (MGraph*)malloc(sizeof(MGraph));if (G == NULL){printf("memory allcation failed,goodbye");exit(1);}CreatGraph(G);MiniSpanTree(G);system("pause");return 0;}。
