lecture 6 graph algorithms

《lecture 6 graph algorithms》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

第六部分图算法（Graphalgorithms）6．1图图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.6.1.1图的基本概念图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={v|vÎ某个数据对象}是顶点的有穷非空集合；E={(v,w)|v,wÎV}是顶点之间关系的有穷集合，也叫做边(edge)集合。l有向图与无向图若图中的每条边都是有方向的，则称为有向图。有向边也称为弧。若图中的每条边都是没有方向的，则称为无向图。例6.1G1=(V1E1)其中:V1={v1,v2,v3,v4}E1={,,,}G2=(V2E2)其中:V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}有向图G1无向图G219 l完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1)，则称其为有向完全图。l邻接顶点若（v,v’）是一条无向边，则称顶点v和v’互为邻接点，或称v和v’相邻接，并称边（v,v’）关联于顶点v和v’，或称（v,v’）与顶点v和v’相关联。l顶点的度一个顶点v的度是与它相关联的边的条数。记作Deg(v)。l顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。TD(v)=ID(v)+OD(v)有n个顶点，e条边或弧的图，有e=l子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’ÍV且E‘ÍE,则称图G’是图G的子图。l路径在图G＝(V,{E})中,若存在一个顶点序列vp1,vp2,…,vpm，使得(v,vp1)、(vp1,vp2)、...、(vpm,v’)均属于E，则称顶点v到v’存在一条路径。若一条路径上除了v和v’j可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。l图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。19 l强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。v5v1v2v3v4v5v1v2v4v5v1v2v3v3v4v1v2G1的两个强连通分量G2的子图v1§权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。12356874ABDCE10796671231516603045358040756.1.2图的存储结构图的数据表示方式有多种，以下介绍较为常用的四种：一、邻接矩阵（AdjacencyMatrix）邻接矩阵是将图中的n个顶点（Vertices），以一个n×n的二维矩阵来表示，其中若A(i,j)=1，则表示图中有一条边（Vi,Vj）存在。反之，A(i,j)=1则没有（见图6.1～图6.4）。例6．219 图6.1图的邻接矩阵表示法无向图的邻接矩阵具有对称性，且对角线上元素都为0，所以在图中只需存储上三角或下三角即可，所需要存储空间为n(n-1)/2。读者要注意的是：（1）若要求无向图中某一顶点相邻边的数目（即度），则要算邻接矩阵中某一列所有1的和或某一行所有1的和。例如要求例（1）中顶点2的相邻边数，可从第2列或第2行，知其顶点2的相邻边数（度）是3。（2）若要求有向图的入度或出度。邻接矩阵中列中1的和便是出度，而行中1的和，便是入度。二、邻接表（AdjacencyList）邻接表是将图中的每个顶点都形成单链表的表头，而在每个链表表头后的结点表示它们之间有边相连。例6.3图6.2每个结点数据结构如图6.1.2.6所示。图6.319 在无向图中，若有n个顶点，m个边，则形成n个链表表头，2m个结点（对称）。在有向图中，则有n个链表表头，及m个顶点。图6.4例6.4图6.5图的邻接表表示法三、邻接多重表（AdjacencyMultilist）每个边均以一个结点表示，但这个结点可同时存在于两个链表中，结点的结构如下：19 LINK1LINK2MV1V2forV1forV2M为一个位的标记字段，用以表示该边是否已被搜索过。V1及V2表示该边的两个顶点。LINK1字段是一个指针，若尚有其他顶点与顶点V1相连，则LINK1指向“该顶点与顶点V1所形成的边结点”，否则指向0（null）。LINK2字段也是一个指针，若尚有其他顶点与顶点V2相连，则LINK2指向“该顶点与顶点V2所形成的边结点”，否则指向0（null）。图的每一个顶点依序产生一个链表头，每个链表头分别指向第一个包含该顶点的边所形成的结点，所需的内存空间比一般的邻接表所需的空间多了标记字段空间。以下为用邻接多重表表示法。图6.6图的邻接多重表表示法四、索引表（IndexedTable）索引表也为一种存储图的一种数据结构，采用一维数组存储顶点，建立一个索引表格并且对应到相当的位置。操作方式如下：（1）以一个一维数组来顺序存储相邻顶点。（2）建立一个索引表格，n个顶点须建立n个位置于索引表格中，分别对应于数组中与第一个与该顶点相邻的位置。19 如图6.1.2.12所示为将6.1.2.11用邻接多重表表示法。图6.1.2.12其索引表的表示方式图6.1.2.13所示。图6.1.2.136．2广度优先搜索Breadth-firstsearch使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1,w2,…,wt，然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为避免重复访问，需要一个辅助数组visited[]，给被访问过的顶点加标记。19 遍历结果：A、B、C、D广度优先遍历v7v6v3v8v5v4v2v1广度优先遍历v4v5v7v6v3v2v113738212v854v7v6v3v8v5v4v2v16以邻接表表示的图存储结构1|v1=>2->3^2|v2=>4->5->1^图中的圈表示已被访问过的邻接点号3|v3=>6->7->1^v1-->v2-->v3-->v4-->v5-->v6-->v7-->v84|v4=>2->8^5|v5=>2->8^6|v6=>3->7^7|v7=>6->3^8|v8=>4->5^BFS(V,E,s)for对每个节点u∈V−{s}19 docolor[u]←WHILEd[u]←∞p[u]←NILcolor[s]←GRAYd[s]←0p[s]←NILQ←∅ENQUEUE(Q,s)whileQ≠∅dou←DEQUEUE(Q)for对每个节点v∈Adj[u]doifcolor[u]=WHILEthencolor[v]←GRAYd[v]←d[u]+1p[v]←uENQUEUE(Q,v)color[u]←BLACK算法运行时间：。BFS算法的正确性：设G=(V，E)是一个无向图或有向图，并假设算法BFS从G上某顶点s∈V开始运行则在执行过程中，BFS可以发现源结点s可达的每一个结点v∈V。在运行终止时，对任意v∈V，d[v]＝d[s,v]。此外，对任意从s可达的结点v≠s,从s到v的最短路径之一是从s到p[v]的最短路径再加上边(p[v],v)。算法分析§如果使用邻接表表示图，则循环的总时间代价为d0+d1+…+dn-1=O(e)，其中的di是顶点i的度。§如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)6．3深度优先搜索Depth-firstsearch19 深度优先搜索在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。遍历结果：A、C、B、D深度优先遍历v7v6v3v8v5v4v2v119 v8v5v4v7v6v3v2v15824216317以邻接表表示的图存储结构1|v1=>2->3^图中的圈表示已被访问过的邻接点号2|v2=>4->5->1^v1-->v2-->v4-->v8-->v5------>v3-->v6-->v73|v3=>6->7->1^4|v4=>2->8^5|v5=>2->8^6|v6=>3->7^7|v7=>6->3^8|v8=>4->5^和广度优先搜索的比较①类似点：每当扫描已发现结点u的邻接表从而发现新结点v时，将置v的先辈域p[v]为u；在搜索过程中，为结点着色以表示结点的状态。②19 不同点：由于深度优先搜索可能由多个源顶点开始重复进行，故产生的先辈子图可由几棵树组成，从而深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林；深度优先搜索除创建一个深度优先森林外，同时为每个结点v加盖两个时间戳：当结点v第一次被发现(置成灰色)时记录下第一个时间戳d[v],当结束检查v的邻接表（置成黑色）时记录下第二个时间戳f[v]。算法实现：DFS(V,E)for对每个顶点u∈Vdocolor[u]←WHITEp[u]←NILtime←0for对每个顶点u∈Vdoifcolor[u]=WHITEthenDFS-VISIT(u)其中DFS-VISIT过程如下：DFS-VISIT(u)color[u]←GRAYtime←time+1d[u]←timefor对每个顶点v∈Adj[u]doifcolor[v]=WHITEthenp[v]←uDFS-VISIT(v)color[u]←BLACKtime←time+1f[u]←timeDFS算法运行时间：§图中有n个顶点，e条边。§如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。§如果用邻接表表示图，沿Firstoutàlink链可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)19 DFS性质：①最基本的特征是它的先辈子图形成一个由树组成的森林；②一个重要特征是它的发现时间和完成时间具有括号结构（可由后面的括号定理及推论得出）；③在深度优先搜索中，可以通过搜索对输入图G=(V，E)的边进行归类（见边的归类）。括号定理：在对有向图或无向图G=(V，E)的任何深度优先搜索中，对于图中任意两结点u和v，下面三个条件有且仅有一条成立：l区间d[u]，f[u]和区间d[v]，f[v]是完全分离的；l区间d[u]，f[u]完全包含于区间d[v]，f[v]中且在深度优先树中u是v的后裔；l区间d[v]，f[v]完全包含于区间d[u]，f[u]中且在深度优先树中u是v的后裔。后裔区间嵌入定理：在有向图或无向图G=(V，E)的深度优先森林中，结点v是结点u的后裔当且仅当d[u]∈E(G)，则u在线性序列中出现在v之前。   通常，这样的线性序列称为满足拓扑次序(TopoiSicaiOrder)的序列，简称拓扑序列。19 c1c2c7c3c4c5c8c6c11c10c12c9c1和c9谁先无关的！c12一定要在c1,c9,c10后！c8一定在最后！拓扑排序结果：c1c2c3c4c5c7c9c10c11c6c12c8或c9c10c11c6c1c12c4c2c3c5c7c8拓扑排序法：(1)在有向图中选一个前驱的顶点且输出。(2)从图中删去该顶点和以它为尾的弧。重复(1),(2)直到全部顶点都已输出，或者当前图中不存在无前驱的顶点为止。后一情况表示中有环。输出：v6v1v4v3v2v5v1v3v5v6v4v2v1v3v5v4v2v3v5v4v2v3v5v2v5v2计算机上实现时可采用邻接表作有向图的存储结构，且在头结点中增加一个入度的数据，入度为零的顶点即没有前驱的顶点，删去顶点和以它为尾的弧的操作时把入度（另一个头结点中）减1来实现.拓扑排序算法框架1、扫描顶点表，将入度为0的顶点入栈；19 2、while(栈非空){将栈顶顶点v弹出并输出之；检查v的出边，将每条出边终点u的入度减1，若u的入度变为0，则把u推入栈；}3、若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。算法分析设AOV网有n个顶点，e条边。初始建立入度为0的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)，所以总的时间复杂度为O(n+e)例6.甲公司预计今年在某地区设立一个输油网络，其管制站及输油管的分布如图8-55所示，应如何制定各输油管的流量才能使网络总流量F达到最大。图8-55注：S---可无限制供应；T---可无限制接收输油管上的数字表示该输油管每分钟可输送多少石油步骤一：刚开始时设所有输油管流量为0，并列出所有S到T可走的路径（见图8-56）：图8-561.S→A→B→C→D→T。2.S→A→B→T。3.S→C→D→T。19 4.S→C→D→A→B→T。由图8-56可找到上列四条途径，然后随便指定一条路径开始做增流工作，路径的指定没有限制，只要方便就可以。步骤二：依步骤一，我们选择路径3（S-C-D-T）（见图8-57）。图8-57列出路径各输油管流量：S→C→D→T。444以路径中最小输油管流量为此路径流量设置依据：S→C→D→T。066此路径剩余流量：S→C→D→T。步骤三：依步骤一，我们选择1（S-A-B-C-D-T）（见图8-58）。1512366图8-581512366路径下各输油管流量：S→A→B→C→D→T。129033以路径中最小输油管流量为此路径流量设置依据：S→A→B→C→D→T。此路径剩余流量：S→A→B→C→D→T。注：当路径流量满时，此路径视为消失。步骤四：由于（S-C）,（B-C）的路径已饱和，因此只剩路径2（S-A-B-T）可走（见图8-59）。19 1279图8-591297列出路径各输油管流量：S→A→B→T。520以路径中最小输油管流量为此路径流量设置依据：S→A→B→T。剩余流量为：S→A→B→T所以我们可以得到甲公司的石油输送网络从S到T最大流量每分钟14单位。6．4．2强连通分支Stronglyconnectedcomponents强连通分支：一有向图G=(V，E)的强连通支是满足如下条件的最大顶点集U⊆V：对任意顶点u,v∈V，有u←v和v←u同时成立，即顶点u和顶点互为可达。如图所示例子。算法实现（为G的转置）：定义有向图G=(V,E)的分支图为GSCC=(VSCC,ESCC),其中VSCC包含的每一个结点对应于G的每个强连通分支。如果图G的对应于节点u的强连通分支中，某个结点和对应于v的强连通分支中的某个结点之间存在一条有向边，则边(u,v)∈ESCC。图1给出了一个实例。显而易见对于分支图有以下定理：定理6.1有向图G的分支图GSCC是一个有向无回路图。寻找图G=(V,E)的强连通分支的算法中使用了G的转置，其定义为：GT=(V,ET)，其中ET={(v,u)∈V×V:(u,v)∈E}，即ET由G中的边改变方向后组成。若已知图G的邻接表，则建立GT所需时间为O(V+E)。注意到下面的结论是很有趣的：G和GT有着完全相同的强连通支，即在G中u和v互为可达当且仅当在GT中它们互为可达。图1(b)即为图1(a)所示图的转置，其强连通支上涂了阴影。19 引理6.1如果两个结点处于同一强连通支中，那么在它们之间不存在离开该连通支的通路。定理6.2在任何深度优先搜索中，同一强连通支内的所有顶点均在同一棵深度优先树中。定理6.3已知有向图G=(V,E)，在对G的深度优先搜索中，对任意结点u∈V,其祖宗Φ(u)是u的祖先。定理6.4在有向图G=(V,E)中，两个结点u,v∈V处于同一强连通分支当且仅当对G进行深度优先搜索时两结点具有同一祖宗STRONGLY-CONNECTED-COMPONENTS(G)1调用DFS(G)计算每个顶点u的完成时间f[u]2计算出3调用DFS()，但在DFS的主循环里按f[u]递减的顺序考虑各结点（和第一行中一样计算）4输出第3步中产生的深度优先森林中每棵树的结点，作为各自独立的强连通支。算法运行时间：。算法的正确性：①19 如果两个结点处于同一强连通支中，那么在它们之间步存在离开该强连通支的通路；②在任何深度优先搜索中，同一强连通支的所有顶点均在同一棵深度优先树中；③已知有向图G=(V，E)，在对G的深度优先搜索中，对任意结点u∈V，其祖宗是u的祖先；④在对有向图G=(V，E)任何深度优先搜索中，对所有结点u∈V，结点u和处于同一个强连通支内；⑤在有向图G=(V，E)中，两个结点u,v∈V处于同一个强连通支内,当且仅当对G的深度优先搜索时两结点具有同一祖宗；⑥过程STRONGLY-CONNECTED-COMPONENTS(G)可正确计算出有向图G的强连通支。6．5总结上面我们介绍了图的基本定义、存储结构以及两种搜索算法。当我们编程时，图的存储结构对程序员来说是很重要的，也是进行后面一些算法的基础。图的搜索算法可以使我们发现图的很多结构信息。许多图的算法的开始时，都是通过搜索输入的图来获取结构信息，用到的两种搜索技术有DFS和BFS。另外还有一些图的算法实际上是由基本的图搜索算法经过简单扩充而成的，比如：强连通分支，拓扑排序、关键路径等。因此，图的搜索技术是图算法领域的核心。19