图论的基本算法.ppt

图论,朱全民,图,图的概念 G=(V,E) 图的基本概念 有向图、顶点、入度、出度、弧、环 无向图、边、路径、顶点的度、邻接 简单图、完全图 平面图、二分图,图的存储结构,邻接矩阵 graph=Record vex:array1vtxptr of vertex; arc:arrayvtxptr, vtxptr of vertex; 邻接表 表节点 type arcptr=arcnode; arcnode=record adjvex:vtxptr; nextarc:arcptr; info: 和弧有关的其他信息 end; vex=Record vexdata: 和顶点有关的其他信息 firstarc:arcptr; end; adjlist=array vtxptr of vexnode;,拓扑排序,网线从机房连接到办公室 在机房，所有网线从左到右编号为1,2,3,N 给出每两条线是否交叉的信息，请计算办公室内从左到右各条线的编号,FUNC toporder(var dig:adjlisttp):boolean; init(top2); m:=0; ve1n:=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); 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),欧拉道路和回路,经过每条边一次且仅一次 先看回路 必要条件：所有点度为偶数 充分条件：还是“所有点度为偶数” 证明！ 把欧拉回路构造出来 “圈套圈” 可能套不出来吗？想一想,欧拉道路和回路,有向的情形 入度 = 出度 如何套圈？ 道路 有两个奇度点 正好是起点和终点 哪个是起点，哪个是终点？ 有向+无向怎么办？ 网络流！不要求掌握,怎样找欧拉回路,幼儿园里有很多房屋 房屋与房屋之间连以走廊 走廊与房屋之间有一扇门 幼儿园长想把门漆成绿色或者黄色，使得 任意一条走廊两头门的颜色不同 任意一间房屋上的门，绿色门的数量与黄色门的数量相差不超过1。 如何实现？,分析,如果每个房屋的门为偶数，那么幼儿园本身就是个欧拉回路。 那么，如果从房屋踏上走廊，门被漆成绿色；从走廊踏进房屋，门被漆成黄色。由于走廊只走一次，因此，每间房屋进出的次数一样，因此，任意一间房屋的门，绿色门和黄色门的数量一样。 如果门的数量为奇数，那么要对幼儿园门进行改造，要使得门数量为奇数的房屋为偶数个，将这样的房屋两两配对，并在新增加的门之间虚设一条走廊，这样幼儿园就成为了欧拉回路。 然后按规律给门油漆，然后撤去所有虚设的走廊和门，由于被撤去的房屋的门最多只有一个，所以同样保证绿色门的数量和黄色的门的数量相差不超过1。,另一个例子,考古学家发现了一块布，布上做有针线活，叫做“十字绣” 交替地在布的两面穿线 布是一个nm的网格 线只能在网格的顶点处才能从布的一面穿到另一面。 每一段线都覆盖一个单位网格的两条对角线之一 而在绣的过程中，一针中连续的两段线必须分处布的两面 给出布两面的图案（实线代表有线，虚线代表背面有线） 最少需要几针才能绣出来？ 一针是指针不离开布的一次绣花过程。 例如图(b)的图案最少需要4针。,分析,抽象成图 网格交叉点：顶点 正面的线：正边 背面的线：负边 有边相连：连通块 每个连通块分别求 对于某个顶点i |正边数-负边数|=K0时 以该顶点为开始或结束的针数=K 可以恰好为K针 所有K值加起来，除以2（每一针有两个端点） 注意差值为0时，为1针而不是0针,最小生成树问题,要求连接所有岛屿 电缆总长度尽量小,Prim算法,任意时刻的中间结果都是一棵树 从一个点开始 每次都花最小的代价，用一条加进一个新点 问题： 这样做是对的吗？ 如何快速找到这个“最小代价”？,Prim算法的正确性,换一种说法 如果存在一个MST，包含当前所有边 则也存在一个 MST, 它包含最小代价边(u, v) 反证法！ 假设存在这样的MST 当前结点集为S，剩下的结点集为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 do begin 从堆中取出最小值，设边为(u,v)，v为新点 (u,v)加入生成树中 v和它所有不在树中的邻居组成的边插入堆 end; 每次取最小值为O(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的一个边集，而且其生成子图仍是生成森林，满足2 G是带权的，所以满足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,，添加到S里面 如果添加之后S仍是独立集，则添加成功 如果S不是独立集，则由定义知以后无论怎样继续添加元素，得到的集合都不可能重新成为独立集，因此撤消此添加操作。 Kruskal算法是生成森林子集系统的贪心算法！ 贪心算法在什么子集系统下是的对的呢？ 定理 贪心算法正确，当且仅当这个系统的极大独立集具有相同的基数 满足条件的子集系统称为“矩阵胚(matroid)”,快速判断是否产生圈,需要借助数据结构！ 我们的算法要求 判断两个点是否在同一棵树中 产生圈当且仅当此边连接同一树中的点！ 快速把两棵树合并 加边意味着两棵树合为一棵 抽象数据类型：并查集！ 经典实现：森林 并查集的森林实现 森林中的每棵树表示不同的集合 树的形态并不重要，有意义的只是“哪些元素在树中”,并查集的操作,查找 用树根作为集合的标识 不断的找父亲，最终将找到树根 要找多少次父亲？和树的高度有关！ 怎样减少树的高度？ 找到树根后沿途把路径上的结点的父亲设为根 专门名称：路径压缩 两元素所在的树根相同，则二者属于同一集合 合并 其中一棵树成为另一棵树树根的子树 谁成为谁的子树？注意树的高度！ 启发式合并 时间复杂度：几乎都为常数！,并查集的实现,回忆刚才用到了什么信息？ 查找：“不断的找父亲”“沿途设置结点的父亲为树根” 合并：“把一棵树的父亲设置为另一棵树的树根” 只有“父亲”信息！ 父亲表示法！ father : array1maxn of integer; 根结点root满足fatherroot := root 查找：while fatherp p do p := fatherp; ? 合并：if height(p1) height(p2) then fatherp1 := p2,Kruskal算法框架,把所有边按照权值从小到大排序为e1,e2, 初始化n个集合，Si=i size := 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),最短路问题,问题描述：给加权图G SSSP：求给定起点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到其他顶点的最短路径求出.,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 (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 endP,Car的旅行路线,又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。 那么Car应如何安排到城市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、计算两点间的欧氏距离 2、计算每个机场的坐标序列 3、使用Dijkstra算法计算最小费用,SSSP：权非负的情形,求1到所有点的距离 d1 = 0 d2 = 3, d4 = 4 d2 = 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算法还能用吗？,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) 核心：标号修正过程（松弛操作） 时间复杂度：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刻开始连续工作8小时。 计算为满足上述限制需要雇佣的最少出纳员数目 在每一时刻可以有比对应的R(i)更多的出纳员在工作。,分析,前i(0 j时 si sj = ri I = ri sum sum已知道时构图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=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 do for 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 胖陀陀处在另外一个未知的城市 他们打算选一个城市X（这个由瘦陀陀来决定） 胖陀陀会赶在瘦陀陀之前到达城市X 然后等待瘦陀陀也赶到城市X与他汇合，并举办一次庆祝宴会（由瘦陀陀请客） 接着一起回到他们的家乡城市B 由于胖陀陀嘴馋，他要求举办宴会的城市必须是瘦陀陀回家的路线中举办宴会最贵的一个城市。,瘦陀陀正专注地看回家的地图 地图上标有n（n200）个城市和某些城市间直达的道路 以及每条道路的过路费 瘦陀陀还知道在每一座城市举办宴会的花费。 给出地图和A、B的位置 请你告诉瘦陀陀回家的最小费用 你的程序会接收到多次询问 即对于每对城市(c1,c2)，你的程序应该立刻给出瘦陀陀从c1到c2的最小花费。,分析,胖陀陀规定必须在最贵的城市举办宴会 因此不能简单地选择一条最短路走 若路上有一个花费特别贵的城市 对于每个点X，如果在那里办宴会 如何求最短路？ 多个询问怎么处理？ floyd计算每两点的距离？ SSSP就可以胜任吗？ AB = AX + XB,关键工程,在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设： （1）根据预算，每一个子工程都有一个完成时间。 （2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。 （3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。 （4）整个工程的完成是指：所有子工程的完成。,示例1,约束条件,输入：第1行为N，N是子工程的总个数，N200。 第2行为N个正整数，分别代表子工程1、2、N的完成时间。 第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、I-1、I+1、N的依赖关系，（I=1、2、N）。每行数据之间均用空格分开。 输出：如子工程划分不合理，则输出-1；如子工程划分合理，则用两行输出：第1行为整个工程最少的完成时间。第2行为按由小到大顺序输出所有关键子工程的编号。,求有向图的关键路径,分析,（1）根据