莱芜哪里做网站,代做预算网站,南京网站建设费用,长沙市装配式建筑信息平台图论算法图论算法在计算机科学中扮演着很重要的角色#xff0c;它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题#xff0c;然后用图论的基本算法加以解决。这类问题算法主要包括Dijkstra#xff0c;Floyd#xff0c;Prim#xff0c;最… 图论算法图论算法在计算机科学中扮演着很重要的角色它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题然后用图论的基本算法加以解决。这类问题算法主要包括DijkstraFloydPrim最短路、网络流、二分图等算法。 背景 哥尼斯堡(KOnigsberg)七桥问题在哥尼斯堡的一个公园里有七座桥将河中两个岛及岛与河岸连接起来问是否可能从这四块陆地中任一块出发恰好通过每座桥一次再回到起点。1736年在经过一年的研究之后29岁的欧拉提交了《哥尼斯堡七桥》的论文圆满解决了这一问题同时开创了数学新一分支---图论。七桥问题在论文中欧拉将七桥问题抽象出来把每一块陆地考虑成一个点连接两块陆地的桥以线表示。并由此得到了如图一样的几何图形。 若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复地画出过此七条线的问题了。若可以画出来则图形中必有终点和起点并且起点和终点应该是同一点由于对称性可知由B或C为起点得到的效果是一样的若假设以A为起点和终点则必有一离开线和对应的进入线若我们定义进入A的线的条数为入度离开线的条数为出度与A有关的线的条数为A的度则A的出度和入度是相等的即A的度应该为偶数。即要使得从A出发有解则A的度数应该为偶数而实际上A的度数是5为奇数于是可知从A出发是无解的。同时若从B或D出发由于B、D的度数分别是3、3都是奇数即以之为起点都是无解的。由上述理由可知对于所抽象出的数学问题是无解的即“七桥问题”也是无解的。由此我们得到:欧拉回路关系(对于一个连通图通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。)可知要使得一个图形可以一笔画必须满足如下两个条件1. 图形必须是连通的。2. 图中的“奇点”个数是0或2。 引进概念 图二元组G(VE)称为图(graph)。V为顶点(vertex) 或结点(node)的集。E为图中边的集合。•点用数字0...n-1表示•点对(uv)称为边(edge)或称弧•子图(subgraph)边的子集和相关联的点集•带权图可以给边加权(weight)成为带权图或加权图(weightedgraph).权通常代表费用、距离等可以是正数也可以是负数•有向图边都是单向(unidirectional)的因此边(uv)是有序数对.(最基本的图通常被定义为“无向图”与之对应的则被称为“有向图”。两者的区别在于有向图中的边是有方向性的。下图即是一个有向图边的方向分别是(1-2), (1- 3), (3- 1), (1-5), (2-3), (3-4), (3-5), (4-5), (1-6), (4-6)。注意图中的边(1-3)和(3-1)是不同的。有向图和无向图的许多原理和算法是相通的。)有时用弧(arc)专指有向边 有时用弧(arc)专指有向边•一条路径(path)是一个结点序列路上的相邻结点在图上是邻接的•如果结点和边都不重复出现则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边称为圈(cycle).•不相交路(disjoint path)表示没有除了起点和终点以外的公共点的路.更严格的全图N个顶点的图有N(N-1)/2个节点于(uv)若邻接则改为非邻接若非邻接则改为邻接得到的图原图的补图生成树•树N个点N-1条边的连通图(无环连通图)•生成树包含某图G所有点的树•一个图G是树当且仅当以下任意一个条件成立 G有V-1条边无圈 G有V-1条边连通 任意两点只有唯一的简单路径 G连通但任意删除一条边后不连通 最短路问题 对一幅图G我们对每一条边赋权w(e)成为一个赋权图。H是G的一个子图则W(H) sigma(w(e)),也就是对每条边的权求和。寻找从一个点a到另一个b的一个子图使得权和最小即为最短路问题。解法一Dijkstra算法(仅适用于无负权边的情况)把顶点集合V分成两组•(1)S已求出的顶点的集合(初始时只含有源点VO)•(2)V-ST尚未确定的顶点集合将T中顶点按递增的次序加入到S中保证•(1)从源点VO到S中其他各顶点的长度都不大于从VO到T中任何顶点的最短路径长度•(2)每个顶点对应一个距离值•S中顶点距离从VO到此顶点的最短距离•T中顶点距离从V0到此顶点的只包括S中顶点作中间顶点的算法图解:不断求一个点集合中的每个点和与他相邻点最短路的最小值。我们还是从实例出发更容易讲解。求下面这个图从A到L的最短路。(1)令a1 A(便于标记),t(a1) 0(表示点a1到a的最短路)S{a1}(被选择的点的集合)T 0(空集 表示被选择的最短路的边集)。(2)求与S中的点a1与他相邻的点的距离d取点a2 C使得距离最小。令S{a1,a2}T{AC}。(3)重复第二步求S中的点a1,a2的相邻点中(去除已选择点)距离最小的那个则为ABCE。再取ABCE中权和最小的一个B所以a3B,令S{a1,a2,a3}T{AC,AB}。…持续下去不断寻找S集合中的每个点与他相邻点的最小距离然后在这些最小距离中找到最小的那个加入到S中同时加入相应的边。直到到达终点L为止。最后得到的最短路为此算法是多项式时间可求解的。解法二Floyd算法(插点法)Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法可以正确处理有向图或负权的最短路径问题。算法思想原理Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题我们需要为这个目标重新做一个诠释。从任意节点i到任意节点j的最短路径不外乎2种可能1是直接从i到j2是从i经过若干个节点k到j。所以我们假设Dis(i,j)为节点u到节点v的最短路径的距离对于每一个节点k我们检查Dis(i,k) Dis(k,j) Dis(i,j)是否成立如果成立证明从i到k再到j的路径比i直接到j的路径短我们便设置Dis(i,j) Dis(i,k) Dis(k,j)这样一来当我们遍历完所有节点kDis(i,j)中记录的便是i到j的最短路径的距离。算法描述暑假小哼准备去一些城市旅游。有些城市之间有公路有些城市之间则没有如左图。为了节省经费以及方便计划旅程小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程也就是求任意两个点之间的最短路径。我们可以用一个4*4的矩阵(二维数组e)来存储。比如1号城市到2号城市的路程为2则设e[1][2]的值为2。2号城市无法到达4号城市则设置e[2][4]的值为∞。另外此处约定一个城市自己到自己的路程也是0例如e[1][1]为0。如果求任意两点之间的最短路径两点之间可以直接到达但却不是最短的路径要让任意两点(例如从顶点a点到顶点b)之间的路程变短只能引入第三个点(顶点k)并通过这个顶点k中转即a-k-b才可能缩短原来从顶点a点到顶点b的路程。每个顶点都有可能使得另外两个顶点之间的路程变短。当任意两点之间不允许经过第三个点时这些城市之间最短路程就是初始路程。在只允许经过1号顶点的情况下任意两点之间的最短路程更新为在只允许经过1号顶点的情况下只需判断e[i][1]e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]e[1][j]表示的是从i号顶点先到1号顶点再从1号顶点到j号顶点的路程之和。其中i是1~n循环j也是1~n循环接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。我们需要在只允许经过1号顶点时任意两点的最短路程的结果下再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]e[2][j]是否比e[i][j]要小在只允许经过1和2号顶点的情况下任意两点之间的最短路程更新为判断e[i][2]e[2][j]是否比e[i][j]要小。同理继续在只允许经过1、2和3号顶点进行中转的情况下求任意两点之间的最短路程。任意两点之间的最短路程更新为最后允许通过所有顶点作为中转任意两点之间最终的最短路程为 最小生成树问题 同样在一个连通赋权图中寻找一颗生成树使得权和最小。Kruskal算法(避圈法)(1)在G中选取最小权边e并置边数i1(2)当in-1时结束否则转向(3)(3设已选择的边为ee2.e在G中选不同于ee2.e的边e;1使得e是满足与ee...e不构成回路且权值最小的边(4)置为i1转向(2)。不断寻找最小权的边即可。比如寻找下图的最小生成树结果如下 网络流问题 如下图所示有一个顶点称为源点(source)还有一个顶点称为汇点(sink)。对于顶点它最大流出2因此它的最大流入为2如下右图所示。而他的最大流也就是5。要想计算最大流同样可是使用前面的思想——分阶段进行。令开始时所有边都没有流如下中间图所示。我们可以用残余图(residual graph)来表示对于每条边还能再添加上多少流。对于每一条边可以从容量中减去当前的流而计算出残留的流。第一步假设我们选择路径此时会发出2个单位的流通过这条路径的每一边如下中间图所示。对比左图我们做如下约定一旦注满(使饱和)一条边例如到和到就将这条边从残余图(也就是中间图)去掉如下右图所示。第二步接下来选择路径此时也会发出2个单位的流通过这条路径的每一边如下中间图所示。同样将残余图更新如下右图所示。第三步从上图的残余图中我们已经可以看出来最后一步的唯一一种走法了。做如下图所示更新。很显然无法走到因此算法至此便终止了。因此正好5个单位的流是最大值。如果一开始我们选择了如下图中间所示的走法那么算法就会失败了因为路已经被堵死了。为了使算法得以成功运作那么就要让流图中具有以相反方向发送流的路径如下所示。那么对于如下右图中的残余图而言从d返回到a的便成了3而非4这是因为从t流到d的流量是3个单位。现在在残余图中就有a和d之间有2个方向或者还有1个单位的流可以从导向或者是3个单位的流导向相反的反向当然我们也可以撤销流。紧接着如果通过到导入2个单位的流算法就会从边取走2个单位的流更新流图如下。参考1.《数据结构》、《离散数学》、《算法导论》、《挑战程序设计竞赛》等书籍和必应、维基百科等网络。2.https://blog.csdn.net/u012469987/article/details/513195743.https://www.cnblogs.com/hxsyl/p/3270401.html4.https://wk.baidu.com/view/343fcfe8172ded630b1cb6f95.https://wk.baidu.com/view/be1b0a7f58cfa1c7aa00b52acfc789eb172d9e07
