图的定义背景知识下面这幅图就是传说中的七桥问题(哥尼斯堡桥问题)。在哥尼斯堡,普雷格尔河环绕着奈佛夫岛(图中的A岛)。这条河将陆地分成了下面4个区域,该处还有着7座连接这些陆地的桥梁。 问题是如何从某地出发,依次沿着各个桥,必须经过每座桥且每座桥只能经过1次,最终回到原地。 不知道这个问题且好奇的童鞋现在肯定在忙活着找出来这道题的结果了。 是伟大的数学家欧拉(Leonhard Euler)在1736年首次使用图的方法解决了该问题。 欧拉将上面的模型转换成了下面这种”图“的形式。 欧拉把顶点的度定义为与该顶点相关联的边的条数,并且他证明了存在从任意点出发,经过所有边恰好一次,并最终回到出发顶点的走法的充分必要条件是:每个顶点的度均为偶数。人们称之为欧拉闭迹(Eulerian walk)。 简要定义图 有时也把边称作弧(arc),如果点对 顶点 我们可以给边赋予各式的属性,比如权值(cost)。权值可以表示从一个顶点到另一个顶点的距离,也可以表示一个顶点到另一个顶点说话费的代价(比如时间、金钱等)。一个边上带权值的图称为网络(network)。 如果无向图中从每一个顶点到其他每个顶点都存在一条路径,则称该无向图是连通的(connected)。具有这样性质的有向图称为是强连通的的(strongly connected)。如果有向图不是强连通的,但它的基础图(underlying graph)(也就是其弧上去掉方向说形成的图)是连通的,那么称该有向图是弱连通的(weakly connected)。完全图(complete graph)是其每一对顶点间都存在一条边的图。
如下表示了一个有着7个顶点和12条边的有向图。 如果具有n个顶点,e条边的图G的顶点i的度为 以上这个数学公式的markdown“源码”:
现在将图看作抽象数据类型,下面给出ADT图的结构: 图的存储表示方式 图主要有3种常用的存储表示方式:邻接矩阵(adjacency matrices),邻接表(adjacency lists),邻接多重表(adjacency multilists)。 邻接矩阵 邻接矩阵使用 1)因为在无向图中,我们只需要知道顶点 2)而在有向图中,我们只需要知道是否有从顶点 3)在带权值的图中, 使用这种存储方式,可以很方便地判断任意两个顶点之间是否有边以及确定顶点的度,这也是这种表示法最大的优势。任意一个顶点i的度等于其邻接矩阵中顶点i所对应的行中的数字之和:
在这种表示法中扫描所有边至少需要 邻接表 如果用邻接矩阵表示稀疏图就会浪费大量内存空间,而用链接表,则是通过把顶点所能到的顶点的边保存在链表中来表示图,这样就只需要 而所谓的邻接表,就是用n个链表代替邻接矩阵中的n行。链表中的结点结构至少要包含一个顶点域和一个链域。对于任意给定的链表i,链表中的结点就是与顶点i相邻的所有顶点。邻接表存储声明的C语言声明如下:
邻接多重表 在无向图的邻接表存储表示中,每一条边
图的基本操作和算法广度优先搜索请先忽视下图中所有的下标,让我们从头开始。随意选择一个点,此处选择 这就是广度优先搜索(breadth-first search),该方法按层处理顶点。距起始点最近的那些顶点首先被求值,最远点则最后被求值,这很像对树的层序遍历(level-order traversal)。 为了实现广度优先搜索,可以使用动态链接队列。在队列中的每个顶点都包含两个域:顶点的序号和链接指针。 函数bfs所使用的队列的定义和函数原型声明为:
图的广度优先搜索算法:
图中每个顶点都被存入队列一次,所以该算法中的while循环至多重复n次。如果采用邻接表存储表示,那么该算法所需要的时间为: 其中 而如果采用邻接矩阵来实现,那么对于每个顶点的访问,while循环的时间为 深度优先搜索深度优先搜索内容较多,已经在下文中单独列出。 连通图使用以上的两种搜索算法也可以用来判断一个无向图是否是连通的。具体步骤如下: 1.调用bfs(0)或dfs(0) 具体代码如下:
算法分析:如果采用邻接表存储,那么函数dfs时间开销为 双连通图双联通图(biconnected graph)是没有关节点的连通图。对此有一个比较重要的公式如下:
回退边也叫back edge,大家顾名思义就好,下面有更多应用。 下面来段求解图的双连通分支的算法: 拓扑排序拓扑排序(topological sort)是对有向无环图的顶点的一种排序,它使得如果存在一条从vi到vj的路径,那么在排序中vj出现在vi的后面。正是由于这个特性,如果图含有回路,那么拓扑排序是不可能的。 求拓扑排序算法的一种简单方式:选中一个没有入边的顶点,显示出该点,并将它和它的边一起从图中删除,然后对图的其余部分应用同样的方法处理。 假设每一个顶点的入度被存储且图被读入一个邻接表中,下面的代码则可以生成一个拓扑排序。 对上图应用拓扑排序的结果如下: 最短路径算法单源最短路径问题:给定一个加权图G=(V,E)和一个特定顶点s作为输入,找出从s到G中每一个其他点的最短加权路径。 如下图所示,从v1到v6的最短加权路径的值为6( 下面这个图从v5到v4的最短加权路径可就有意思了,它是1么?不是。按照 当未指明所讨论的是加权路径还是无权路径时,如果图是加权的,那么路径就是加权的。 下面列出单源最短路径算法: 思考:找出A到所有其他顶点的最短路径以及B到所有其他顶点的最短无权路径。 如果要求所有顶点对之间的最短路径,可以用下面这个算法: Dijkstra算法前面的广度优先搜索中的图是无权图,而如果一旦变成了加权图,那么问题就变得困难起来了。 对于每个顶点,我们标记为known以及unknown,和上面一样,还得有一个距离的 那么这个算法到底是怎么回事了?请看下图。 图中已经对权重做好了标记,以 毫无疑问这里会接下来走到v4去,因为v4的权重为1比v2的权重为2要小。 可能你已经看到了上图中的右图而好奇为什么下一步是v2,但是v4根本不能走到v2。因为v4能够走到的,比如v3,权重从v1开始一共是3,这比从v1到v2还要大。于是就跳转回到了v2。 下一步便走到了 紧接着走到了 最后便顺势走到了v6完成了整个Dijkstra算法,它们都已被标记为known。 具有负边值的图而如果一个图具有负的边值,那么Dijkstra算法就行不通了。这是因为一个顶点u被声明为known后,那就可能从某个另外的unknown顶点v有一条回到u的负的路径。而“回到”就意味着循环,前面的例子中我们已经知道了循环是多么的…… 问题并非没有解决的办法,如果我们有一个常数X,将其加到每一条边的值上,这样除去负的边,再计算新图的最短路径,最后把结果应用到原图上。然后这个解决方案也是布满了荆棘,因为居多许多条边的路径变得比那些具有很少边的路径权重更重了。如果我们将s放到队列中,然后再每一个阶段让一个顶点v出队,找出所有与v邻接的顶点w,使得 无环图如果图是无环的,则可以通过改变声明顶点为known的顺序,或者叫做顶点选取法则来改进Dijkstra算法。这种方法通过拓扑排序来选择顶点,由于选择和更新可以在拓扑排序执行的过程中执行,因此新的算法只需要一趟就可以完成。 通过下面这个动作结点图(activity-node graph)来解释什么是关键路径分析(critical path analysis)再合适不过了。一条边 为了进行这些运算,我们把动作结点图转化成事件结点图(event-node graph),每个事件对应于一个动作和所有与它相关的动作完成。 所以现在我们需要找出事件的最早完成时间,只要找出从第一个事件到最后一关事件的最长路径的长。因为有正值回路(positive-cost cycle)的存在最长路径问题常常是没有意义的。而由于事件结点图是无环图,那就不需要担心回路的问题了,这样一来就不用有所顾忌了。 以下是最早完成时间。 以下是最晚完成时间。 借助顶点的拓扑排序计算最早完成时间,而最晚完成时间则通过倒转拓扑排序来计算。 而事件结点图中每条边的松弛时间(slack time)代表对应动作可以被延迟而不推迟整体完成的时间量,最早完成时间、最晚完成时间和松弛时间如下所示。 某些动作的松弛时间为0,这些动作是关键性的动作,它们必须按计划结束。至少存在一条完成零-松弛边组成的路径,这样的路径是关键路径(critical path)。 网络流问题如下左图所示,有一个顶点 要想计算最大流,同样可是使用前面的思想——分阶段进行。令开始时所有边都没有流,如下中间图所示。我们可以用残余图(residual graph)来表示对于每条边还能再添加上多少流。对于每一条边,可以从容量中减去当前的流而计算出残留的流。 第一步:假设我们选择 第二步:接下来选择 第三步:从上图的残余图中我们已经可以看出来最后一步的唯一一种走法了,也就是从 很显然从 如果一开始我们选择了 为了使算法得以成功运作,那么就要让流图中具有以相反方向发送流的路径,如下所示。那么对于如下右图中的残余图而言,从d返回到a的便成了3而非4,这是因为从t流到d的流量是3个单位。现在在残余图中就有a和d之间有2个方向,或者还有1个单位的流可以从 紧接着如果通过 |
|