图论的基本算法ppt课件

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

2、ecord n vexdata: 和顶点有关的其他信息和顶点有关的其他信息n firstarc:arcptr;n end;n adjlist=array vtxptr of vexnode;拓扑排序n网线从机房衔接到办公室n在机房，一切网线从左到右编号为1,2,3,N n给出每两条线能否交叉的信息，请计算办公室内从左到右各条线的编号 (a) (b) nFUNC toporder(var dig:adjlisttp):boolean;n init(top2); m:=0; ve1.n:=0n while Not empty(top1) do n j:=pop(top1); push(top2,j

3、); 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针针n一切一切K值加起来，除以值加起来，除以2每一针有两个端点每一针有两个端点n留意差值为留意差值为0时，为时，为1针而不是针而不是0针针最小生成树问题n要求衔接一切岛屿n电缆总长度尽量小

4、 400 250 1500 500 2500 Main lsland 750 600 Prim算法n恣意时辰的中间结果都是一棵树恣意时辰的中间结果都是一棵树n从一个点开场从一个点开场n每次都花最小的代价，用一条加进一个新每次都花最小的代价，用一条加进一个新点点n问题：问题：n这样做是对的吗？这样做是对的吗？n如何快速找到这个如何快速找到这个“最小代价？最小代价？Prim算法的正确性n换一种说法换一种说法n假设存在一个假设存在一个MST，包含当前一切边，包含当前一切边n那么也存在一个那么也存在一个 MST, 它包含最小代价边它包含最小代价边(u, v)n反证法！反证法！n假设存在这样的假设存在这

5、样的MSTn当前结点集为当前结点集为S，剩下的结点集为，剩下的结点集为Tn由于在由于在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我们的算法要求我们的算法要求n快速取快速取/删除最小值边权删除最小值边权n允许插入边参与新点时插入它的关接允许插入边参与新点时插入它的关接边边n笼统数据类型：优先队列！笼统数据类型：优先队列

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

7、它在包含运算下封锁，即I的每个元素a都是E的一个子集，并对于a的任何子集a，a一定也是I的元素。n3给E中每个元素e赋予一个正权w(e)。n思索至少有一条边的带权无向连通图Gn它的边集为En它的一切生成森林的集合为In那么(E,I)是一个子集系统，称为生成森林子集系统nE非空，所以满足条件1n生成森林是E的一个边集，而且其生成子图仍是生成森林，满足2nG是带权的，所以满足3。 子集优化问题n极大独立集n把I中的元素都称为独立集n对于I中的元素a，假设不存在I中的另一个元素a使得a是a的真子集，那么称a是极大独立集。n该极大独立集的基数为它包含的元素个数n在刚刚引见的子集系统中，G的一切生成树就

8、是一切的极大独立集。一切极大独立集具有一样的基数|V|-1。其中|V|为G的顶点数。n子集优化问题n在子集系统(E, I)中选取一个元素SI，使得w(S)最大定义w(S)为S中一切元素的权和 子集优化问题的贪婪算法n贪婪算法n先把E中元素按照权值从大到小排序为e1,e2,n令集合S=空集n然后每次尝试着把e1,e2,，添加到S里面n假设添加之后S仍是独立集，那么添加胜利n假设S不是独立集，那么由定义知以后无论怎样继续添加元素，得到的集合都不能够重新成为独立集，因此吊销此添加操作。 nKruskal算法是生成森林子集系统的贪婪算法！n贪婪算法在什么子集系统下是的对的呢？n定理n贪婪算法正确，当且

9、仅当这个系统的极大独立集具有一样的基数n满足条件的子集系统称为“矩阵胚(matroid)快速判别能否产生圈n需求借助数据构造！n我们的算法要求n判别两个点能否在同一棵树中n产生圈当且仅当此边衔接同一树中的点！n快速把两棵树合并n加边意味着两棵树合为一棵n笼统数据类型：并查集！n经典实现：森林n并查集的森林实现n森林中的每棵树表示不同的集合n树的形状并不重要，有意义的只是“哪些元素在树中并查集的操作n查找n用树根作为集合的标识n不断的找父亲，最终将找到树根n要找多少次父亲？和树的高度有关！n怎样减少树的高度？n找到树根后沿途把途径上的结点的父亲设为根n专门称号：途径紧缩n两元素所在的树根一样，那

10、么二者属于同一集合n合并n其中一棵树成为另一棵树树根的子树n谁成为谁的子树？留意树的高度！n启发式合并n时间复杂度：几乎都为常数！并查集的实现n回想刚刚用到了什么信息？n查找：“不断的找父亲“沿途设置结点的父亲为树根n合并：“把一棵树的父亲设置为另一棵树的树根n只需“父亲信息！n父亲表示法！nfather : array1.maxn of integer;n根结点root满足fatherroot := rootn查找：while fatherp p do p := fatherp; ?n合并：if height(p1) height(p2) then fatherp1 := p2Kruskal

11、算法框架把一切边按照权值从小到大排序为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)最短路问题n问题描画：给加权图GnSSSP：求给定起点s到其他一切点的最短路nAPSP：求每两对点的最短路n算法n标号设定类：dijkstran标号修正类：bellman-fordn动态规划类：flo

12、yd-warshalln变形与运用举例SSSP (Dijkstra算法)n中心思想：按途径递增的次序产生最短途径的算中心思想：按途径递增的次序产生最短途径的算法法n 1)找到图中最短的途径，设为找到图中最短的途径，设为v,vj,将将j设为设为已标号的点已标号的点n 2)找下一条次短的途径，假设终点为找下一条次短的途径，假设终点为k,将将k设为设为已标号的点已标号的点,那么要么是那么要么是v,vk要么是要么是v,vj,vk,假设经过假设经过vj ,将将j设为已检查的点设为已检查的点,放入放入集合集合.n 3)以次短途径出发找第三短的途径以次短途径出发找第三短的途径,类似第二步类似第二步的方法的方

13、法.n 4)按上述方法不断到一切的顶点被检查过按上述方法不断到一切的顶点被检查过,那么从那么从v到其他顶点的最短途径求出到其他顶点的最短途径求出.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 vt

14、xnum-1 do wm:=max; j:=v0; for i:=1 to vtxnum do if not (i in s) and (distiwm) 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 endPCar的游览道路n又到暑假了，住在城市又到暑假了，住在城市A的的 Car想和朋友一同去想和朋友一同去城市城市B旅游。她知道每个城市都有四个飞机场，旅游。她知道每

15、个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第两个机场之间有一条笔直的高速铁路，第i个城市个城市中高速铁路的单位里程价钱为中高速铁路的单位里程价钱为Ti，恣意两个不同，恣意两个不同城市的机场之间均有航线，一切航线单位里程的城市的机场之间均有航线，一切航线单位里程的价钱均为价钱均为t。n那么那么Car应如何安排到城市应如何安排到城市B的道路才干尽能够的的道路才干尽能够的节省破费昵？她发现这并不是一个简单的问题，节省破费昵？她发现这并不是一个简单的问题，于是她来向他讨教。于是她来向他讨教。约束条件输入输

16、入第一行为一个正整数第一行为一个正整数n(0n10)，表示有，表示有n组测试数据。组测试数据。每组的第一行有四个正整数每组的第一行有四个正整数s，t，A，B。s0S100表示城市的个数，表示城市的个数，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为为第第

17、i个城市高速铁路单位里程的价钱。个城市高速铁路单位里程的价钱。输出输出共有共有n行，每行一个数据对应测试数据。行，每行一个数据对应测试数据。分析1、计算两点间的欧氏间隔、计算两点间的欧氏间隔2、计算每个机场的坐标序列、计算每个机场的坐标序列3、运用、运用Dijkstra算法计算最小费用算法计算最小费用SSSP：权非负的情形n求求1到一切点的间隔到一切点的间隔nd1 = 0nd2 = 3, d4 = 4nd2 = 3. 为什么？为什么？n每次固定每次固定d的最小值的最小值n标号设定！标号设定！n怎样取最小值？堆！怎样取最小值？堆！n称号：称号：dijkstran和和Prim算法很类似算法很类似n

18、Prim: 边最小值边最小值ndijkstra: d最小值最小值n中间结果：最短路树！中间结果：最短路树！n时间复杂度时间复杂度O(m+n)logm)12433432一个例子n给出一个带权无向图给出一个带权无向图Gn边权为边权为11 000的整数的整数n对于对于v0到到v1的恣意一条简单路的恣意一条简单路pn定义定义s(p)为为p上一切边权的最大公约数上一切边权的最大公约数n思索思索v0到到v1的一切路的一切路p1,p2,n求一切求一切s(p1),s(p2),的最小公倍数的最小公倍数n模型？最短路？模型？最短路？n途径长度定义不再是权和，而是途径长度定义不再是权和，而是ndijkstra算法还

19、能用吗？算法还能用吗？SSSP：权恣意的情形n最短路有能够不存在！最短路有能够不存在！n 什么时候不存在？什么时候不存在？n 有负圈！有负圈！n标号设定标号设定标号修正标号修正n依然有标号依然有标号di = kn但是标号但是标号di无法固定，只能不断更新无法固定，只能不断更新n新算法新算法n如有最短路，那么每个顶点最多经过一次如有最短路，那么每个顶点最多经过一次n即：这条路不超越即：这条路不超越n-1条边条边 n迭代！依次思索迭代！依次思索1,2,3n-1条边的情形条边的情形SSSP：bellman-ford算法n依次思索边长度不超越1,2n-1的路n思索长度不超越1,2,3k-1的路后，标号

20、为dn长度为k的路可以由不超越1,2,k-1的路添加一条边得到：nfor k:=1 to n-1 don for 每条边(u,v) don if (dudu+w(u,v) then n dv:=du+w(u,v) n中心：标号修正过程松弛操作n时间复杂度：O(nm)n改良的终止条件：d都不改动n加速：用dijkstra得到初始d一个例子n24小时营业的超市小时营业的超市n需求一批出纳员来满足它的需求需求一批出纳员来满足它的需求n每天的不同时段需求不同数目的出纳员每天的不同时段需求不同数目的出纳员n例如：午夜时只需一小批，而下午那么需求很多例如：午夜时只需一小批，而下午那么需求很多n经理曾经提供

21、他经理曾经提供他n一天里每一小时需求出纳员的最少数量一天里每一小时需求出纳员的最少数量R(0), R(1), , R(23)。nR(0)表示从午夜到午夜表示从午夜到午夜1:00需求出纳员的最少数目，需求出纳员的最少数目，nR(1)表示上午表示上午1:00到到2:00之间需求的之间需求的n每一天，这些数据都是一样的。每一天，这些数据都是一样的。n有有N人恳求这项任务人恳求这项任务n每个恳求者每个恳求者i在每天在每天24小时中，从一特定的时辰开场延续小时中，从一特定的时辰开场延续任务恰好任务恰好8小时小时n定义定义ti0ti23为上面提到的开场时辰为上面提到的开场时辰n也就是说，假设第也就是说，假

22、设第i个恳求者被录用，他将从个恳求者被录用，他将从ti刻开场延续刻开场延续任务任务8小时。小时。n计算为满足上述限制需求雇佣的最少出纳员数目计算为满足上述限制需求雇佣的最少出纳员数目n在每一时辰可以有比对应的在每一时辰可以有比对应的R(i)更多的出纳员在任务。更多的出纳员在任务。 分析n前i(0=i=23)小时的雇佣总数：sin规定s-1 = 0n第i(0=i=23)小时需求的出纳员：rin第i(0=i=23)小时恳求的人数：tin那么有不等式n0 = si si-1 j时 si sj = rinI = ri sumnsum知道时构图G(-1,0,1,23)nSa sb = c：有向边(b,

23、a, c)n-1为起点的单源最长路n最长路存在且s23 = sum，有解n枚举sum！二分？APSP: 根本分析n设di，j，k是n在只允许经过结点1k的情况下ni到j的最短路长度n那么它有两种情况想一想，为什么：n假设最短路经过点k，那么ndi，j，k应该等于di，k，k-1+dk，j，k-1；n假设最短路不经过点k，那么ndi，j，k应该等于di，j，k-1。n综合起来ndi，j，k=mindi，k，k-1+dk，j，k-1，di，j，k-1n边境条件是di，j，0=w(i，j)不存在的边权为 floyd-warshall算法n根本的动态规划n把k放外层循环，可以节省内存n对于每个k，计算每两点的目前最短路nfor k:=1 to n donfor i:=1 to n don for j:=1 to n don if (di,k)and(dk,j)n and(di,k+