《day图论算法与模型构建（精品） .ppt》由会员分享，可在线阅读，更多相关《day图论算法与模型构建（精品） .ppt（111页珍藏版）》请在三一办公上搜索。
1、图论算法与模型构建,总览,图的基本概念与存储结构图的遍历和染色性图的连通性问题路径问题 拓扑排序流量问题匹配问题,图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.,定义1 一个有序二元组(V,E)称为一个图,记为G=(V,E),其中,V称为G的顶点集,V,其元素称为顶点或结点,简称点;E称为G的边集,其元素称为边,它联结V 中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果V=v1,v2,vn是有限非空点集,则称G为有限图或n阶图.,Sec.1 图的基本概念与存储结构,如果E的每一条边都是无向边,
2、则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.,图1,图2,并且常记,V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.,称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.,有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.用N(v)表示图G中所有与顶点v相邻的顶点的集合.,d(v1)=d(v3)=d(v4)=4,d(v2)=2.,我们今后只讨论有限简单图：,
3、(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.,定义2 若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).,定义3 设G=(V,E)是一个图,v0,v1,vkV,且1ik,vi-1viE,则称v0 v1 vk是G的一条通路.如果通路中没有相同的边,则称此通路为道路.
4、始点和终点相同的道路称为圈或回路.如果通路中既没有相同的边,又没有相同的顶点,则称此通路为路径,简称路.定义4 任意两点均有通路的图称为连通图.定义5 连通而无圈的图称为树,常用T表示树.,图的储存结构,矩阵邻接表邻接多重表十字链表,无向图邻接表,1,5,2,4,3,12345,1|,5|,4|,3|/,2|,2|,2|,3|,1|,2|,4|/,5|/,4|/,5|/,邻接链表每一个顶点有一个所有与之相邻的链表每一条边2 个（对无向图）要在两个顶点的链表中都加入空间复杂度O(|E|)对稀疏图这种方式比较好,邻接表,Pascal语言 const maxv=10000;type Tnode=re
5、cord/定义顶点类型 c:integer;/顶点编号 next:Tnode;/此点的邻接链表end;Var/数组g表示每个顶点的邻接链表/的链表头-哨兵 g:array1.maxv of Tnode;n,m,i,a,b:integer;t:Tnode;,C+语言#include using namespace std;const int maxv=10000;struct Tnode/定义顶点类型 int c;/顶点编号 Tnode*next;/此点的邻接链表;/数组g表示每个顶点的邻接链表/的链表头-哨兵 Tnode gmaxv;int n,m,i,a,b;Tnode*t;,图G有n个顶点
6、，编号从1到n。有m条有向边，输入时每行两个整数a b，表示边为从顶点a连接到顶点b。下面程序用指针实现图的邻接链表。,Pascal语言 procedure ins(x:integer;var p:Tnode);Begin/插入链表子过程 new(t);t.c:=x;t.next:=p.next;p.next:=t;end;begin readln(n,m);/初始化邻接链表“哨兵”for i:=1 to n do gi.next:=nil;/读入边，插入邻接链表 for i:=1 to m do begin readln(a,b);ins(b,ga);ins(a,gb);/无向边时再加入 e
7、nd;/.,C+语言 void ins(int x,Tnode/无向边时/,邻接表的实现A（指针）,Pascal语言 const maxV=1000;/最多顶点数 maxE=10000;/最多边数type Tnode=record/定义顶点类型 c:integer;/节点编号 next:integer;/此节点的邻接链表end;var e:array1.maxE of Tnode;g:array1.maxV of Tnode;n,m,efree,i,a,b,t:integer;procedure ins(x:integer;var p:Tnode);begin/取一个空元素插入链表p后 eef
8、ree.c:=x;eefree.next:=p.next;p.next:=efree;efree:=efree+1;/新空元素下标end;,C+语言 const int maxV=1000,/最多顶点数 maxE=10000;/最多边数struct Tnode/定义顶点类型 int c;/顶点编号 int next;/此点的邻接链表;/数组g表示每个顶点的邻接链表/的链表头-哨兵 Tnode gmaxV,emaxE;int n,m,i,a,b,efree,t;void ins(int x,Tnode/新空元素下标,邻接表的实现B（数组）,Pascal语言 begin readln(n,m);/
9、初始化邻接链表“哨兵”for i:=1 to n do gi.next:=-1;efree:=1;/读入边，插入邻接链表 for i:=1 to m do begin readln(a,b);ins(b,ga);ins(a,gb);/无向边时 end;.,C+语言 int main()cin n m;efree=0;/初始化邻接链表“哨兵”for(i=1;iab;ins(b,ga);/ins(a,gb);/无向边时,邻接表的实现B（数组）,带权图的邻接表存储方法,Type Link=Node;Node=Record v,w:Longint;顶点和费用 Next:Link;End;Map:Arr
10、ay1.Maxnof Link;用邻接表记录的图,Read(n,m);For i:=1 to m do Begin Read(a,b,c);New(p);p.v:=b;p.w:=c;p.Next:=Mapa;Mapa:=p;End;,Sec.2 图的遍历和染色性,图的遍历和染色性是解决一切图论问题的根基，例如判断图的联通性，判断图是否有环，判断图是否为二分图，等等一些基本问题都要通过图的遍历和染色来进行。这一步骤虽然很不起眼，但是在编程解题过程中往往都是一些最基本的步骤，整个问题的求解往往都是由它开始的。,图的遍历,从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一
11、过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS和广度优先搜索BFS。这两种方法都适用于有向图和无向图。,图的深度优先搜索遍历,图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。连通图的深度优先遍历算法思想。（1）访问初始顶点v并标记顶点v已访问。（2）查找顶点v的第一个邻接顶点w。（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。（5）继续查找顶点w的下一个邻
12、接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。,深度优先遍历的程序实现：（邻接表、Pascal）,/图的一般结构 type graph_node=record end;type AdjList=record id:integer;next:AdjList;end;var n_nodes,S_i:integer;nodes:array1.maxN of graph_node;visited:array1.maxNof integer;adj:array1.maxN of AdjList;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链表的节点数据结构,深度优先
13、遍历的程序实现：（邻接表、Pascal）,置每个点标识为“未访问”,从所有未被访问的点k出发，调用DFS(k),procedure search();begin k:integer;for k:=1 to n_nodes do visitedk:=0;for k:=1 to n_nodes do if visitedk0 then DFS(k);end;,置被访问节点的“时间”-次序,访问k的所有相邻的节点,procedure DFS(k:integer);begin/从k出发搜索 var j:AdjList;begin inc(S_i);visitedk:=S_i;j:=adjk;while
14、(jNULL)do begin if visitedj.id0 then DFS(j.id);j:=j.next;end;end;,图的广度优先搜索遍历,图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。连通图的广度优先遍历算法思想。（1）顶点v入队列。（2）当队列非空时则继续执行，否则算法结束。（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（4）查找顶点v的第一个邻接顶点col。（5）若v的邻接顶点col未被访问过的，则col入队列。（6）继续查找顶点v的另一个新的邻接顶点
15、col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。,广度优先遍历的程序实现：（邻接表、C+）,/图的一般结构 struct graph_node;struct AdjList int id;AdjList*next;int n_nodes,S_index=0;graph_node nodes maxN;int visited maxN;AdjList*adj maxN;,标识项点有没有访问过,每个顶点都有邻接链表,邻接链表的节点数据结构,广度优先遍历的程序实现:（邻接表、C+）,置每个点标识为“未访问”,从所有未被访问的点k出发，调用BFS(k),void se
16、arch()int k;for(k=0;kn_nodes;k+)visitedk=0;for(k=0;kn_nodes;k+)if(!visitedk)BFS(k);,宽度优先遍历的程序实现：（邻接表、C+）,int q maxN;void BFS(int k)int front,back;q0=k;front=back=0;for(;fronnext)if(!visitedj-id)q+back=j-id;visitedj-id=+S_index;,BFS用的队列，一般全局,Front=back,队列不空,访问k的所有相邻的节点,例1、双栈排序(NOIP2008 提高组),给出N(1=n=1
17、000)个未排序的数，要求用两个栈将它排好序。有4种操作：1、入栈12、出栈13、入栈24、出栈2必须满足栈的先进后出的性质。不能排序则输出-1可以排序则输出字典序最小的操作序列。,这道题的关键还是在于构图和染色。,首先是构图：将所有数都看成点，两个点ai和aj之间连一条边的条件为ai和aj不能进入同一个栈。而不能进入同一个栈又如何判断呢？,如果存在k使得ijk且akaiaj则ai和aj不能进入同一个栈。,构图完毕，问题就渐渐明朗了，如果图中存在奇环则问题必然无解。,然后按照输入的顺序对图进行二染色，染到1的入1栈，染到2的入2栈。,这样每个数字进哪个栈都知道，剩下的就是模拟了。,图的连通分量
18、最小生成树问题（MST）桥和割顶,Sec3.图的连通性问题,生成树问题,无向图的最小生成树（贪心思想）Prim算法，适用于点少的图Kruskal算法，适用于边少的图有向图的最小树形图,局域网(net)某局域网内有n(n=100)台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网络卡的现象。我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)=1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要除去一些连线，使得网络中没有回路，并且被除去网线的f(i,j)最大，请求出这个最大值。,实际问题,生成树：一个|V|个点的图，取
19、其中|V|-1条边，并连接所有的顶点，则组成原图的一个生成树。属性：|v|-1条边、连通、无环。最小生成树：加权图的最小生成树是一棵生成树，其所有边的权值之和不会大于其它任何生成树。简单讲：找出连接所有点的最低成本路线,最小生成树(MST）,红边连接了所有顶点,所以构成一棵生成树权和=1+2+4+4+7+8+9,环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边),最小生成树(MST)-算法原理,9,4,剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为这些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MS
20、T，且每个MST中都包含一条最小交叉边。,最小生成树(MST)-算法原理,7,4,9,最小边原则：图中权值最小的边(如果唯一的话)一定在最小生成树上。唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。,最小生成树(MST)-算法原理,Prim算法构建MST的过程,将1号节点置入集合S中。找到所有连接S中的节点和非S中的节点的边中的权值最小的那一条，并标记这条边，同时将连接的非S中的节点加入S集合。重复2步骤，直到所有节点都在S中了。,1,2,4,3,5,6,1,2,3,1,2,3,1,2,1,2,算法描述1：(1)将G剪切成两个集合A、B，A中只有一个点r(2)取最小
21、权的交叉边(x,y)，xA,yB(3)将y加入A(4)如果已经加了n-1条边，结束。否则，转(3),最小生成树(MST)-Prim算法,算法描述2：MST_Prim(G,r)/从任意点r出发，生长成一MST for i=1 to n do disi/初始化每点到A集合的最小值 inAi false/设顶点不在A中disr 0/将r设为0（或-），准备取出for i=1 to n do v get-min()/取dis?中最小的值c和顶点v,inA v true/v放入A中 sum sum+c/c加入MST的总和中 updata(v)/枚举交叉边(v,B),改进dis,最小生成树(MST)-Pr
22、im算法,算法要点：每次求最小权交叉边时，如果都重新计算，则显然要枚举(x,y)-xA,yB。O(n2)时间复杂度。其实每次A中只是增加一个新顶点v，最多有交叉边(v,y)，修改量只有与v有边的顶点，为O(n)。只需记录下B中的每个元素y与A所有元素中最小权边，则求最小值最多为O(n)-有时可以用“堆”优化。,最小生成树(MST)-Prim算法,Kruskal算法同样是常用的求最小生成树的算法之一，其算法思想如下：K r u s k a l算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成
23、一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。这个算法可以用并叉集优化到o(e*(e)的时间复杂度。(表示阿克曼反函数),最小生成树(MST)-Kruskal算法,找到连接两个不同连通分量（由已标记的边构成的）的边中，权值最小的那一条，标记这条边。重复1步骤，直到所有节点都在同一连通分量中。,1,2,4,3,5,6,1,2,3,1,2,3,1,2,1,2,最小生成树(MST)-Prim算法,MST_Kruskal(G)(1)将G所有
24、条边按权从小到大排序；图mst开始为空(2)从小到大次序取边(x,y)(3)若加入边(x,y)，mst就有环，则放弃此边，转(2)(4)将边(x,y)加入mst，如果已经加了n-1条边，结束。否则，转(2),最小生成树(MST)-Kruskal算法,算法要点：Kruskal算法的最难点在于怎样判断加入边(x,y)后是否形成了环。问题可化为：判断边(x,y)的两个顶点x,y在图（实际是森林）mst中是否已经连通。如果已经连通，加入边将形成环；否则，不形成环。并查集：连通点集之类问题，有高效算法-并查集。,最小生成树(MST)-Kruskal算法,算法描述：MST_Kruskal(G)for i=
25、1 to n do fi i;/初始化并查集 sort(e,e+m);/边按大小排序c 0;/取边的计数器for i=1 to m do/从小到大取边 v find_set(ei.v);/左端点所在连通块“根”u find_set(ei.u);/右端点所在连通块“根 if(u,v 不在同一连通块上)/如果不在同一连通块 union(v,u);/合并两连通块 sum=sum+gvu;/加入这条边的权 if(+c=n-1)break;/if 取了n-1条边，结束,最小生成树(MST)-Kruskal算法,时间复杂度分析Prim算法普通的方法 O(|V|2)Prim算法中用“堆”方法 O(|E|+|
26、V|)*log|V|)-对稀疏图较好Kruskal算法 O(|E|*log|E|+|N|*A(|V|)-对稀疏图较好,最小生成树(MST)-时间复杂度,次小生成树,根据kruskal算法，不难证明，任意一棵次小生成树必然是由最小生成树换掉一条边。,1、先求最小生成树。O(E+V)log E),2、在生成树上DFS求出任意两点间路径上的最大边权FIJ。O(V2),3、穷举所有不在生成树上的边e=，求出minwe-Fst。O(E),时间复杂度：O(E+V)log E),例2、hurdles(USACO),给出一个N(1=n=300)个点M(1=m=25,000)条边的无向图，给出T(1=t=40,
27、000)个询问，询问要求寻找一条从节点s，到节点t的路径使得该路径的边权的最大值最小，只需输出最大值即可。,Hurdles.in5 6 21 2 123 2 81 3 52 5 33 4 42 4 83 41 2,Hurdles.out48,朴素想法：对于每次询问做一遍DFS时间复杂度：O(T*M),标准算法：1、求出原图的最小生成树。2、对于每个询问，在最小生成树上进行DFS找出最大边即可。,时间复杂度：O(N+M)*logM+T*N),最小生成树的应用示例（构图）,Newstart.pdf,最小生成树的动态维护,公路建设,与其实说桥和割顶，不如说是图的dfs树的运用。而桥和割顶，只是dfs
28、树的一个比较重要的运用。,图的dfs树,即对图进行深度优先遍历所形成的一棵树。性质：任何一棵图的dfs树不能可能有横向边而只可能有返祖边。,桥和割顶,桥和割顶,桥：定义：连通图中的一条边，如果删去这一条边，那么整个图就不再连通了。割顶：连通图中的一个点，如果删去这个点和相关的边，那么整个图就不再连通了。（这里只讨论无向图中的桥和割顶）,在左图中，DE之间的边即为这张图中唯一的一个桥。而D,E则分别为这张图中的两个割顶。,在dfs树中，我们不难发现，对于一个桥，必然没有一条返祖边跨越这条边，反之，则必然存在一条返祖边跨越这条边。,桥和割顶,桥和割顶,考虑到上面的这一个性质，我们就可以引入时间戳来
29、求一个图的桥了。要判断一条边是不是桥，只需要看它的子树中，有没有一条返祖边返回到这条边的上面。因此，我们对于每个节点，维护一个访问时间和它的子树的最早访问时间。由于dfs树没有横向边，这一点很好地保证了，一个节点的子树的最早访问时间比这个节点的访问时间早，那么就存在一条返祖边返回到这个节点的祖先。通过这种方式，我们就能够求出一个图中的桥了。,伪代码：Dfs(u)t=t+1;timeu=t;min_timeu=t vstu=true;for(u,v)E do if(vstv=false)dfs(v);min_timeu=min(min_timeu,min_timev);else min_time
30、u=min(min_timeu,timev);if(min_timeutimeu)u节点到父亲的边不是桥,桥和割顶,桥和割顶,思考：如何求一个图的割顶？（与求图的桥非常的相似）,只需要考虑一个节点的所有子树（不包括该节点本身）是否有返祖边即可。（计算桥的时候需要考虑该节点本身）,Sec4.最短路,最短路，是图论中最基本的问题，也有着广泛的运用。解决这一问题的算法也有很多种。今天，主要就介绍一些较为常见的最短路算法。,全局最短路径算法：Floyd,单源最短路径算法：Dijkstra Bellman-ford SPFA,最短路径：对在权图G=(V,E),从一个源点s到汇点t有很多路径，其中路径上权
31、和最少的路径，称从s到t的最短路径。简单讲：找出连接两个给定点的最低成本路径单源最短路径问题：求从源点s到其它所有点的最短路径问题。,最短路径(ShortestPath)-定义,三角形性质 设源点s到点x、y的最短路径长度为disx、disy。x与y之间的距离是lenxy，则有下面的“三角形定理”：disx+lenxy=disy 松驰 若在处理过程中，有两点x、y出现不符合“三角形定理”，则可改进一下松驰：if(disx+lenxy disy)disy=disx+lenxy;,最短路径(ShortestPath)-属性,X,Y,S,如果边没有负权的，我们可以用类似Prim算法的贪心算法Dijk
32、stra算法。算法描述1：SP_Dijkstra(G,s)(1)将G中顶点分成两个集合A、B，A集合中由已经求出最短路径的顶点组成，B集合是其它顶点。开始时A中只有一个点s(2)从B集合中取一个当前最短的顶点v(3)把v加入A集合，并对v相连的顶点试做“松驰”(4)如果|A|=|V|，结束。否则转(2),最短路径-Dijkstra算法,Dijkstra算法,Dijkstra算法中心+,1,2,4,3,3,1,6,3,2,+,+,+,0,Dist值,4,3,2,1,节点号,3,2,6,5,4,选择,标记,扩展,算法描述2：SP_Dijkstra(G,s)/求单源s到其它点的最短距离 for i=
33、1 to n do disi/初始化每点到s距离 inAi false/设顶点不在A中diss 0/将diss设为0，准备取出for i=1 to n do v get-min()/取dis?中最小的值c和顶点v,inA v true/v放入A中 updata(v)/检查(v,B),松驰dis?sum sum+c/c加入MST的总和中,最短路径-Dijkstra算法,与prim不相同点,如果边有负权的话，Dijkstra算法是错误的。这里需要不断迭代地做“松驰”，直到无“松驰”为止。算法描述3：SP_Bellman(G,s)(1)初始化每点到s点的最短距离为(2)取所有边(x,y)，看x能否对
34、y松驰。(3)如果没有任何松驰，则结束break。(4)如果松驰次数N，转(2)(5)否则，图中有“负圈”。,最短路径-Bellman-ford算法,算法说明：Bellman-ford算法N次迭代就可以判断图中是否有“负环”。取所有边有两种方法：(1)扫描每一点的邻接链表(2)用有序点对(x,y)记录边时，可直接取边。但要请注意对无向图，要注意(y,x)也要松驰。对于求s到某点t的最短距离，可能因为其它地方有“负环”而出现问题，要预处理。,最短路径-Bellman-ford算法,算法描述4：SP_Bellman(G,s)/求单源s到其它点的最短距离 for i=1 to n do disi/初
35、始化每点到s距离diss 0/将diss设为0for i=1 to n do/最多迭代n rel=false;/是否有松驰标志 for 每条边(x,y)/取图的每一条边 if(disx+lenxydisy)/不满足三角形性质 disy=disx+lenxy;/松驰disy rel=true;if rel=false return 0;/没有一次松驰，则结束 return-1;/迭代了n次，有负圈,最短路径-Bellman-ford算法,对迭代的改进：SPFA算法 Bellman-ford算法中，每次都要检查所有的边。这个看起来比较浪费，对于边(x,y)，如果上一次disx没有改变，则本次的检查
36、显然是多余的。我们每次只要从上次刚被“松驰”过的点x，来看看x能不能松驰其它点即可。SPFA算法中用BFS中的队列来存放刚被“松驰”过的点。由于顶点个数为|V|，队列如果用数组的话显然要用“循环队列”使用空间。,最短路径-SPFA算法,算法描述：SP_SPFA(G,s)/求单源s到其它点的最短距离 for i=1 to n do disi;visi false;/初始化每点到s距离,不在队列diss 0;/将diss设为0viss true;count 1;/s放入队列head 0;tail 0;q0=s;/队列头尾指针while(count0)do v qhead;/队头节点v for 每条
37、边(v,i)/与v相连的每一条边 if(disv+lenvidisi)/不满足三角形性质 disi disv+lenvi;/松驰disi if(visi=false)/不在队列，则加入队列 visi true;count+1;tail+1;qtail=i;visv false;head+1;count-1;/v出队列,最短路径-SPFA算法,求每对节点之间最短距离问题：例如，求一个图的直径，即所有最短路径中最长的。如果多次调用单源最短路径算法，效果并不好。特别是对有负边的图。如果无负环，则有简单的Floyd-warshell算法。这是动态规划算法。,最短路径-Floyd算法,动态规划算法定义d
38、 i,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=min di,k,k-1+dk,j,k-1,di,j,k-1 边界条件 di,j,0=lenij（不存在的边权可为）,最短路径-Floyd算法,算法描述6：SP_Floyd(G)/求每对节点的最短距离 for i=1 to n do for j=1 to n do disi,j lenij;/初始化边界条件for k=1 to n do/K放在最外层，数组少一维
39、for i=1 to n do for j=1 to n do if(disi,k+diskjdisi,j)/状态转移 disi,j disik+diskj;,最短路径-Floyd算法,Floyd算法,主要用于解决一类全局最短路的问题。优点：常数小，编程复杂度低缺点：时间复杂度高，往往无法解决一类单源最短路的问题,For i=1 to n 1.取V-S中的一顶点u使disu=mindisv|vV-S 2.S=S+u 3.For V-S中每个顶点v do Relax(u,v,W),Dijkstra算法,优化：1.用临接表存边 2.用二叉堆（最小堆）维护V-S集合中节点当前dis值算法复杂度从O(
40、V2)降到O(VV+E),Dijkstra算法,最为经典的解决单源最短路径的算法不优化：优点：编程复杂度低缺点：时间复杂度不是很理想，所有边权必须非负 优化后：有点：时间复杂度理想缺点：编程复杂度略高（如果用c+选手用优先队列，可能空间复杂度较高），所有边权必须非负,Bellman-ford算法,基本流程：对每一条边，都进行V次松弛操作。如果不存在负权环，可以证明，任意一条最短路都至多经过V个点，这一点保证了算法的正确性。此外，Bellman-ford算法还可以用于判断一个图中是否有负权环，经过V次操作后，再进行一次松弛操作，如果还有边可以松弛，则说明该图存在负权环。,伪代码：for i=1
41、to|V|-1 dofor(u,v)E do relax(u,v,w);判断负权环for(u,v)E doIf disu+wdisv return false,时间复杂度太高！,优化：SPFA算法,在Bellman-ford算法的实现过程中，实际上我们进行了大量的冗余计算。尤其是在后面的松弛过程中，枚举每一条边事实上浪费了大量的时间。由此，我们引入了SPFA算法。SPFA算法的本质还是Bellman-ford，但是它通过一个队列，去掉了大量的冗余计算，大大加速了算法。,While(Q!=empty)u=Q.top;for(u,v)E do if(relax(u,v,W)and(v V-Q)Q=
42、Q+v;Q=Q-u;,时间复杂度O(K*E),Dijkstra单源 非负 O(|V|2)对稠密图好可用“堆”优化 O(|E|*log|V|)对稀疏图较好Bellman-Ford单源 无负环 O(|V|*|E|)可先用Dijkstra预处理优化SPFA用更新队列优化,时间复杂度平均好，但不确定。Floyd全源 无负环 O(|V|2),最短路径-算法比较,例3、phoneline(USACO),有N(1=n=1000)个点，M(1=m=10000)条边，寻找一条从结点1到结点N的路径，使得其中各边长度的最大值最小。并且给定一个整数K(0=k=300)，可以使路径中的K条边长度变为零。求最小的那个最
43、大值。,乍看和最短路没有关系，因为要求最大值最小。,二分答案？,1、对边按照长度排序。,2、二分要输出的最小的最大值P。,3、把所有边长小于等于P的边长度标为0，大于P的边长度标为1。,4、做一次单源最短路径，求出1到N的最短路径，看是否小于K。,时间复杂度：Dijkstra:N2*log M 悬！Dijkstra 堆优化:(N log N+M)log M 可行！SPFA:由于边权有许多0，松弛次数不会很多 可行！,例4、block(USACO),Bessie 来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择次短路径，而不是最短路径。农
44、村有 R(1=R=100,000)条双向的路，每条路连接 N(1=N=5000)个 结点中的两个。结点的编号是 1.N。Bessie 从结点 1出发，她的朋友(目的地)在结点 N。次短路径可以使用最短路径上的路，而且允许退回，即到达一个结点超过一次。次短路径是一种长度大于最短路径的路径(如果存在两条或多条最短路径存在，次短路径就是比 它们长，且不比其他任何的路径长的路径)。,典型的次短路径,算法并不复杂,在记录最短路径的Disti数组中同时存放到i点的最短路径和次短路径，记作Disti1和Disti2，在做松弛操作的时候同时更新最短路径和次短路径。第一遍每次都选取Disti1最小的进行松弛，在
45、Disti1全部都松弛一遍后再选取Disti2最小的进行松弛。时间复杂度同最短路径,拓扑排序在图论中有着重要的地位，在历届NOIP中，对这方面的内容也有所考察，比如03年的神经网络等等。,拓扑排序是针对有向无环图而言的。拓扑排序后形成的序列满足这样一个条件：不存在两个点u,v，u在序列中在v之前并且v在图中是u的前驱。,对于右图，一个满足条件的拓扑序列是1 2 3 4 5 6 7。然而1 2 3 5 7 6 4则不满足条件，因为7在序列中在4之前，但是4是7的前驱。,Sec.5拓扑排序,拓扑排序,我们可以通过一个队列来解决这一类问题。我们每次把入度为0的点入队，然后依次处理这些点，将这些点的出
46、边删除，删除时，顺便将新造成的入度为0的点入队，处理完某个点后，这个点出队。如此操作，直到队列为空。如果还存在某个点没有入过队，这说明这个有向图存在环。,伪代码：While(Q!=empty)u=Q.top;for(u,v)E do dec(cntv)if(cntv=0)Q=Q+v;Q=Q-u;,拓扑排序算法,寻找入度为0的节点将找到的节点放入队列中，删除所有这个节点引出的边重复1，直至没有度为0的节点如果有节点不在队列中，则说明原图中有环，否则无环。,1,2,5,3,6,4,7,求关键路径算法,对给定的图进行拓扑排序按照拓扑排序的结果扩展和标记,1,2,3,4,5,6,8,7,9,6,4,5
47、,1,1,2,4,7,9,2,4,Sec6.网络流与匹配问题,网络最大流最小费用最大流二分图的最大匹配二分图的最佳匹配,网络流算法,寻找增广链，并根据增广链修改流量。重复这一步骤，直到不再存在增广链。如果需要在此基础上求最小费用最大流，只需从增广链的选择上着手。,二分图与匹配算法,二分图的匹配算法又称匈牙利算法匈牙利算法的中心可增广轨不断寻找可增广轨，并根据可增广轨修改匹配最佳匹配只是在选择可增广轨时，将匹配的权值作为选择的条件,图的应用(模型构建),例题1:(TRAVEL)一个城市中有N个车站，已知M条连接这些车站的公共汽车单向路线，设计算法求出从第一号车站到第N号车站的最少换车次数.,分析
48、,这道题粗看起来似乎不太简单，但我们仔细分析一下题目就会发现，这道题实际上可以转化为最短路径问题来进行求解。考虑经过的所有路线中，每条路线都只保留一头一尾两个车站，则经过的车站数目再减2实际上就是所求的换车次数了。要使换车次数最少，也就是要找从1到N的一条最短路径。而图中的边也需要重新设计。在每一条路线中，任两个结点均由其中的前者向后者连一条边，然后将每条边的长度都定为1。,利用图论模型进行构造,例题2：圆桌吃饭问题 n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？,转化为图论模型,设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，
49、连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为：求m与L1,L2,Lm，使得e(Li)e(Lj)=，并且m达到最大值。,构造方法,作一圆，把圆周分成n-1等分，标上n-1个刻度，将顶点1至n-1依次排列在圆周上，顶点n放在圆心。先从圆心出发，向任意点连一条线，再从这点出发，沿圆周向左右两个方向迂回连线，直到连完圆周上所有的点，再连回圆心。这样就构造出一条哈密尔顿回路。保持所有的顶点位置不变，把所有连线围绕圆心逆时针方向旋转一个刻度，得到一条新的哈密尔顿回路。这样连续旋转(n-
50、1)div 2次，就得到了(n-1)div 2条回路。,N=5,构造图象，充分展示各变量之间的关系,【例3】01串问题(NOI)给定N,L0,A0,B0,L1,A1,B1，设计一个长度为N的01串，使得对于任何连续的长度为L0的子串，0的个数大于等于A0,且小于等于B0,对于任何连续的长度为L1的子串，1的个数大于等于A1且小于B1。,【解题分析】模式1 分析不等式,设hi为01子串s0.si(1=I=n)中1的个数，其中s0=0,h0=0。显然，由hi的定义可以得出不等式0=hi-1=hi,hi=hi-1+1,移项即得：,0=hi-hi-1-1=hi-1-hi,L0-b0=hi-hi-l0,
