邻接矩阵在工程上的应用

邻接矩阵在工程上的应用摘要：邻接矩阵作为在图论中常用的思想，不仅仅可以应用于数学研究领域，对于工程领域也起到相当重要的作用，本文主要通过两个例题分析计算机工程中的求解最短路径问题所用到的dijkstra算法和求解最小生成树所用到的prim算法，来剖析这些方法用到的邻接矩阵的思想在解决问题中的重要作用。关键词：最短路径，dijkstra算法，最小生成树，prim算法第1章绪论1.1研究背景及意义随着经济的快速发展，城市化进一步加大，城市规模进一步扩大，人口密度进一步加大。邻接矩阵的应用思想本就是一个寻求资源配置最优化方案的过程，近年来对于资源配置的优化问题成为了许多学者关注的焦点，在经济社会发展中发挥出越来越大的作用。这主要是由于以下两方面的原因，一方面由于可优化的问题所涉及的领域相当广泛，几乎涉及到经济和社会发展的各个方面，例如：工农业生产，工商管理、人力资源管理，交通、应急系统等等；另一方面，在一些问题的解决方案经过优化后，不仅直接高效，而且给社会节省了大量的资源，同时在有限资源的前提下，带来了较大的利益。同时对邻接矩阵这种思想的应用，在解决实际生产生活问题中能够提供行之有效的解决方法。展望未来，社会不断进步，新事物不断出现，国际环境日趋复杂，对于邻接矩阵的应用也会伴随社会发展的步伐与时俱进，不断的融入其他的领域之中，不仅仅限于工程领域，也会逐渐向着农学领域等其他领域进军。1.2研究目的与展望随着新世纪的到来，我国经济正在健康快速的发展，作为“基建狂魔”的中国，其基础设施日益完善，但同时也迎来了许多新的问题。众所周知，资源都是有限的，但由于我国庞大的体量，我国所需要建设的基础设施并不是一笔小数目，其中所需投入的材料以及各种成本多到难以估量，而如何通过合理的设计方案来减少所耗费的各种成本，进一步合理的安排资源减少其浪费，并达到预期的效果和要求，实现效益的最大化，成为了我们日渐关注的话题。因此，本文基于邻接矩阵在图论中的思想，对实际生活中的一些问题进行优化，例如合理的安排行程，减少时间上的损失，又或者是针对一些建设固定设施的铺设提出合理的优化方案减少成本支出，这里以湖南工程学院作为研究单位进一步分析对这些问题的方案优化，以此进一步扩大到城市居民。第2章邻接矩阵的定义及原理简介2.1定义和其特性2.1.1定义邻接矩阵（AdjacencyMatrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}[1]

。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。2.1.2特性无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。2.2原理2.2.1文字介绍邻接矩阵简单来说就是一个表示顶点之间相邻关系的矩阵。若准确的说，邻接矩阵是基于图的用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。（一般而言，我们对图中两个顶点之间存在关系的，其对应的邻接矩阵所对应的行列位置上所赋予为1的数，不存在关系则赋值0，方便一眼能够清晰明了）由于邻接矩阵是基于图，并将存放在数组中的图的数据具体化表现出来的一种形式，所以我们很轻松的就看出顶点之间的相互关系，很容易确定图中任意两个顶点是否有边相连，故我们常常遇到一些复杂的图理不清其关系时往往会用到它。2.2.2图示介绍由图可以看出顶点之间的关系，但是想将其存入计算机并转换为计算机可识别的语言该如何实现呢？首先，我们是把顶点存在一维数组中，那么他们的关系存在在二维数组中，就好像是如下格式(下方1为有关系，0为没有关系，未加入权值)。若每条边加入权值，则顶点之间相应的关系为1则替换为其边的权值。例如A->C的权值为5，B->C的权值为5，A->D的权值为10，B->D的权值为10，C->E的权值为15，D->E的权值为15，则为以下格式。（0依旧代表该边相邻两节点之间没关系）第3章相关算法的介绍3.1最短路径（动态规划）3.1.1Dijkstra（迪杰斯特拉)算法1.算法基本思想：Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v1放入S,集合S每并入一个新顶点，都要修改源点V0到集合V-S中顶点当前的最短路径长度值。在构造的过程中还设置了两个辅助数组：• dist[]：记录从源点V0到其他各顶点当前的最短路径长度，它的初态为：若从v0到v1有弧，则为弧上的权值；否则置dist⑴为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.Dijksfra算法的步骤（不考虑对path[]的操作）：（1） 初始化：集合S初始为{0},dist[]的初始值dist[i]=arcs[0][i],i=l,2,...,n-l。（2） 从顶点集合V-S中选出，满足dist[j]=Min{dist[i]|vi∈V-S},vj就是当前求得的一条从v0出发的最短路径的终点，令S=S∪{j}。（3） 修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：若dist[j]+arcs[j][k]<dist[k],则更新dist[k]=dist[j]+arcs[j][k]。（4） 重复（2）〜（3）操作共n-1次，直到所有的顶点都包含在S中。3.2最小生成树3.1.2Prim算法1.算法思想：简单来说这个算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里，最终使得所有顶点连通，并且边权值之和达到最小的时候，一个带权无向图的最小生成树就求出来了。

2.算法步骤：

（1）将V0到其他顶点的所有边当作候选边；（2）重复以下步骤n-1次，使得其他n-1个顶点被并入到生成树中。①从候选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中；②考査所有剩余顶点Vi，如果（V,Vi）的权值比lowcost[i]（lowcost[i]保存的是当前生成树到顶点i的多条边中最短的一条边的权值）小，则用（V,Vi）的权值更新lowcost[i]。第4章例题分析4.1（邻接矩阵在带权有向无环图中求单源最短路径）从湖南工程学院出发（V1），途经各个公交站点（由于公交站点数量众多，我们仅选择少数站点，5个点，作为代表分析）,最终到达湘潭火车站（V5）,由于在疫情期间，人们尽量遵循少乘坐公共交通的原则，故选择步行或者骑行方式，在该情况下，若要得到从湖南工程学院到火车站的所有出行方案中路径长度最短的那一个，并求出求出其最短路径方案所经过的站点（含源点和终点），我们该如何分析所有情况来获取路径最短的那一个方案？解：（1）首先将采集相关的信息，如站点以及站点之间的距离等信息，并构建出一个图来表示它们之间的关系。（权值数字1：100，单位：米）（2）构建邻接矩阵（1代表v1,以此类推），直观表示顶点间的关系。（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，停止迭代顶点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}表3.1.1从起点v1到各点的dist值和最短路径的求解过程注：路径下方的数字，是起点到目标顶点的路径长度。（4）结果测试4.2（邻接矩阵在带权连通无向图中求最小生成树）为了更方便的解决学生饮水以及饮水的安全问题，学校曾做过一个是否对每一栋楼铺设直饮水管道的调查，如果学校确定对每一栋楼铺设直饮水管道，我们应该如何合理的设计其铺设的路线，使铺设管道材料的成本达到最低，在这里我们仅将湖南工程学院新校区明德楼作为试点（由于明德楼两栋楼一般靠在一起，故两栋则看作一个点，一共有5个点，5个点之间相互连通的连通图）如何以最小的材料成本（仅考虑该因素）使得每个点相互连通？解：设顶点1代表明德1,2栋，顶点2代表明德3,4栋，顶点3代表明德5,6栋，顶点4代表明德7,8栋，顶点5代表明德9,10栋。获取顶点以及其之间的距离等相关信息，构建一个无向连通图。(权值单位：米)构建邻接矩阵操作步骤a.以顶点1为起始点，根据贪心策略选择与已知点关联的最短代价边，由邻接矩阵直观的得到第1行第2列的值最小，则1的后继节点为2，1-2为最小代价边。b.此时，顶点2为新的起始节点，接下来寻找与顶点2相邻的最小代价边，由（2）中给出的邻接矩阵知道，第2行第1列和第3列的值最小，但由于1-2边已被选中，故排除该选项，则最小的值在第2行第3列上，得到2的后继节点为3，2-3为与顶点2相邻的最小代价边。c.此时，顶点3为新的起始节点，接下来寻找与顶点3相邻的最小代价边，这时可先排除已选中的边1-2和2-3，以免对后面的计算造成一定的干扰，由于顶点3为前驱节点，我们可直接从邻接矩阵的第3行进行寻找，寻得第3行第4列的值最小，故得到3的后继节点为4，3-4为与顶点3相邻的最小代价边。d.同理，寻得与顶点4相邻的最小代价边4-5，4的后继节点为5，由于此时顶点之间刚好连通，故停止继续寻找，得到了该图的最小生成树，各最小代价边分别为1-2（50），2-3（50），3-4（100），4-5（50），最小生成树的长度为250。结果测试总结本论文从当下工业迅速发展的背景下，简单阐述了邻接矩阵在工程领域上的应用，并介绍了何为邻接矩阵，以及邻接矩阵的特性和原理。再通过几个与学生生活中息息相关的例题，分析了邻接矩阵在解决这些日常生活中问题的妙用。方便读者通过本论文对邻接矩阵以及其作用有个基本的了解，能够清楚的认识到邻接矩阵的这种思想是不仅仅在数学中被应用，在实际的工程领域中，尤其是相关的优化问题中，也时常出现。由于本文作者水平有限，仅能窥探至入门之径，有些概念不能清晰的展现出来，并且本文还有许多不足和需要改进的地方，望谅解。附录例题3.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;}例题3.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];p[