邻接矩阵在工程上的应用

邻接矩阵在工程上的应用摘要：邻接矩阵作为解决图论问题中常用的一种方法，不仅仅可以应用于数学研究领域，对于工程领域也起到相当重要的作用。本文主要是通过计算机工程中的求解最短路径问题所用到的Dijkstra算法和求解最小生成树所用到的prim算法，分别解决从湖南工程学院到湘潭火车站的一个最优出行方案的选择问题和引水管道的最小成本铺设方案问题。在使用Dijkstra算法和Prim算法的过程时，主要是用邻接矩阵的存储方式来存储图的相关信息，但是在使用Prim算法的过程中，我直接通过邻接矩阵的图解一步步迭代来得到直接得到最小生成树，但是这个方法仅仅对于顶点和边比较少的图实用性比较大，对于顶点和边比较多且复杂的网络图并不适用。通过剖析这些算法我发现，许多优化的方案实际上都是用到了相关邻接矩阵的理论。关键词：最短路径，Dijkstra算法，最小生成树，prim算法ApplicationofAdjacencyMatrixinEngineeringAbstract:Asacommonmethodtosolvegraphtheoryproblems,adjacencymatrixcannotonlybeappliedinthefieldofmathematicalresearch,butalsoplaysaveryimportantroleinthefieldofengineering.Inthispaper,theDijkstraalgorithmusedtosolvetheshortestpathproblemandtheprimalgorithmusedtosolvetheminimumspanningtreeincomputerengineeringaremainlyusedtosolvetheproblemofselectinganoptimaltravelschemefromHunanInstituteofEngineeringtoXiangtanRailwayStationandtheproblemoflayingthewaterdiversionpipelineattheminimumcostrespectively.IntheprocessofusingDijkstraalgorithmandPrimalgorithm,theadjacencymatrixismainlyusedtostoretherelevantinformationofthegraph.However,intheprocessofusingPrimalgorithm,Idirectlygettheminimumspanningtreebyiteratingstepbystepthroughthediagramoftheadjacencymatrix.However,thismethodismorepracticalonlyforgraphswithfewerverticesandedges,andisnotsuitablefornetworkgraphswithmoreverticesandedgesandmorecomplex.Byanalyzingthesealgorithms,Ifindthatmanyoptimizationschemesactuallyusethetheoryofrelatedadjacencymatrix.Keywords:shortestpath,Dijkstraalgorithm,minimumspanningtree,primalgorithm目录TOC\o"1-3"\h\u8848第1章绪论 76321.1研究背景及意义 7268771.2研究目的与展望 73490第2章邻接矩阵的定义及原理简介 856972.1定义和其特性 8233402.2原理 8268222.2.1文字介绍 82102.2.2图示介绍 913393第3章相关算法的介绍 11113573.1最短路径（动态规划） 11154413.1.1Dijkstra（迪杰斯特拉)算法 11217901.算法基本思想： 11240422.Dijkstra算法的步骤（不考虑对path[]的操作）： 116043.2最小生成树 12284693.1.2Prim算法 125648第4章算法的实际应用 1395984.1最优路径方案的选择 13180844.2饮水管道的铺设问题 158851（1）获取顶点以及其之间的距离等相关信息，构建一个无向连通图。(权值单位：米) 161939（2）构建邻接矩阵 162395（3）操作步骤 1724602（4）结果测试 1915435例题4.1代码实现： 2226712例题4.2代码实现： 2415487总结 2810387致谢 29第1章绪论1.1研究背景及意义随着中国经济发展的越加快速，城市化的步子进一步加大，城市规模不断扩大，人口密度进一步加大。邻接矩阵的应用思想本就是一个寻求资源配置最优化方案的过程，近年来对于资源配置的优化问题成为了国家关注的焦点，并且在经济社会发展中发挥出越来越大的作用。这主要是由于以下两方面的原因，一方面由于可优化的问题所涉及的领域相当广泛，几乎涉及到经济和社会发展的各个方面，例如：工农业生产，工商管理、人力资源管理，交通、应急系统等等；另一方面，在一些问题的解决方案经过优化后，不仅直接高效，而且给社会节省了大量的资源，同时在有限资源的前提下，带来了较大的利益。同时对邻接矩阵这种思想的应用，在解决实际生产生活问题中能够提供行之有效的解决方法。展望未来，社会不断进步，新事物不断出现，国际环境日趋复杂，对于邻接矩阵的应用也会伴随社会发展的步伐与时俱进，不断的融入其他的领域之中，不仅仅限于工程领域，也会逐渐向着农学领域等其他领域进军。[1]1.2研究目的与展望随着新世纪的到来，我国经济正在健康快速的发展，作为“基建狂魔”的中国，其基础设施日益完善，但同时也迎来了许多新的问题。众所周知，资源都是有限的，但由于我国庞大的体量，我国所需要建设的基础设施并不是一笔小数目，其中所需投入的材料以及各种成本多到难以估量，而如何通过合理的设计方案来进行运筹优化进而减少所耗费的各种成本，进一步合理的安排资源减少其浪费，并达到预期的效果和要求，实现效益的最大化，成为了我们日渐关注的话题。[2][3]因此，本文基于邻接矩阵在图论中的思想，对实际生活中的一些问题进行优化，例如合理的安排行程，减少时间上的损失，又或者是针对一些建设固定设施的铺设提出合理的优化方案减少成本支出，这里以湖南工程学院作为研究单位进一步分析对这些问题的方案优化，以此进一步扩大到城市居民。第2章邻接矩阵的定义及原理简介2.1定义和其特性邻接矩阵（AdjacencyMatrix）主要是表示节点之间相邻关系的矩阵。假设设G=(V,E)是一个图，其中V={v1,v2,…,vn}。[4]图G的邻接矩阵是一个具有下列性质的n阶方阵[5]：①如果图G是一个无向图，则其邻接矩阵一定是对称的，而且主对角线一定为0（0指的是没有关系，避免自身成环的情况），而副对角线就不一定为0；如果图G是一个有向图，由于它的指向边权值可能不一样，故有向图的邻接矩阵不一定对称。②如果图G是一个无向图，随便一个顶点（例如i）的度为第i列（或第i行）所有非0元素的总个数；如果图G是一个有向图，则随便一个顶点（例如i）的出度为第i行所有非零元素的个数，而它的入度为第i列所有非零元素的总个数。③如果图G是一个无向图，那么它的邻接矩阵一定对称，所以除了对角线的值都为0外，邻接矩阵仅需要存储上三角形或者下三角形的数据集就可以了，因此邻接矩阵法表示图仅需要n（n-1）/2个空间；如果图G是一个有向图，因为不能保证两点之间是否有两条来回的有向边或者两条有向边的权值不一样，所以有向图的邻接矩阵法表示图需要n^2个空间。2.2原理2.2.1文字介绍邻接矩阵理解起来不是别困难，简单来说就是一个矩阵，再精确一点就是一个表示顶点之间相邻关系的矩阵，又或者说看顶点之间是否有边，边的权值又是多少。若是准确的来说，用数据结构的语言来讲，邻接矩阵就是基于图的用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。[6]（一般而言，我们对图中两个顶点之间存在关系的，其对应的邻接矩阵所对应的行列位置上所赋予为1的值，不存在关系则赋值0，方便一眼能够清晰明了）由于邻接矩阵是基于图，并将存放在数组中的图的数据具体化表现出来的一种形式，所以我们很轻松的就看出顶点之间有什么样的关系，故我们常常遇到一些复杂的图理不清其关系时往往会用到它。2.2.2图示介绍图2.2.1有向图的示例由图可以看出顶点之间的关系，但是想将其存入计算机并转换为计算机可识别的语言该如何实现呢？首先，我们是把顶点集存放在一维数组中，将他们之间的关系存放在二维数组中，比如以下图的格式(下方1为有关系，0为没有关系，未加入权值)。图2.2.2示例有向图的边之间的关系矩阵图若每条边加入权值，则顶点之间相应的关系为1则替换为其边的权值。例如A->C的权值为5，B->C的权值为5，A->D的权值为10，B->D的权值为10，C->E的权值为15，D->E的权值为15，则为以下格式。（0依旧代表该边相邻两节点之间没关系）图2.2.3加入权值后的示例有向图的边之间的关系矩阵图第3章相关算法的介绍3.1最短路径（动态规划）3.1.1Dijkstra（迪杰斯特拉)算法1.算法基本思想：Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v1放入S,集合S每并入一个新顶点，都要修改源点V0到集合V-S中顶点当前的最短路径长度值。[7]• 设置一个辅助的数组dist[]：记录从源点到其他各个顶点的目前的最短路径长度的值，它的初始状态为：若从v0到v1有边，则为边上的权值；否则将dist[1]置为0。• 设置一个辅助的数组path[]:path[i]表示从源点到顶点f之间的最短路径的前驱结点。并且当这个算法结束时，可根据该数组存储的值往回追溯，得到从源点V0到顶点Vi的最短路径。假设从顶点V0出发，即顶点V0为顶点O（在程序中定义为整型数组比较方便），集合S最初只包含顶点0,用邻接矩阵arcs存储带权有向图的信息，arcs[i][j]存储有向边＜i,j＞的权值，若不存在有向边＜i,j＞,则arcs[i][j]的值为0。2.Dijkstra算法的步骤（不考虑对path[]的操作）：（1） 初始化：集合S初始为{0},dist[]的初始值dist[i]=arcs[0][i],i=l,2,...,n-l。（2） 从顶点集合V-S中选出一个顶点j，v0到vj的路径最短,vj就是目前的一条从v0开始出发的最短路径的终点，将顶点j并入集合S之中。（3） 更新从v0出发到集合（V-S）中任一一个顶点vk可达到的最短路径的长度：若dist[j]+arcs[j][k]的值小于dist[k]值,则新的dist[k]值等于dist[j]+arcs[j][k]的值。（4） 重复（2）和（3）这样类似的操作，直到集合S包含所有的顶点，则结束迭代。3.2最小生成树3.1.2Prim算法1.算法思想：初始最小生成树边数为0，我们按照贪心算法的原则，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里，并在前面的基础上继续进行同理的迭代，直到所有的顶点连通，并且边权值之和达到最小的时候，一个带权无向图的最小生成树就求出来了。[8][9][10]2.算法步骤：

（1）从V0开始，将其加入原始的最小生成树中（原始最小生成树为空），在所有与顶点V0相邻的边中，选取权值最小的那条边加入最小生成树中，同时与这条权值最小的边的另一个顶点加入该最小生成树中，以这个顶点为新的初始点。（2）从新的初始点出发，在所有与新初始点相邻的边中，选取权值最小的那条边加入最小生成树中，同时与这条权值最小的边的另一个顶点加入该最小生成树中，以这个顶点为新的初始点，以此类推，直到所有顶点连通或者边数达到n-1条，则结束迭代。第4章算法的实际应用4.1最优路径方案的选择从湖南工程学院出发（V1），途经各个公交站点（由于公交站点数量众多，我们仅选择少数站点，5个点，作为代表分析）,最终到达湘潭火车站（V5）,由于在疫情期间，人们尽量遵循少乘坐公共交通的原则，故选择步行或者骑行方式，在该情况下，若要得到从湖南工程学院到火车站的所有出行方案中路径长度最短的那一个，并求出求出其最短路径方案所经过的站点（含源点和终点），我们该如何分析所有情况来获取路径最短的那一个方案？问题分析：该问题是一个典型的在带权有向无环图中求单源最短路径的问题。根据前面理论的分析，利用Dijkstra算法，选择邻接矩阵的存储方式来实现对数据的存储问题。[11][12][13][14][15]首先将采集相关的信息，如站点以及站点之间的距离等信息，并构建出一个图来表示它们之间的关系。（权值数字1：100，单位：米）图4.1.1表示站点之间关系的带权有向图构建邻接矩阵（1代表v1,以此类推），直观表示顶点间的关系。图4.1.2表示有向图中顶点与边之间的关系以及相应边的权值大小的矩阵图（3）操作步骤初始时，S中只有起点V1(即S={V1})。每轮得到的最短路径如下：第一轮：V1->V2的距离最短，将顶点V2加入S，此时最短路径的长度为4第二轮：在上一轮的最短路径的基础上，V1->V2->V3的距离最短，将顶点V3加入S，此时最短路径的长度为10第三轮：在上一轮的最短路径的基础上，V1->V2->V3->V4的距离最短，将顶点V4加入S，此时最短路径的长度为15第四轮：在上一轮的最短路径的基础上，V1->V2->V3->V4->V5的距离最短，将顶点V5加入S，此时最短路径的长度为26,此时火车站终点V5已加入S，停止迭代表4.1.3从起点v1到各点的dist值和最短路径的求解过程顶点V2V3V4V5集合S第1轮V1->V24V1->V312\\{V1,V2}第2轮\V1->V2->V310V1->V2->V424\{V1,V2,V3}第3轮\\V1->V2->V3->V415V1->V2->V3->V538{V1,V2,V3,V4}第4轮\\\V1->V2->V3->V4->V526{V1,V2,V3,V4,V5}注：路径下方的数字，是起点到目标顶点的路径长度。（4）结果测试图4.1.4最短路径的代码实现结果图4.2饮水管道的铺设问题为了更方便的解决学生饮水以及饮水的安全问题，学校曾做过一个是否对每一栋楼铺设直饮水管道的调查，如果学校确定对每一栋楼铺设直饮水管道，我们应该如何合理的设计其铺设的路线，使铺设管道材料的成本达到最低，在这里我们仅将湖南工程学院新校区明德楼作为试点（由于明德楼两栋楼一般靠在一起，故两栋则看作一个点，一共有5个点，5个点之间相互连通的连通图）如何以最小的材料成本（仅考虑该因素）使得每个点相互连通？问题分析：这是一个典型的在带权连通无向图中求最小生成树的问题，这里选择专门用于求解该类问题的Prim算法，这里的最小生成树从无边的五个顶点开始，依照邻接矩阵给出的关系，一步一步迭代，每次迭代多一条最短代价边，直到最小生成树中的顶点相互连通。[16][17][18][19][20][21]获取顶点以及其之间的距离等相关信息，构建一个无向连通图。(权值单位：米)图4.2.1饮水管道所有可能铺设的带权无向线路图注：顶点1代表明德1,2栋，顶点2代表明德3,4栋，顶点3代表明德5,6栋，顶点4代表明德7,8栋，顶点5代表明德9,10栋。构建邻接矩阵图4.2.2表示明德楼之间的关系以及距离操作步骤a.以顶点1为起始点，根据贪心策略选择与已知点关联的最短代价边，由邻接矩阵直观的得到第1行第2列的值最小，则1的后继节点为2，1-2为最小代价边。图4.2.3最小生成树的第一次迭代图b.此时，顶点2为新的起始节点，接下来寻找与顶点2相邻的最小代价边，由（2）中给出的邻接矩阵知道，第2行第1列和第3列的值最小，但由于1-2边已被选中，故排除该选项，则最小的值在第2行第3列上，得到2的后继节点为3，2-3为与顶点2相邻的最小代价边。图4.2.4最小生成树的第二次迭代图c.此时，顶点3为新的起始节点，接下来寻找与顶点3相邻的最小代价边，这时可先排除已选中的边1-2和2-3，以免对后面的计算造成一定的干扰，由于顶点3为前驱节点，我们可直接从邻接矩阵的第3行进行寻找，寻得第3行第4列的值最小，故得到3的后继节点为4，3-4为与顶点3相邻的最小代价边。图4.2.5最小生成树的第三次迭代图d.同理，寻得与顶点4相邻的最小代价边4-5，4的后继节点为5，由于此时顶点之间刚好连通，故停止继续寻找，得到了该图的最小生成树，各最小代价边分别为1-2（50），2-3（50），3-4（100），4-5（50），最小生成树的长度为250。图4.2.6最小生成树的第四次迭代图结果测试图4.2.7最小生成树的顶点路径以及长度图参考文献王雅婧.运筹学在工程管理中的应用[J].建设监理,2018(06):42-45.高洁.利用运筹学方法谈高职教育发展的模式和前景[D].延边大学,2010.卡普斯京,李国海.运筹学:问题与前景[J].现代外国哲学社会科学文摘,1998(11):39-40.张英丽,顾玉宛,解世艳,曹黎.树的邻接矩阵[J].江苏工业学院学报,2009,21(02):47-49.于兰芳.图的矩阵表示及性质[J].承德民族师专学报,2006(02):11-13.达文姣,郭珍,任志国,石旺峰.基于邻接矩阵存储结构的二元关系的合成运算[J].甘肃高师学报,2013,18(05):10-11.贾敬霞,王振宇,何孝敏,付稳稳.基于C语言的迪杰斯特拉算法仿真与实现[J].电脑编程技巧与维护,2020(03):9-11.王敏,杨秀香,李云飞.基于邻接矩阵的近似Prim算法解决无向图特定问题[J].渭南师范学院学报,2015,30(22):35-38.王化宇.最小生成树算法及其应用[J].内蒙古科技与经济,2011(06):72-73.孙培,刘凯.最小生成树问题的数学模型及其证明[J].电脑知识与技术,2014,10(28):6682-6684.李楠,邹晓松,孙志勇,王森.基于改进Dijkstra算法的配电网网架扩展规划[J].电力科学与工程,2020,36(04):38-43.车建涛,高方玉,解玉文,李端玲,牛坤,马士恩.基于Dijkstra算法的水下机器人路径规划[J].机械设计与研究,2020,36(01):44-48.邹佰翰,张吉懿,苑晓兵.最短路径算法在计算机网络路由选择中的应用研究[J].电声技术,2020,44(02):59-60+70.刘喜勋,何苗.一边多权图的邻接矩阵实现技术和Dijkstra算法的改进[J].自动化与仪器仪表,2016(07):186-189.赵艳丽.实际路网最短路径算法优化与实现[D].华南理工大学,2015.Science-OperationsScience;ResearchersfromTechnicalUniversityClujNapocaProvideDetailsofNewStudiesandFindingsintheAreaofOperationsScience(Thegeneralizedminimumspanningtreeproblem:Anoverviewofformulations,solutionproceduresandlatestadvances)[J].ScienceLetter,2020.[17]杨晶,张兆鑫,王鹏.最小生成树算法在城市基础建设中的应用[J].电子测试,2015(02):37-38+36.[18]梁西陈.最小生成树在网络设计中的应用[J].宿州教育学院学报,2008(02):150-152.[19]李建军,沈啸林,陈明贺,刘硕,陈舒研.基于最小生成树算法的怀柔区快递站点选址问题研究[J].南方农机,2019,50(01):91-93.[20]刘朝霞.改进的Prim算法在求解旅行商问题中的应用[J].阴山学刊(自然科学版),2015,29(01):8-10+19.[21]薛春艳.最小生成树在城市高速公路问题中的应用[J].电脑编程技巧与维护,2009(06):30-31+60.附录例题4.1代码实现：#include<cstdio>usingnamespacestd;#definemax10000#defineinf20000intn,e;//顶点数n，边的条数eintcost[20][20]; //邻接矩阵intdist[20];//存储最短路径的长度值intpre[20];//存储一个顶点在其最短路径的前趋intS[20];//标志数组，若为已经找到最短路径的结点则为1,否则为0voidDijkstra(intv){ for(inti=0;i<n;i++){ dist[i]=cost[v][i];//初始化 S[i]=0;//标志位初始为0 if(dist[i]<max) pre[i]=v;//若存在边，则前趋为原点 else pre[i]=-1;//否则，前趋为-1,不可达 } S[0]=1;//原点标志为1 for(inti=0;i<n-1;i++){//循环n-1次 intu;//u为待选顶点 intmin=inf;//令初始最小值>max，使距离值为max的顶点也能加到S中 for(intj=0;j<n;j++){ if((!S[j])&&dist[j]<min){//寻找距离S最小的顶点u min=dist[j]; u=j; } } S[u]=1;//将其标志设置为1 for(intk=0;k<n;k++){//调整未加入S的点的的距离值 if((!S[k])&&dist[k]>dist[u]+cost[u][k]){ dist[k]=dist[u]+cost[u][k]; pre[k]=u;//若通过u减小了k的距离，则修改k的前趋为u } } } printf("\nTheresult:\n");//输出结果 for(inti=0;i<n;i++){ printf("<%d,%d>:",v+1,i+1); intp=pre[i]; if(p!=-1){//若可达输出最短路径 printf("%d",dist[i]);//输出最短距离 printf("%d",i+1);//根据前趋逆向输出最短路径 while(p!=v){ printf("<--%d",p+1); p=pre[p]; } printf("<--%d",v+1); } else{//若不可达则输出“inf” printf("inf"); } printf("\n"); }}intmain(){ printf("请输入顶点数目和边的数目:"); scanf("%d%d",&n,&e); for(inti=0;i<n;i++) for(intj=0;j<n;j++) cost[i][j]=max;//初始化为max intstart,end,dut; printf("请输入各边的始点，终点，权值：\n"); for(inti=0;i<e;i++){ scanf("%d%d%d",&start,&end,&dut);//输入边的始点，终点和权值 start--; end--;//结点号与存储的下标相差1 cost[start][end]=dut; } intv=0; Dijkstra(v);//以顶点1（即下标为0）为原点v return0;}例题4.2代码实现：#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>usingnamespacestd;constintmaxn=1005;constintINF=0x3f3f3f3f;intp[maxn];//储存父节点intedge[maxn][maxn];//邻接矩阵intd[maxn];//到生成树的最短距离intvis[maxn];//是否加入集合中intn,m;voidinit()//初始化{memset(vis,0,sizeof(vis));memset(p,-1,sizeof(p));for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)i==j?edge[i][j]==0:edge[i][j]=INF;}voidprim(){//以1作为根节点for(inti=1;i<=n;i++){if(edge[1][i]!=INF)p[i]=1;d[i]=edge[1][i];}while(1){intmaxx=INF;intu=-1;for(inti=1;i<=n;i++)//找到距离生成树最短距离的节点{if(!vis[i]&&d[i]<maxx){maxx=d[i];u=i;}}if(u==-1)break;//将选出的节点纳入集合vis[u]=1;for(inti=1;i<=n;i++)//更新该节点影响的节点{if(!vis[i]&&d[i]>edge[u][i]){d[i]=edge[u][i];