《图论的基本算法》PPT课件.ppt

《《图论的基本算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论的基本算法》PPT课件.ppt（49页珍藏版）》请在三一办公上搜索。

1、图论,朱全民,图,图的概念G=(V,E)图的基本概念有向图、顶点、入度、出度、弧、环无向图、边、路径、顶点的度、邻接简单图、完全图平面图、二分图,图的存储结构,邻接矩阵 graph=Record vex:array1.vtxptr of vertex;arc:arrayvtxptr,vtxptr of vertex;邻接表 表节点 type arcptr=arcnode;arcnode=record adjvex:vtxptr;nextarc:arcptr;info:和弧有关的其他信息 end;vex=Record vexdata:和顶点有关的其他信息 firstarc:arcptr;end;

2、adjlist=array vtxptr of vexnode;,拓扑排序,网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号,FUNC toporder(var dig:adjlisttp):boolean;init(top2);m:=0;ve1.n:=0 while Not empty(top1)do j:=pop(top1);push(top2,j);m:=m+1;k:=firstadj(dig,j);while k0 do 入度(k):=入度(k)-1;if 入度(k)=0 then push(top1,k

3、);if vej+dut()vek then vek:=vej+dut();k:=nextadj(dig,j,k)if mn then return(false)else return(true);endF;,求拓扑序列,拓扑排序,核心问题：给一些序关系，排出全序！一个一个排先排最大然后第二大具体实现？每次取0出度点枚举所有点吗？0出度只可能是1出度变来的！O(n+m),欧拉道路和回路,经过每条边一次且仅一次先看回路必要条件：所有点度为偶数充分条件：还是“所有点度为偶数”证明！把欧拉回路构造出来“圈套圈”可能套不出来吗？想一想,欧拉道路和回路,有向的情形入度=出度如何套圈？道路有两个奇度点正好

4、是起点和终点哪个是起点，哪个是终点？有向+无向怎么办？网络流！不要求掌握,怎样找欧拉回路,幼儿园里有很多房屋房屋与房屋之间连以走廊走廊与房屋之间有一扇门幼儿园长想把门漆成绿色或者黄色，使得任意一条走廊两头门的颜色不同任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过1。如何实现？,分析,如果每个房屋的门为偶数，那么幼儿园本身就是个欧拉回路。那么，如果从房屋踏上走廊，门被漆成绿色；从走廊踏进房屋，门被漆成黄色。由于走廊只走一次，因此，每间房屋进出的次数一样，因此，任意一间房屋的门，绿色门和黄色门的数量一样。如果门的数量为奇数，那么要对幼儿园门进行改造，要使得门数量为奇数的房屋为偶数个，将这

5、样的房屋两两配对，并在新增加的门之间虚设一条走廊，这样幼儿园就成为了欧拉回路。然后按规律给门油漆，然后撤去所有虚设的走廊和门，由于被撤去的房屋的门最多只有一个，所以同样保证绿色门的数量和黄色的门的数量相差不超过1。,另一个例子,考古学家发现了一块布，布上做有针线活，叫做“十字绣”交替地在布的两面穿线布是一个nm的网格线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一而在绣的过程中，一针中连续的两段线必须分处布的两面给出布两面的图案（实线代表有线，虚线代表背面有线）最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。例如图(b)的图案最少需要4针。,分

6、析,抽象成图网格交叉点：顶点正面的线：正边背面的线：负边有边相连：连通块每个连通块分别求对于某个顶点i|正边数-负边数|=K0时以该顶点为开始或结束的针数=K可以恰好为K针所有K值加起来，除以2（每一针有两个端点）注意差值为0时，为1针而不是0针,最小生成树问题,要求连接所有岛屿电缆总长度尽量小,Prim算法,任意时刻的中间结果都是一棵树从一个点开始每次都花最小的代价，用一条加进一个新点问题：这样做是对的吗？如何快速找到这个“最小代价”？,Prim算法的正确性,换一种说法如果存在一个MST，包含当前所有边则也存在一个 MST,它包含最小代价边(u,v)反证法！假设存在这样的MST当前结点集为S

7、，剩下的结点集为T由于在MST中S-T连通一定有跨越S-T的某边(u,v)它不是最小代价边(u,v)删除(u,v)，加入(u,v)，S和T分别连通，且S-T通过(u,v)连通得到了一个更小的MST！,快速找到最小代价,需要借助数据结构！我们的算法要求快速取/删除最小值（边权）允许插入边（加入新点时插入它的关接边）抽象数据类型：优先队列！经典实现：堆！,Prim算法框架,初始化，树仅含一个任意一点v0把v0的邻边插入堆for i:=1 to n-1 dobegin 从堆中取出最小值，设边为(u,v)，v为新点(u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(

8、logm)总时间复杂度为O(nlogm),Kruskal算法,任意时刻的中间结果是一个森林从n个点的集合开始每次选不产生圈的前提下权最小的边加入问题：这样做是对的吗？如何快速的判断是否产生圈,Kruskal算法的正确性,把一个二元组(E,I)叫做一个子集系统，如果满足：1E是一个非空集合2I是E的一个子集族，它在包含运算下封闭，即I的每个元素a都是E的一个子集，并对于a的任何子集a，a一定也是I的元素。3给E中每个元素e赋予一个正权w(e)。考虑至少有一条边的带权无向连通图G它的边集为E它的所有生成森林的集合为I则(E,I)是一个子集系统，称为生成森林子集系统E非空，所以满足条件1生成森林是E

9、的一个边集，而且其生成子图仍是生成森林，满足2G是带权的，所以满足3。,子集优化问题,极大独立集把I中的元素都称为独立集对于I中的元素a，如果不存在I中的另一个元素a使得a是a的真子集，则称a是极大独立集。该极大独立集的基数为它包含的元素个数在刚才介绍的子集系统中，G的所有生成树就是所有的极大独立集。所有极大独立集具有相同的基数|V|-1。其中|V|为G的顶点数。子集优化问题在子集系统(E,I)中选取一个元素SI，使得w(S)最大（定义w(S)为S中所有元素的权和）,子集优化问题的贪心算法,贪心算法先把E中元素按照权值从大到小排序为e1,e2,令集合S=空集然后每次尝试着把e1,e2,，添加到

10、S里面如果添加之后S仍是独立集，则添加成功如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此撤消此添加操作。Kruskal算法是生成森林子集系统的贪心算法！贪心算法在什么子集系统下是的对的呢？定理贪心算法正确，当且仅当这个系统的极大独立集具有相同的基数满足条件的子集系统称为“矩阵胚(matroid)”,快速判断是否产生圈,需要借助数据结构！我们的算法要求判断两个点是否在同一棵树中产生圈当且仅当此边连接同一树中的点！快速把两棵树合并加边意味着两棵树合为一棵抽象数据类型：并查集！经典实现：森林并查集的森林实现森林中的每棵树表示不同的集合树的形态并不重要，有

11、意义的只是“哪些元素在树中”,并查集的操作,查找用树根作为集合的标识不断的找父亲，最终将找到树根要找多少次父亲？和树的高度有关！怎样减少树的高度？找到树根后沿途把路径上的结点的父亲设为根专门名称：路径压缩两元素所在的树根相同，则二者属于同一集合合并其中一棵树成为另一棵树树根的子树谁成为谁的子树？注意树的高度！启发式合并时间复杂度：几乎都为常数！,并查集的实现,回忆刚才用到了什么信息？查找：“不断的找父亲”“沿途设置结点的父亲为树根”合并：“把一棵树的父亲设置为另一棵树的树根”只有“父亲”信息！父亲表示法！father:array1.maxn of integer;根结点root满足father

12、root:=root查找：while fatherp p do p:=fatherp;?合并：if height(p1)height(p2)then fatherp1:=p2,Kruskal算法框架,把所有边按照权值从小到大排序为e1,e2,初始化n个集合，Si=isize:=0;for i:=1 to m do if ei的两个端点u,v不在同一个集合 then begin 合并Su和Sv inc(size);if size=n 1 then break;end;最坏情况循环执行m次，判断约O(1)如果输入已经排序好，则总时间复杂度为O(m)，否则为O(mlogm),最短路问题,问题描述：给

13、加权图GSSSP：求给定起点s到其他所有点的最短路APSP：求每两对点的最短路算法标号设定类：dijkstra标号修正类：bellman-ford动态规划类：floyd-warshall变形与应用举例,SSSP(Dijkstra算法),核心思想：按路径递增的次序产生最短路径的算法 1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点 2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,若经过vj,将j设为已检查的点,放入集合.3)以次短路径出发找第三短的路径,类似第二步的方法.4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点

14、的最短路径求出.,PROC short_DIJ(da:adjmatrix;v0:vtxptr)var dist:arrayvtxptr of weighttype;存储路径长度 path:arrayvtxptr of set;存储路径 for i:=1 to vxtmun do disti:=da.costv0,i;if distimax then pathi:=v0+i else pathi:=;s:=v0;s存储被标号的顶点 for k:=1 to vtxnum-1 do wm:=max;j:=v0;for i:=1 to vtxnum do if not(i in s)and(disti

15、wm)then j:=i;wm:=disti s:=s+j for i:=1 to vtxnum do if not(i in s)and(distj+da.costj,iwm then disti:=distj+da.costj,i;pathi:=pathj+pathi endP,Car的旅行路线,又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。那么Car应如何安排到城市

16、B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。,约束条件,输入第一行为一个正整数n(0n10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。s（0S100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1A，BS）。接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。输出共有n行，每行一个数据对应测试数据。,分析,1、计算两点间的欧氏距

17、离2、计算每个机场的坐标序列3、使用Dijkstra算法计算最小费用,SSSP：权非负的情形,求1到所有点的距离d1=0d2=3,d4=4d2=3.为什么？每次固定d的最小值标号设定！怎样取最小值？堆！名称：dijkstra和Prim算法很类似Prim:边最小值dijkstra:d最小值中间结果：最短路树！时间复杂度O(m+n)logm),一个例子,给出一个带权无向图G边权为11 000的整数对于v0到v1的任意一条简单路p定义s(p)为p上所有边权的最大公约数考虑v0到v1的所有路p1,p2,求所有s(p1),s(p2),的最小公倍数模型？最短路？路径长度定义不再是权和，而是dijkstra

18、算法还能用吗？,SSSP：权任意的情形,最短路有可能不存在！什么时候不存在？有负圈！标号设定标号修正仍然有标号di=k但是标号di无法固定，只能不断更新新算法如有最短路，则每个顶点最多经过一次即：这条路不超过n-1条边 迭代！依次考虑1,2,3n-1条边的情形,SSSP：bellman-ford算法,依次考虑边长度不超过1,2n-1的路考虑长度不超过1,2,3k-1的路后，标号为d长度为k的路可以由不超过1,2,k-1的路增加一条边得到：for k:=1 to n-1 do for 每条边(u,v)do if(dudu+w(u,v)then dv:=du+w(u,v)核心：标号修正过程（松弛操

19、作）时间复杂度：O(nm)改进的终止条件：d都不改变加速：用dijkstra得到初始d,一个例子,24小时营业的超市需要一批出纳员来满足它的需求每天的不同时段需要不同数目的出纳员例如：午夜时只需一小批，而下午则需要很多）经理已经提供你一天里每一小时需要出纳员的最少数量R(0),R(1),R(23)。R(0)表示从午夜到午夜1:00需要出纳员的最少数目，R(1)表示上午1:00到2:00之间需要的每一天，这些数据都是相同的。有N人申请这项工作每个申请者i在每天24小时中，从一特定的时刻开始连续工作恰好8小时定义ti（0ti23）为上面提到的开始时刻也就是说，如果第i个申请者被录用，他将从ti刻开

20、始连续工作8小时。计算为满足上述限制需要雇佣的最少出纳员数目在每一时刻可以有比对应的R(i)更多的出纳员在工作。,分析,前i(0 j时 si sj=riI=ri sumsum已知道时构图G(-1,0,1,23)Sa sb=c：有向边(b,a,c)-1为起点的单源最长路最长路存在且s23=sum，有解枚举sum！二分？,APSP:基本分析,设di，j，k是在只允许经过结点1k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：如果最短路经过点k，那么di，j，k应该等于di，k，k-1+dk，j，k-1；如果最短路不经过点k，那么di，j，k应该等于di，j，k-1。综合起来di，j，k

21、=mindi，k，k-1+dk，j，k-1，di，j，k-1边界条件是di，j，0=w(i，j)（不存在的边权为）,floyd-warshall算法,基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路for k:=1 to n dofor i:=1 to n do for j:=1 to n do if(di,k)and(dk,j)and(di,k+dk,jdi,j)then di,j:=di,k+dk,j一定要背下来！时间复杂度：O(n3)用途：预处理！,一个例子,一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。瘦陀陀处在城市A胖陀陀处在另外一个未知的城市他们打

22、算选一个城市X（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市X然后等待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）接着一起回到他们的家乡城市B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。,瘦陀陀正专注地看回家的地图地图上标有n（n200）个城市和某些城市间直达的道路以及每条道路的过路费瘦陀陀还知道在每一座城市举办宴会的花费。给出地图和A、B的位置请你告诉瘦陀陀回家的最小费用你的程序会接收到多次询问即对于每对城市(c1,c2)，你的程序应该立刻给出瘦陀陀从c1到c2的最小花费。,分析,胖陀陀规定必须在最贵的城市举办宴会因此不能简单地

23、选择一条最短路走若路上有一个花费特别贵的城市对于每个点X，如果在那里办宴会如何求最短路？多个询问怎么处理？floyd计算每两点的距离？SSSP就可以胜任吗？AB=AX+XB,关键工程,在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键

24、子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：（1）根据预算，每一个子工程都有一个完成时间。（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。（4）整个工程的完成是指：所有子工程的完成。,示例1,约束条件,输入：第1行为N，N是子工程的总个数，N200。第2行为N个正整数，分别代表子工程1、2、N的完成时间。第3行到N+2行，每行有N-1个0或1。其中

25、的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、I-1、I+1、N的依赖关系，（I=1、2、N）。每行数据之间均用空格分开。输出：如子工程划分不合理，则输出-1；如子工程划分合理，则用两行输出：第1行为整个工程最少的完成时间。第2行为按由小到大顺序输出所有关键子工程的编号。,求有向图的关键路径,分析,（1）根据的得到邻接矩阵对子工程进行拓扑排序。如果该图能够进行拓扑排序的话，证明有解，反之则无解。（2）根据的得到拓扑序列进行动态规划求解，得到工程所需的完成时间。动态规划方程：FI=MAXFJ+COSTI AI，J 0，第I子工程必须在子工程J之后完工FI表示完成子工程I所需的最早

26、时间，COSTI表示完成子工程I所需的时间。（3）根据的得到的F序列和拓扑序列，查找关键工程。如果FI=FJ-COSTJ（AJ，I 0）的话且第I个子工程为关键工程，那么第J个子工程也是关键工程。初始时，最后完成的一个或多个工程为关键工程。这一道试题的时间复杂度大致为O(N2)。,算法,思想：求事件的最早开始时间vei和最迟开始时间vli。从ve(1)=0开始往前递推 ve(j)=Maxve(i)+dut()从vl(n)=ve(n)开始往后递推 vl(i)=Minvl(j)-dut()算法步骤：1)输入e条弧建立AOE-网的存储结构2)从源点V1出发,令ve1=0，按拓扑有序求其余各定点最早发

27、生时间vei。如果得到拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法中止；否则执行步骤33)从汇点Vn出发，令vln=ven，按逆拓扑有序求其余各定点的最迟发生时间vli4)根据各定点的ve和vl的值求每条弧的最早开始时间e(s)和最迟开始时间l(s)。若满足e(s)=l(s),则该活动为关键活动,求关键路径,PROC critical_path(Var dig:adjlisttp);crt_adjlist(dig);if not toporder(dig)then writeln(Has a cycle)else vl1.n:=ven;初始化最迟发生时间 while Not empty(top2)Do j:=pop(top2);k:=firstadj(dig,j);while k0 do if vlk-dut();k:=nextadj(dig,j,k);,