图论在实际生活中的应用

《图论在实际生活中的应用》由会员分享，可在线阅读，更多相关《图论在实际生活中的应用（12页珍藏版）》请在装配图网上搜索。

1、 摘 要寻找最短的路径到达想要去的地方在这个快节奏的时代已经变得越来越重要，它对于节约人们的时间成本具有重要意义。当前城市的规模越来越大，交通道路状况也越来越复杂，从一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带来极大地方便。本文就通过找重庆邮电大学几个代表性地点之间寻找最短距离路径为例，介绍经典的最短路径算法Floyd算法及其算法的实现。关键字： 最优路径，Floyd算法，寻路 一、图论的基本知识图论起源于举世闻名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛

2、及岛与河岸是连接起来的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即用点来代替每一块陆地，将每一座桥用联接相应的两个点的一条线来代替，所以相当于得到一个“图”（如下图）。CABD(b) 柯尼斯堡七桥图 桥转换成图 欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论及拓扑学的创始人。 图论其实也是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，

3、也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形以及巧妙的证明；涉及的问题很多而且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。 那么什么是图论中的图呢？在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中

4、，人们只关心点与点之间是否有连线，而不关心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。 因此在现实世界中，事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度来扩展讨论范围。 1.1、图论概述图论Graph Theory是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等几乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，又大大的促进了图论的发展。图论中的研究对象是由若干给定的点及连接两点的

5、线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 1.2 图论中的最短路问题路的定义 设为无向标定图，中顶点与边的交替序列称为到的通路，其中，为的端点，分别称为始点与终点，中的边的条数称为它的长度，若又有，则称为回路。若的所有边各异，则称为简单通路。若又有，则称为简单回路，若所有的顶点（除与可能相同外）各异，所有的边也各异，则称为初级通路或路径，若又有，则为初级回路或圈，将长度为奇数的圈成为奇圈，长度为偶数的圈为偶圈。我们要考虑的问题是对任意给定的一个赋权图,及中两个指点的顶点与，求出其最短路径。易见。只要考虑简单连通

6、图的情形就够了。这里我们假设每边的权都是大于0的实数。因为当一条边的权为0时。我们可以把和合并成一个顶点。又，我们约定边当且仅当。 1.3 Floyd算法 Floyd算法的基本思想： 可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是地点的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k

7、的最短距离。所以，若有d(ij)d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。 Floyd算法的基本步骤： 定义nn的方阵序列D-1, D0 , Dn1,初始化： D-1C D-1ij边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。迭代：设Dk-1已求出，如何得到Dk（0kn-1） Dk-1ij表示从i到j的中间点不大于k-1

8、的最短路径p：ij， 考虑将顶点k加入路径p得到顶点序列q：ikj， 若q不是路径，则当前的最短路径仍是上一步结果：Dkij= Dk1ij； 否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。 因为q的两条子路径ik和kj皆是中间点不大于k1的最短路径，所以从i到j中间点不大于k的最短路径长度为：Dkijmin Dk-1ij, Dk-1ik +Dk-1kj 二、 利用图论知识寻找指定两点最短路径2.1 把实际问题转化成图论问题 图1 重庆邮电大学地图上图为邮电大学的地图，我们在地图中选取重邮的八个地方看成是八个点（1、新世纪超市 2、三教学楼 3、数字图书馆 4、二教学楼 5、信

9、科大楼 6、太极操场 7、老图书馆 8、31栋宿舍），用线段把每一个点与其相邻的点连接起来，从而形成一个无向图。再根据实际情况：不同地点的距离问题；路的畅通与否等给相应的边赋上权值，最后得出一个赋权图，如图2：图2 赋权图2.2 Floyd算法用C+实现#include#include#includeusing namespace std;#define MAX_VEX_NUM 10vector allPath; /向量，用来存放所有的顶点a到顶点i的路径vector all; /向量，用来存放对应路径的长度struct MGraph char vexsMAX_VEX_NUM; int arc

10、sMAX_VEX_NUMMAX_VEX_NUM;int vexnum,arcnum;MGraph G; int Locatevex(MGraph G,char v)/图的基本操作，寻找V的位置int i=0;while(iG.vexnum & v!=G.vexsi)i+;if(iG.vexnum)return i;elsereturn -1;int CreateUDG(MGraph &G) /数组邻接矩阵表示法构造无向图char v1,v2;int weight;cout请输入图的顶点数和边的条数G.vexnumG.arcnum;cout请输入顶点的名称(0-9)endl;for(int i=

11、0;iG.vexsi; for(int q=0;qG.vexnum;q+) for(int p=0;pG.vexnum;p+) G.arcsqp=0; for(int k=0;kG.arcnum;k+)/构造邻接矩阵 cout输入边的顶点和权值：(格式为：起点 终点 权值)v1v2weight; int a=Locatevex(G,v1); int b=Locatevex(G,v2); G.arcsab=weight; G.arcsba=G.arcsab; cout该图的邻接矩阵表示为：n;for(int n=0;nG.vexnum;n+)/输出顶点 coutG.vexsn ;cout(矩阵顶

12、点名称); coutendl; coutendl; for(int x=0;xG.vexnum;x+)/输出邻接矩阵 for(int y=0;yG.vexnum;y+) coutG.arcsxy ; coutendl; coutendl; cout+vexs;allPath.push_back(path); all.push_back(Long); cout路径:path 长度:Long+vexs; int i=Locatevex(G,vexs); visitedi=true; for(int j=0;jG.vexnum;j+) if(!visitedj)&(G.arcsij!=0) Minw

13、ay(G,visited,G.vexsj,Long+G.arcsij,vb,path); visitedi=false; void CountMinway(MGraph G) /该函数调用递归部分实现递归char va,vb;string path; coutva; coutvb;coutendl; int i=Locatevex(G,va);bool visited100;for(int j=0;jG.vexnum;j+)visitedj=false; visitedi=true; int Long=0; path+=va;for( j=0;jG.vexnum;j+)if(G.arcsij!

14、=0)Long=G.arcsij;Minway(G,visited,G.vexsj,Long,vb,path); coutendl;void Minway()/输出最短路径int min=10000;for(int i=0;iallPath.size();i+)if(allimin)min=alli;for(int j=0;jallPath.size();j+)if(allj=min)cout最短路径: allPathj 长度:alljendl;coutendl;void main()CreateUDG(G); /建图CountMinway(G); /找出所有路径Minway(); /输出最短

15、路径 程序描述：通过输入顶点的个数、边的条数和名称以及两点之间的权值得到一个带权值的矩阵。再输入你所处的位置和你要到的位置，程序将通过Floyd算法给出可以到达的路径，并给出最优的路径（即权值最小的路径）。 输入图的顶点个数和边的条数，并输入顶点的名称如图3所示。 图3 数据输入图 输入边的权值，输入格式为边的起点名称 终点名称 和权值，如图4所示。图4 权值的输入 程序自动生成并输出图的邻接矩阵如图5所示。图5 图的邻接矩阵 输入所在的位置和想要去的位置，程序给出可以到达的所以路径及其权值，并给出最短的路径及其权值如图6所示。图6 输出结果总结 图论其实是一门应用数学，它的概念和结果来源非常

16、广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化。非常灵活，常常是一种问题一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。在实际生活中，图论是有很大的利用价值的，应用的范围也很广泛。在教材图论及其算法中就介绍了图论在实际生活中各方面的应用，例如解决中国投递员问题，解决旅行推销员问题，解决七桥问题等。有的时候通过人工计算和处理图论问题很费时费力而且准确性无法保证，所以我们需要将问题抽象出来再进行

17、分析，通过计算机编程实现，在经过调试和修改实现所需要的功能。通过计算机可以快速的处理问题并准确地给出答案。参考文献：1殷剑宏、吴亚开.图论及其算法M.合肥:中国科学技术大学出版社,20052严蔚敏.数据结构（c语言版）M.北京:清华大学出版社,2009高效能学习的八大学习方法方法一：目 标 激 励法 成就天才的必备素质就是远大志向，明确目标，勤奋刻苦，持之以恒，百折不挠。作为一名学生，要想在学习的道路上一路高歌，战胜各科学习困难，在考试中脱颖而出，就必须树立远大的理想，制定明确的学习目标和切实可行的计划，在日常学习中勤奋苦学，孜孜不倦，持之以恒，面对学习中上的挫折，百折不挠，勇往直前，并掌握一

18、套正确的学习方法，科学合理地安排好自己的时间，只有这样，才能到达成功的理想彼岸。 方法二：统筹计划学习法正像建造楼房先要有图纸，打仗先要有部署一样，成功有效的学习也必须制定好一套切实可行的计划。所谓统筹计划学习法，就是学习者为达到一定的学习目标，根据主客观条件而制订学习步骤的一种学习方法。统筹计划学习法包括四个方面：一是学习目标，二是学习内容，三是时间安排，四是保证落实的措施。只有综合考虑这四个方面，才能订出切实可行的规划。同时计划要因人而异，因事而异，并根据执行情况，适当及时调整。方法三：兴趣引导法使学习兴趣化，是获取成功的特别重要的法则。有的同学虽然很努力地学习，但是却对学习没有兴趣。凡是

19、这种情况，学习效率都差得很，往往是事倍功半，效率不高。所以，千万不要只知道积极地去学，光顾着学，傻学，而要想办法培养自己的兴趣。只有将学习积极性转化为学习兴趣之后，你才有可能实现学习效率的飞跃。方法四：高效率学习法 作为学生，谁能够高效地管理时间，科学地利用时间，抓住时间的脉搏，谁就能创造学业的成功，成就人生的辉煌。爱时间就是爱生命，爱生命的每一部分。谁把握住时间，谁就拥有一切。时间就是生命。“一个人一生只有三天：昨天、今天和明天。昨天已经过去，永不复返；今天已经和你在一起，但很快就会过去；明天就要到来，但也会消失。抓紧时间吧，一生只有三天！”现在是你们人生的黄金时期，也是学习知识、吸取知识最

20、有效率的时期，你们应善于管理时间珍惜时间，不虚度年华，使生命失去原本的灿烂光彩。方法五：刨根质疑学习法 学习的过程是由一个“无疑有疑解疑无疑”不断循环往复的过程。学须善思，思后存疑，疑后问，问后知。所以，我们在日常生活和学习过程中，要善于思考，培养“凡事问一个为什么”的习惯。作为一个学生，我们要善于发现问题，敢于向权威挑战，同时又要虚心求教，不耻下问，不懂的问题多问老师，向同学请教。积极参加各种有关学习的交谈、讨论、学习兴趣小组，创设一个与别人交流的良好平台，合作解决问题。方法六：笔 记 学 习法笔墨学习法又称笔记法，是利用记笔记学习的一种方法。在日常的读书、听课、复习的时候，对有一定价值和意

21、义的材料、知识点、问题迅速及时地标记出来，记下来，然后整理成笔记，这对于巩固知识，积累材料，提高学习成绩都具有十分重要的意义。方法七：全 面 预 习法打无准备的仗必输，没有预习的功课一定不会好。要想有一个高效的课堂学习，必须牢牢抓住课前预习这个关键环节。常言道：“凡事预则立，不预则废。”“预”，即准备。预习就是在教师讲课之前，学生阅读教材及相关的内容，为新课学习做好必要的知识准备。我们在预习的时候，要大体了解书本内容，思考重点，发现难点，注意方法，增强预习的主动性、针对性，培养良好的预习习惯。方法八：高 效 听 课法 一个人的学生时代，大部分的学习时间是在课堂中度过的。在短短的十几年时间里每个学生几乎接受和继承了人类几千年所积累的知识中最基本、最精华的部分，由此可见课堂学习的重要性。一个学生学习的好坏，成绩的高低，关键在于课堂学习。充分利用每一节课的45分钟，高效学习，对提高学习质量将产生巨大的影响。专家认为，要想听好一节课，课前必须从身心、知识、物质上做好充分准备，在上课时力求做到“五到”，即耳到、眼到、口到、心到、手到；专心致志，勤于思考，思维与老师合拍。同时，上课时勇于发言，积极参加讨论，有机会多动手、多实践，做好笔记，才能有效地把握课堂，把课堂变成自己学习的主战场。