干图论专题精品课件

1、干图论专题第1页，共41页，2022年，5月20日，6点48分，星期三内容介绍拓扑排序欧拉道路和回路最小生成树问题最短路问题第2页，共41页，2022年，5月20日，6点48分，星期三基本概念图G=(V, E)点集V边集E，边(u, v)权集W，边(u,v)有权w图形表示邻接矩阵表示邻接表表示前向星表示第3页，共41页，2022年，5月20日，6点48分，星期三拓扑排序网线从机房连接到办公室在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号 第4页，共41页，2022年，5月20日，6点48分，星期三拓扑排序核心问题：给一些序关系，排出

2、全序！一个一个排先排最大然后第二大具体实现？每次取0出度点枚举所有点吗？0出度只可能是1出度变来的！O(n+m)第5页，共41页，2022年，5月20日，6点48分，星期三欧拉道路和回路经过每条边一次且仅一次先看回路必要条件：所有点度为偶数充分条件：还是“所有点度为偶数”证明！把欧拉回路构造出来“圈套圈”可能套不出来吗？想一想第6页，共41页，2022年，5月20日，6点48分，星期三欧拉道路和回路有向的情形入度 = 出度如何套圈？道路有两个奇度点正好是起点和终点哪个是起点，哪个是终点？有向+无向怎么办？网络流！不要求掌握第7页，共41页，2022年，5月20日，6点48分，星期三一个例子幼儿

3、园里有很多房屋房屋与房屋之间连以走廊走廊与房屋之间有一扇门幼儿园长想把门漆成绿色或者黄色，使得任意一条走廊两头门的颜色不同任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过1。 如何实现？每个房屋的门都是偶数个把奇数改造成偶数！第8页，共41页，2022年，5月20日，6点48分，星期三另一个例子考古学家发现了一块布，布上做有针线活，叫做“十字绣”交替地在布的两面穿线布是一个nm的网格线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一而在绣的过程中，一针中连续的两段线必须分处布的两面给出布两面的图案（实线代表有线，虚线代表背面有线）最少需要几针才能绣

4、出来？一针是指针不离开布的一次绣花过程。例如图(b)的图案最少需要4针。 第9页，共41页，2022年，5月20日，6点48分，星期三分析抽象成图正面的线：正边背面的线：负边有边相连：连通块每个连通块分别求对于某个顶点I|正边数-负边数|=K0时以该顶点为开始或结束的针数=K可以恰好为K针所有K值加起来，除以2（每一针有两个端点）第10页，共41页，2022年，5月20日，6点48分，星期三最小生成树问题要求连接所有岛屿电缆总长度尽量小第11页，共41页，2022年，5月20日，6点48分，星期三Prim算法任意时刻的中间结果都是一棵树从一个点开始每次都花最小的代价，用一条加进一个新点问题：这

5、样做是对的吗？如何快速找到这个“最小代价”？第12页，共41页，2022年，5月20日，6点48分，星期三Prim算法的正确性换一种说法如果存在一个MST，包含当前所有边则它一定包含最小代价边(u, v)反证法！假设存在这样的MST，包含当前所有边但不包含(u, v)当前结点集为S，剩下的结点集为T由于在MST中S-T连通一定有跨越S-T的某边(u,v)它不是最小代价边(u,v)删除(u,v)，加入(u,v)，S和T分别连通，且S-T通过(u,v)连通得到了一个更小的MST！第13页，共41页，2022年，5月20日，6点48分，星期三快速找到最小代价需要借助数据结构！我们的算法要求快速取/删

6、除最小值（边权）允许插入边（加入新点时插入它的关接边）抽象数据类型：优先队列！经典实现：堆！堆是一棵完全二叉树每个结点有一个权值根的权值最小根的左右子树都是堆第14页，共41页，2022年，5月20日，6点48分，星期三堆的操作插入插在哪里可以保持完全二叉树的形态呢？插最后！怎样维持堆的根最小性质呢？向上调整（和父亲交换）删除怎样保持完全二叉树形态呢？和最后一个元素交换，再直接删除怎样维持堆的根最小性质呢？向下调整（和两个儿子比较，和较小的交换）时间复杂度：均为O(logn)还有一个操作：取最小值，怎么实现？第15页，共41页，2022年，5月20日，6点48分，星期三堆的实现完全二叉树可以用

7、数组heap1.maxn实现结点i的父亲：i div 2左儿子：2*i右儿子：2*i+1存在条件：i = nodecount不用指针！利用了数组的“随机存取”特性！插入删除过程 用循环，不要用递归第16页，共41页，2022年，5月20日，6点48分，星期三Prim算法框架初始化，树仅含一个任意一点v0把v0的邻边插入堆for i:=1 to n-1 dobegin 从堆中取出最小值，设边为(u,v)，v为新点 (u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆end;每次取最小值为O(logm)总时间复杂度为O(nlogm)第17页，共41页，2022年，5月20日，6点48分，

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

9、满足条件1生成森林是E的一个边集，而且其生成子图仍是生成森林，满足2G是带权的，所以满足3。 第19页，共41页，2022年，5月20日，6点48分，星期三子集优化问题极大独立集把I中的元素都称为独立集对于I中的元素a，如果不存在I中的另一个元素a使得a是a的真子集，则称a是极大独立集。该极大独立集的基数为它包含的元素个数在刚才介绍的子集系统中，G的所有生成树就是所有的极大独立集。所有极大独立集具有相同的基数|V|-1。其中|V|为G的顶点数。子集优化问题在子集系统(E, I)中选取一个元素SI，使得w(S)最大（定义w(S)为S中所有元素的权和） 第20页，共41页，2022年，5月20日，

10、6点48分，星期三子集优化问题的贪心算法贪心算法先把E中元素按照权值从大到小排序为e1,e2,令集合S=空集然后每次尝试着把e1,e2,，添加到S里面如果添加之后S仍是独立集，则添加成功如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此撤消此添加操作。 Kruskal算法是生成森林子集系统的贪心算法！贪心算法在什么子集系统下是的对的呢？定理贪心算法正确，当且仅当这个系统的极大独立集具有相同的基数满足条件的子集系统称为“矩阵胚(matroid)”第21页，共41页，2022年，5月20日，6点48分，星期三快速判断是否产生圈需要借助数据结构！我们的算法要

11、求判断两个点是否在同一棵树中产生圈当且仅当此边连接同一树中的点！快速把两棵树合并加边意味着两棵树合为一棵抽象数据类型：并查集！经典实现：森林并查集的森林实现森林中的每棵树表示不同的集合树的形态并不重要，有意义的只是“哪些元素在树中”第22页，共41页，2022年，5月20日，6点48分，星期三并查集的操作查找用树根作为集合的标识不断的找父亲，最终将找到树根要找多少次父亲？和树的高度有关！怎样减少树的高度？找到树根后沿途把路径上的结点的父亲设为根专门名称：路径压缩两元素所在的树根相同，则二者属于同一集合合并其中一棵树成为另一棵树树根的子树谁成为谁的子树？注意树的高度！启发式合并时间复杂度：几乎都

12、为常数！第23页，共41页，2022年，5月20日，6点48分，星期三并查集的实现回忆刚才用到了什么信息？查找：“不断的找父亲”“沿途设置结点的父亲为树根”合并：“把一棵树的父亲设置为另一棵树的树根”只有“父亲”信息！父亲表示法！father : array1.maxn of integer;根结点root满足fatherroot := root查找：while fatherp p do p := fatherp; ?合并：if height(p1) height(p2) then fatherp1 := p2第24页，共41页，2022年，5月20日，6点48分，星期三Kruskal算法框架

13、把所有边按照权值从小到大排序为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)第25页，共41页，2022年，5月20日，6点48分，星期三最短路问题问题描述：给加权图GSSSP：求给定起点s到其他所有点的最短路APSP：求每两对点的最短路算法标号设定类：dijkstra标号修正类：bel

14、lman-ford动态规划类：floyd-warshall变形与应用举例第26页，共41页，2022年，5月20日，6点48分，星期三SSSP：权非负的情形求1到所有点的距离d1 = 0d2 = 3, d4 = 4d2 = 3. 为什么？每次固定d的最小值标号设定！怎样取最小值？堆！名称：dijkstra和Prim算法很类似Prim: 边最小值dijkstra: d最小值中间结果：最短路树！时间复杂度O(m+n)logm)第27页，共41页，2022年，5月20日，6点48分，星期三一个例子给出一个带权无向图G边权为11 000的整数对于v0到v1的任意一条简单路p定义s(p)为p上所有边权的

15、最大公约数考虑v0到v1的所有路p1,p2,求所有s(p1),s(p2),的最小公倍数模型？最短路？路径长度定义不再是权和，而是dijkstra算法还能用吗？第28页，共41页，2022年，5月20日，6点48分，星期三SSSP：权任意的情形最短路有可能不存在！ 什么时候不存在？ 有负圈！标号设定标号修正仍然有标号di = k但是标号di无法固定，只能不断更新新算法如有最短路，则每个顶点最多经过一次即：这条路不超过n-1条边 迭代！依次考虑1,2,3n-1条边的情形第29页，共41页，2022年，5月20日，6点48分，星期三SSSP：bellman-ford算法依次考虑边长度不超过1,2n-

16、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) 核心：标号修正过程（松弛操作）时间复杂度：O(nm)改进的终止条件：d都不改变加速：用dijkstra得到初始d第30页，共41页，2022年，5月20日，6点48分，星期三一个例子24小时营业的超市需要一批出纳员来满足它的需求每天的不同时段需要不同数目的出纳员例如：午夜时只需一小批，而下午则需要很多）经理已经提供你一天里每一小时需要出纳员的最少数

17、量R(0), R(1), , R(23)。R(0)表示从午夜到午夜1:00需要出纳员的最少数目，R(1)表示上午1:00到2:00之间需要的每一天，这些数据都是相同的。有N人申请这项工作每个申请者i在每天24小时中，从一特定的时刻开始连续工作恰好8小时定义ti（0ti23）为上面提到的开始时刻也就是说，如果第i个申请者被录用，他将从ti刻开始连续工作8小时。计算为满足上述限制需要雇佣的最少出纳员数目在每一时刻可以有比对应的R(i)更多的出纳员在工作。 第31页，共41页，2022年，5月20日，6点48分，星期三分析前i(0=i=23)小时的雇佣总数：si规定s-1 = 0第i(0=i=23)

18、小时需要的出纳员：ri第i(0=i=23)小时申请的人数：ti则有不等式0 = si si-1 j时 si sj = riI = ri sumsum已知道时构图G(-1,0,1,23)Sa sb = c：有向边(b, a, c)-1为起点的单源最长路最长路存在且s23 = sum，有解枚举sum！二分？第32页，共41页，2022年，5月20日，6点48分，星期三APSP: 基本分析设di，j，k是在只允许经过结点1k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：如果最短路经过点k，那么di，j，k应该等于di，k，k-1+dk，j，k-1；如果最短路不经过点k，那么di，j，k

19、应该等于di，j，k-1。综合起来di，j，k=mindi，k，k-1+dk，j，k-1，di，j，k-1边界条件是di，j，0=w(i，j)（不存在的边权为） 第33页，共41页，2022年，5月20日，6点48分，星期三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)用途：预处理！第

20、34页，共41页，2022年，5月20日，6点48分，星期三一个例子一场可怕的战争后，瘦陀陀和他的好朋友胖陀陀将要凯旋。瘦陀陀处在城市A胖陀陀处在另外一个未知的城市他们打算选一个城市X（这个由瘦陀陀来决定）胖陀陀会赶在瘦陀陀之前到达城市X然后等待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴会（由瘦陀陀请客）接着一起回到他们的家乡城市B由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。 第35页，共41页，2022年，5月20日，6点48分，星期三一个例子（续）瘦陀陀正专注地看回家的地图地图上标有n（n200）个城市和某些城市间直达的道路以及每条道路的过路费瘦陀

21、陀还知道在每一座城市举办宴会的花费。给出地图和A、B的位置请你告诉瘦陀陀回家的最小费用你的程序会接收到多次询问即对于每对城市(c1,c2)，你的程序应该立刻给出瘦陀陀从c1到c2的最小花费。 第36页，共41页，2022年，5月20日，6点48分，星期三分析胖陀陀规定必须在最贵的城市举办宴会因此不能简单地选择一条最短路走若路上有一个花费特别贵的城市对于每个点X，如果在那里办宴会如何求最短路？多个询问怎么处理？floyd计算每两点的距离？SSSP就可以胜任吗？AB = AX + XB第37页，共41页，2022年，5月20日，6点48分，星期三讨论题目（一）没有水或食物，你将无法前行为了穿越沙漠，应该购买多少食物呢？在出发地，你可以采购食物和获得无限多的免费水但由于背包容量有限，在任意时候拥有的水和食物总量不得超过一个