图论的基本算法.ppt

《图论的基本算法.ppt》由会员分享，可在线阅读，更多相关《图论的基本算法.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论的基本算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望图n图的概念G=(V,E)n图的基本概念n有向图、顶点、入度、出度、弧、环n无向图、边、路径、顶点的度、邻接n简单图、完全图n平面图、二分图图的存储结构n邻接矩阵邻接矩阵 graph=Record vex:array1.vtxptr of vertex;arc:arrayvtxptr,vtxptr of vertex;n邻接表邻接表 表节点表节点 type arcptr=arcnode;arcnode=

2、record adjvex:vtxptr;nextarc:arcptr;info:和弧有关的其他信息和弧有关的其他信息 end;vex=Record vexdata:和顶点有关的其他信息和顶点有关的其他信息 firstarc:arcptr;end;adjlist=array vtxptr of vexnode;拓扑排序n网线从机房连接到办公室n在机房，所有网线从左到右编号为1,2,3,N n给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号 nFUNC toporder(var dig:adjlisttp):boolean;n init(top2);m:=0;ve1.n:=0n w

3、hile Not empty(top1)do n j:=pop(top1);push(top2,j);m:=m+1;n k:=firstadj(dig,j);n while k0 do n 入度(k):=入度(k)1;n if 入度(k)=0 then push(top1,k);n if vej+dut()vek then vek:=vej+dut();n k:=nextadj(dig,j,k)n n n if m0时时n以该顶点为开始或结束的针数以该顶点为开始或结束的针数=Kn可以恰好为可以恰好为K针针所有所有K值加起来，除以值加起来，除以2（每一针有两个端点）（每一针有两个端点）n注意差值

4、为注意差值为0时，为时，为1针而不是针而不是0针针最小生成树问题n要求连接所有岛屿n电缆总长度尽量小Prim算法n任意时刻的中间结果都是一棵树任意时刻的中间结果都是一棵树从一个点开始从一个点开始每次都花最小的代价，用一条加进一个新点每次都花最小的代价，用一条加进一个新点n问题：问题：这样做是对的吗？这样做是对的吗？如何快速找到这个如何快速找到这个“最小代价最小代价”？Prim算法的正确性n换一种说法换一种说法如果存在一个如果存在一个MST，包含当前所有边，包含当前所有边则也存在一个则也存在一个 MST,它包含最小代价边它包含最小代价边(u,v)n反证法！反证法！假设存在这样的假设存在这样的MS

5、T当前结点集为当前结点集为S，剩下的结点集为，剩下的结点集为T由于在由于在MST中中S-T连通连通n一定有跨越一定有跨越S-T的某边的某边(u,v)n它不是最小代价边它不是最小代价边(u,v)n删除删除(u,v)，加入，加入(u,v)，S和和T分别连通，且分别连通，且S-T通过通过(u,v)连通连通n得到了一个更小的得到了一个更小的MST！快速找到最小代价n需要借助数据结构！需要借助数据结构！n我们的算法要求我们的算法要求快速取快速取/删除最小值（边权）删除最小值（边权）允许插入边（加入新点时插入它的关接边）允许插入边（加入新点时插入它的关接边）抽象数据类型：优先队列！抽象数据类型：优先队列！

6、n经典实现：堆！经典实现：堆！Prim算法框架初始化，树仅含一个任意一点v0把v0的邻边插入堆for i:=1 to n1 dobegin 从堆中取出最小值，设边为(u,v)，v为新点 (u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(logm)总时间复杂度为O(nlogm)Kruskal算法n任意时刻的中间结果是一个森林从n个点的集合开始每次选不产生圈的前提下权最小的边加入n问题：这样做是对的吗？如何快速的判断是否产生圈Kruskal算法的正确性n把一个二元组(E,I)叫做一个子集系统，如果满足：1E是一个非空集合2I是E的一个子集族，它在包含运算下封闭

7、，即I的每个元素a都是E的一个子集，并对于a的任何子集a，a一定也是I的元素。3给E中每个元素e赋予一个正权w(e)。n考虑至少有一条边的带权无向连通图G它的边集为E它的所有生成森林的集合为I则(E,I)是一个子集系统，称为生成森林子集系统nE非空，所以满足条件1n生成森林是E的一个边集，而且其生成子图仍是生成森林，满足2nG是带权的，所以满足3。子集优化问题n极大独立集把I中的元素都称为独立集对于I中的元素a，如果不存在I中的另一个元素a使得a是a的真子集，则称a是极大独立集。该极大独立集的基数为它包含的元素个数n在刚才介绍的子集系统中，G的所有生成树就是所有的极大独立集。所有极大独立集具有

8、相同的基数|V|1。其中|V|为G的顶点数。n子集优化问题在子集系统(E,I)中选取一个元素SI，使得w(S)最大（定义w(S)为S中所有元素的权和）子集优化问题的贪心算法n贪心算法先把E中元素按照权值从大到小排序为e1,e2,令集合S=空集然后每次尝试着把e1,e2,，添加到S里面n如果添加之后S仍是独立集，则添加成功n如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此撤消此添加操作。nKruskal算法是生成森林子集系统的贪心算法！贪心算法在什么子集系统下是的对的呢？n定理贪心算法正确，当且仅当这个系统的极大独立集具有相同的基数满足条件的子集系统称

9、为“矩阵胚(matroid)”快速判断是否产生圈n需要借助数据结构！n我们的算法要求判断两个点是否在同一棵树中n产生圈当且仅当此边连接同一树中的点！快速把两棵树合并n加边意味着两棵树合为一棵抽象数据类型：并查集！n经典实现：森林n并查集的森林实现森林中的每棵树表示不同的集合树的形态并不重要，有意义的只是“哪些元素在树中”并查集的操作n查找用树根作为集合的标识不断的找父亲，最终将找到树根n要找多少次父亲？和树的高度有关！n怎样减少树的高度？找到树根后沿途把路径上的结点的父亲设为根专门名称：路径压缩两元素所在的树根相同，则二者属于同一集合n合并其中一棵树成为另一棵树树根的子树谁成为谁的子树？注意树

10、的高度！n启发式合并n时间复杂度：几乎都为常数！并查集的实现n回忆刚才用到了什么信息？查找：“不断的找父亲”“沿途设置结点的父亲为树根”合并：“把一棵树的父亲设置为另一棵树的树根”只有“父亲”信息！n父亲表示法！father:array1.maxn of integer;根结点root满足fatherroot:=root查找：while fatherp p do p:=fatherp;?合并：if height(p1)height(p2)then fatherp1:=p2Kruskal算法框架把所有边按照权值从小到大排序为e1,e2,初始化n个集合，Si=isize:=0;for i:=1 t

11、o m do if ei的两个端点u,v不在同一个集合 then begin 合并Su和Sv inc(size);if size=n 1 then break;end;n最坏情况循环执行m次，判断约O(1)n如果输入已经排序好，则总时间复杂度为O(m)，否则为O(mlogm)最短路问题n问题描述：给加权图GSSSP：求给定起点s到其他所有点的最短路APSP：求每两对点的最短路n算法标号设定类：dijkstra标号修正类：bellmanford动态规划类：floydwarshall变形与应用举例SSSP(Dijkstra算法)n核心思想：按路径递增的次序产生最短路径的算核心思想：按路径递增的次序

12、产生最短路径的算法法 1)找到图中最短的路径，设为（找到图中最短的路径，设为（v,vj）,将将j设为已设为已标号的点标号的点 2)找下一条次短的路径，假设终点为找下一条次短的路径，假设终点为k,将将k设为已设为已标号的点标号的点,那么要么是（那么要么是（v,vk）要么是（）要么是（v,vj,vk）,若经过若经过vj,将将j设为已检查的点设为已检查的点,放入集合放入集合.3)以次短路径出发找第三短的路径以次短路径出发找第三短的路径,类似第二步的类似第二步的方法方法.4)按上述方法一直到所有的顶点被检查过按上述方法一直到所有的顶点被检查过,则从则从v到到其他顶点的最短路径求出其他顶点的最短路径求出

13、.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 vtxnum1 do wm:=max;j:=v0;for i:=1 to vtxnum do if not(i in s)and(distiwm)then j

14、:=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 endPCar的旅行路线n又到暑假了，住在城市又到暑假了，住在城市A的的 Car想和朋友一起去城想和朋友一起去城市市B旅游。她知道每个城市都有四个飞机场，分旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第个机场之间有一条笔直的高速铁路，

15、第i个城市中个城市中高速铁路的单位里程价格为高速铁路的单位里程价格为Ti，任意两个不同城，任意两个不同城市的机场之间均有航线，所有航线单位里程的价市的机场之间均有航线，所有航线单位里程的价格均为格均为t。n那么那么Car应如何安排到城市应如何安排到城市B的路线才能尽可能的的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。于是她来向你请教。约束条件输入输入n第一行为一个正整数n(0n10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。ns（0S100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A

16、，B的序号，（1A，BS）。接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。输出输出共有n行，每行一个数据对应测试数据。分析1、计算两点间的欧氏距离、计算两点间的欧氏距离2、计算每个机场的坐标序列、计算每个机场的坐标序列3、使用、使用Dijkstra算法计算最小费用算法计算最小费用SSSP：权非负的情形n求求1到所有点的距离到所有点的距离d1=0d2=3,d4=4d2=3.为什么？为什么？每次固定每次固定d的

17、最小值的最小值n标号设定！标号设定！n怎样取最小值？堆！怎样取最小值？堆！n名称：名称：dijkstra和和Prim算法很类似算法很类似nPrim:边最小值边最小值ndijkstra:d最小值最小值n中间结果：最短路树！中间结果：最短路树！时间复杂度时间复杂度O(m+n)logm)一个例子n给出一个带权无向图给出一个带权无向图G边权为边权为11 000的整数的整数对于对于v0到到v1的任意一条简单路的任意一条简单路pn定义定义s(p)为为p上所有边权的最大公约数上所有边权的最大公约数考虑考虑v0到到v1的所有路的所有路p1,p2,n求所有求所有s(p1),s(p2),的最小公倍数的最小公倍数n

18、模型？最短路？模型？最短路？路径长度定义不再是权和，而是路径长度定义不再是权和，而是ndijkstra算法还能用吗？算法还能用吗？SSSP：权任意的情形n最短路有可能不存在！最短路有可能不存在！什么时候不存在？什么时候不存在？有负圈！有负圈！n标号设定标号设定标号修正标号修正仍然有标号仍然有标号di=k但是标号但是标号di无法固定，只能不断更新无法固定，只能不断更新n新算法新算法如有最短路，则每个顶点最多经过一次如有最短路，则每个顶点最多经过一次即：这条路不超过即：这条路不超过n-1条边条边 n迭代！依次考虑迭代！依次考虑1,2,3n-1条边的情形条边的情形SSSP：bellmanford算法

19、n依次考虑边长度不超过1,2n1的路考虑长度不超过1,2,3k1的路后，标号为d长度为k的路可以由不超过1,2,k1的路增加一条边得到：for k:=1 to n1 do for 每条边(u,v)do if(dudu+w(u,v)then dv:=du+w(u,v)核心：标号修正过程（松弛操作）时间复杂度：O(nm)改进的终止条件：d都不改变加速：用dijkstra得到初始d一个例子n24小时营业的超市小时营业的超市需要一批出纳员来满足它的需求需要一批出纳员来满足它的需求每天的不同时段需要不同数目的出纳员每天的不同时段需要不同数目的出纳员n例如：午夜时只需一小批，而下午则需要很多）例如：午夜时

20、只需一小批，而下午则需要很多）n经理已经提供你经理已经提供你一天里每一小时需要出纳员的最少数量一天里每一小时需要出纳员的最少数量R(0),R(1),R(23)。R(0)表示从午夜到午夜表示从午夜到午夜1:00需要出纳员的最少数目，需要出纳员的最少数目，R(1)表示上午表示上午1:00到到2:00之间需要的之间需要的每一天，这些数据都是相同的。每一天，这些数据都是相同的。n有有N人申请这项工作人申请这项工作每个申请者每个申请者i在每天在每天24小时中，从一特定的时刻开始连续工作恰好小时中，从一特定的时刻开始连续工作恰好8小时小时定义定义ti（0ti23）为上面提到的开始时刻）为上面提到的开始时刻

21、也就是说，如果第也就是说，如果第i个申请者被录用，他将从个申请者被录用，他将从ti刻开始连续工作刻开始连续工作8小小时。时。n计算为满足上述限制需要雇佣的最少出纳员数目计算为满足上述限制需要雇佣的最少出纳员数目在每一时刻可以有比对应的在每一时刻可以有比对应的R(i)更多的出纳员在工作。更多的出纳员在工作。分析n前i(0=i=23)小时的雇佣总数：si规定s1=0n第i(0=i=23)小时需要的出纳员：rin第i(0=i=23)小时申请的人数：tin则有不等式0=si si1 j时 si sj=rinI=ri sumnsum已知道时构图G(1,0,1,23)Sa sb=c：有向边(b,a,c)1

22、为起点的单源最长路最长路存在且s23=sum，有解n枚举sum！二分？APSP:基本分析n设di，j，k是在只允许经过结点1k的情况下i到j的最短路长度n则它有两种情况（想一想，为什么）：如果最短路经过点k，那么ndi，j，k应该等于di，k，k1+dk，j，k1；如果最短路不经过点k，那么ndi，j，k应该等于di，j，k1。综合起来ndi，j，k=mindi，k，k1+dk，j，k1，di，j，k1n边界条件是di，j，0=w(i，j)（不存在的边权为）floydwarshall算法n基本的动态规划把k放外层循环，可以节省内存对于每个k，计算每两点的目前最短路for k:=1 to n d

23、ofor i:=1 to n do for j:=1 to n do if(di,k)and(dk,j)and(di,k+dk,j0，第I子工程必须在子工程J之后完工FI表示完成子工程I所需的最早时间，COSTI表示完成子工程I所需的时间。（3）根据的得到的F序列和拓扑序列，查找关键工程。如果FI=FJCOSTJ（AJ，I 0）的话且第I个子工程为关键工程，那么第J个子工程也是关键工程。初始时，最后完成的一个或多个工程为关键工程。这一道试题的时间复杂度大致为O(N2)。算法思想：求事件的最早开始时间vei和最迟开始时间vli。从ve(1)=0开始往前递推 ve(j)=Maxve(i)+dut(

24、)从vl(n)=ve(n)开始往后递推 vl(i)=Minvl(j)dut()算法步骤：1)输入e条弧建立AOE网的存储结构2)从源点V1出发,令ve1=0，按拓扑有序求其余各定点最早发生时间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()vlj then vlj:=vlk-dut();k:=nextadj(dig,j,k);