（全国百强校）高中信息奥赛夏令营数据结构复习课件：图的算法(共41张).ppt

1、数 据 结 构山东师大附中 赵宗昌u图的存储方式：邻接矩阵，,边表u最短路径算法：FloyedDijkstraBellman-Ford图的算法3 3 邻接矩阵是表示结点间相邻关系的矩阵。邻接矩阵是表示结点间相邻关系的矩阵。ai,j=W：0:i 到到 j 无边无边1.图的邻接矩阵表示法图的邻接矩阵表示法一.图的存储 G=(V,E)优点：存储简单；找优点：存储简单；找i邻接点方便邻接点方便（for j=1 to n do if aI,j0 then）缺点：存储空间大；找邻接点费时缺点：存储空间大；找邻接点费时 n=100000 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40

2、 3 2 4 01 2 3 4 51 2345一维数组存储顶点信息；顶点间的关系 邻接表是图的一种链式存储结构，在邻接表中，对于图中的每一个顶点u都建立一个单向链表，链表中的每一结点用来描述顶点u的邻接点。2.邻接表邻接表顶点v指向第一个邻结点link顶点v 边权w 指向下一个邻结点next邻接表的实现有两种方法：指针链表和邻接表的实现有两种方法：指针链表和。数组模拟链表实际上就是链表的线性存储，把链表用多个数数组模拟链表实际上就是链表的线性存储，把链表用多个数组或者记录来存储，操作简单方便。组或者记录来存储，操作简单方便。constconst maxn=10000;/maxn=10000;/

3、图的顶点上限图的顶点上限 maxm=100000;/maxm=100000;/图的边上限图的边上限 varvar h:array1.maxn of longint;h:array1.maxn of longint;/hi /hi用来记录顶点用来记录顶点i i的第一邻接点位置；的第一邻接点位置；v:array1.2 v:array1.2*maxm of longint;maxm of longint;/vi /vi记录第记录第i i条边的顶点编号；条边的顶点编号；w:array1.2 w:array1.2*maxm of longint;maxm of longint;/wi /wi记录第记录第

4、i i条边的长度；条边的长度；next:array1.2 next:array1.2*maxm of longint;maxm of longint;/nexti /nexti记录下一个邻接点的位置；记录下一个邻接点的位置；i j x2 5 31 3 23 5 22 3 11 2 24 5 41 4 3顶点顶点i hi11321038414512p12345678910 11 12 13 14vp25315332215441wp33222211224433nextp000042153706911readln(i,j,x);readln(i,j,x);5u建立邻接表P:=0;P:=0;For i

5、:=1 to m For i:=1 to m begin begin readln(i,j,x);readln(i,j,x);end;end;Procedure add(i,j,x)inc(p);inc(p);vp:=j;vp:=j;wp:=x;wp:=x;textp:=hi;textp:=hi;hi:=p;hi:=p;u访问结点i的邻接点:p:=hi;p:=hi;while p0 do while p0 do begin begin 处理处理i i邻接点邻接点;边边（i,vpi,vp）;p:=nextp;p:=nextp;end;end;3.边表 图的边表就是用图的边表就是用3个一维数组（或

6、者记录）来存储每条边个一维数组（或者记录）来存储每条边的两个顶点及边长，数组的元素个数等于图中边的数量。的两个顶点及边长，数组的元素个数等于图中边的数量。下标下标1234567u3141221v5254353w2243132二.拓扑排序 引例 士兵排队 有有n个士兵个士兵(1n10000)，士兵的编号依次为，士兵的编号依次为1、2、3、n。指挥官要把这。指挥官要把这n个士兵从高到矮依次排成一行。但现在指个士兵从高到矮依次排成一行。但现在指挥官无法直接获得每个人的具体身高，只能获得挥官无法直接获得每个人的具体身高，只能获得“p1比比p2高高”这样的比较结果。这样的比较结果。现在已知有现在已知有m

7、（m=100000）个高矮关系，请按照从高到低输）个高矮关系，请按照从高到低输出一种合理的排队序列。出一种合理的排队序列。【输入】【输入】第一行为一个正整数第一行为一个正整数n。第二行为一个正整数第二行为一个正整数m。以下以下m行，每行两个正整数行，每行两个正整数x、y，表示，表示x比比y高。高。【输出】【输出】一行一行n个空格隔开的正整数，表示一种合理的排队序列。个空格隔开的正整数，表示一种合理的排队序列。如：8 10 2 1 1 4 1 5 4 5 4 6 3 5 3 7 5 6 5 8 7 8把士兵看成点，一个高矮关系看成一条有向边把士兵看成点，一个高矮关系看成一条有向边一种合法的排队顺

8、序是：一种合法的排队顺序是：2 3 1 4 7 5 6 8u拓扑排序的定义及算法：对一个有向无环图对一个有向无环图G，将，将G中所有顶点排成一个线性序列，使中所有顶点排成一个线性序列，使得图中任意一对顶点得图中任意一对顶点u和和v，若，若 E，则在线性序列中，则在线性序列中u出现在出现在v之前，这个线性序列称为图之前，这个线性序列称为图G的一个拓扑序列。的一个拓扑序列。生成拓扑序列的过程叫做生成拓扑序列的过程叫做拓扑排序拓扑排序。拓扑排序拓扑排序算法描述算法描述:1.从有向图中选择一个没有前驱从有向图中选择一个没有前驱(入度为入度为0)的顶点并且输出它。的顶点并且输出它。2.从图中删去该顶点从

9、图中删去该顶点,并且删去从该顶点发出的全部有向边。并且删去从该顶点发出的全部有向边。3.返回返回1，直到剩余的图中不存在没有前趋的顶点为止。，直到剩余的图中不存在没有前趋的顶点为止。4.剩余图中还有顶点，说明该有向图中存在环，无拓扑序列。剩余图中还有顶点，说明该有向图中存在环，无拓扑序列。如果一个图有拓扑序列，拓扑序列可能不是唯一的。如果一个图有拓扑序列，拓扑序列可能不是唯一的。u算法实现：1.图的存储：邻接表 readln(n);readln(n);readln(e);readln(e);for p:=1 to e dofor p:=1 to e do begin begin readln(

10、i,j);readln(i,j);inc(dj);/inc(dj);/入度入度 vp:=j;nextp:=hi;hi:=p;vp:=j;nextp:=hi;hi:=p;end;end;2.Bfs实现：head:=0;tail:=0;head:=0;tail:=0;for i:=1 to n do if di=0 then for i:=1 to n do if di=0 then/入度为入度为0 0的入队的入队 begin inc(tail);qtail:=i;end;begin inc(tail);qtail:=i;end;while headtail dowhile head0 do /i

11、 while p0 do /i结点的邻接点去边结点的邻接点去边 begin begin dec(dvp);/dec(dvp);/入度减入度减1 1 if dvp=0 then/if dvp=0 then/入度为入度为0 0的结点入队的结点入队 begin inc(tail);qtail:=vp;end;begin inc(tail);qtail:=vp;end;p:=nextp;p:=nextp;end;end;end;end;3.输出拓扑序列（按入队序列输出队列元素）for i:=1 to n-1 do write(qi,);for i:=1 to n-1 do write(qi,);wri

12、te(qn);write(qn);u拓扑排序的应用 （动态规划）图的最长路问题 给定有向图给定有向图G，有，有n个顶点，个顶点，m条边，题目条边，题目，试求出图，试求出图G中最长路的长度。中最长路的长度。【输入格式】【输入格式】第一行：第一行：n，m 两个数字，分别表示顶点数和边数两个数字，分别表示顶点数和边数 第第2行行第第m+1行：每行三个数字行：每行三个数字x，y，z，分别表示一条边，分别表示一条边的两个端点和长度的两个端点和长度【输出格式】【输出格式】一个数一个数max，表示图，表示图G中最长路的长度。中最长路的长度。【数据范围】【数据范围】对于对于50%的数据，的数据，n=10000

13、，m=100000 对于对于100%的数据，的数据，n=100000，m=1000000 样例输入：样例输入：4 44 4 1 2 11 2 1 2 4 52 4 5 1 3 31 3 3 3 4 23 4 2 样例输出：样例输出：6 612341532分析：123415325436fi:以结点以结点i为终点的最长路径为终点的最长路径f i=max f j+d j,i j是是i的前驱结点的前驱结点目标：目标：max f i 拓扑排序的同时+DP求fi：邻接表存储邻接表存储 入度为入度为0 0的的结点入队的的结点入队,f=0;,f=0;while headtail dowhile head0 d

14、o /i while p0 do /i结点的邻接点去边结点的邻接点去边 begin begin dec(dvp);/i dec(dvp);/i的邻接点的邻接点vpvp入度减入度减1 1 if dvp=0 then/if dvp=0 then/入度为入度为0 0的结点入队的结点入队 begin inc(tail);qtail:=vp;end;begin inc(tail);qtail:=vp;end;p:=nextp;p:=nextp;end;end;end;end;u奖金问题三.最短路径算法Floyd算法算法Dijkstra算法算法Bellman-Ford算法算法SPFA算法算法明确：1 各种

15、算法的特点及其使用范围各种算法的特点及其使用范围 2 时间复杂度时间复杂度 3 最短路径的技术原理最短路径的技术原理/松弛技术（三角不等式）松弛技术（三角不等式）procedure procedure relaxrelax(u,v(u,v：longint);longint);begin begin if diss,vdiss,u+wu,v then if diss,vdiss,u+wu,v then diss,v:=diss,u+wu,v;diss,v:=diss,u+wu,v;end;end;4 不存在 ijkn12-83长度为长度为-1的负权回路的负权回路1.floyd算法（计算每一对顶点

16、间的最短路径）算法（计算每一对顶点间的最短路径）目标：把图中任意两点目标：把图中任意两点i与与j之间的最短距离都求出来之间的最短距离都求出来 di,j。原理：根据图的传递闭包思想：原理：根据图的传递闭包思想：ijkif di,k+dk,jdi,j then di,j=di,k+dk,jfor k:=1 to n dofor k:=1 to n do /枚举中间点枚举中间点 for i:=1 to n do for i:=1 to n do /起点起点 for j:=1 to n do for j:=1 to n do /终点终点 if di,k+dk,jdi,j then if di,k+dk

17、,jdi,j then di,j:=di,k+dk,j;di,j:=di,k+dk,j;算法实现：算法实现：初始化条件：初始化条件：D i,i=0 Di,j=边权，边权，i与与j有直接相连的边有直接相连的边Di,j=+，i与与j无直接相连的边。无直接相连的边。/一般设一般设 maxlongint/2?为了保存原来的邻接矩阵为了保存原来的邻接矩阵a a：令：令d=ad=a，如果不需要保存，如果不需要保存a a，直接在直接在a a上做即可。上做即可。时间复杂度：时间复杂度：O(n3)邻接矩阵存储邻接矩阵存储可以负权，但不能有负权回路可以负权，但不能有负权回路计算某一顶点到其它所有顶点的最短路径计算

18、某一顶点到其它所有顶点的最短路径 （单源最短路径问题）（单源最短路径问题）开始点（源点）：开始点（源点）：startDi:顶点顶点i到到start的最短距离。的最短距离。初始：初始：Dstart=0；Di=astart,i （无边设为（无边设为maxlongint div 2）12534107571734492.Dijkstra算法start其它其它n-1个点个点集合集合1：已求点：已求点集合集合2：未求点：未求点1、在集合、在集合2中找一个到中找一个到start距离最近的顶点距离最近的顶点k:mindk2、把顶点、把顶点k加到集合加到集合1中，同时修改集合中，同时修改集合2 中的剩余顶中的剩

19、余顶点点j的的dj是否经过是否经过k后变短。如果变短修改后变短。如果变短修改djIf dk+ak,jdj then dj=dk+ak,j3、重复、重复1，直至集合，直至集合2空为止。空为止。fillchar(f,sizeof(f),false);fillchar(f,sizeof(f),false);for i:=1 to n do di:=astard,i;for i:=1 to n do di:=astard,i;fstart:=true;/fstart:=true;/加入集合加入集合1 1 for i:=2 to n dofor i:=2 to n do begin begin min:

20、=maxlongint/2;min:=maxlongint/2;k:=0;k:=0;for j:=1 to n do for j:=1 to n do if(not fj)and(djmin)then if(not fj)and(djmin)then begin min:=dj;k:=j;end;begin min:=dj;k:=j;end;if(k=mb)then exit;if(k=mb)then exit;/找到目标找到目标 if (k=0)or(min=maxlongint)then exit;if (k=0)or(min=maxlongint)then exit;/更新结束更新结束

21、fk:=true;/fk:=true;/加入集合加入集合1 1 for j:=1 to n do /for j:=1 to n do /修改集合修改集合2 2中的中的djdj if(not fj)and(dk+ak,jdj)then if(not fj)and(dk+ak,jdj)then dj:=dk+ak,j;dj:=dk+ak,j;end;end;时间复杂度：时间复杂度：O(n2)不能有负权的边不能有负权的边堆优化：堆优化：O(n*ln(n)u3.Bellman-Ford算法 同Dijkstra算法相比，Bellman-Ford算法能够在图中的情况下解决单源最短路问题。的情况下解决单源最

22、短路问题。其基本思路为：如果两点之间有最短路，那么最多经过图中所有顶点各一次（如果经过某个顶点两次，那么我们走出了一个环。如果环的权值为非负，显然不划算；如果权值为负，则最短路不存在），也就是说，这条。根据最短路的最优子结构性质，最多包含k条边的最短路可以有最多包含k-1条边的最短路“加一条边”来求得，因此通过反复松弛每条边，即可求得源点到所有点的最短路。procedure bellman_ford;/procedure bellman_ford;/beginbegin for i:=1 to n-1 do n-1 for i:=1 to n-1 do n-1遍松弛遍松弛 for j:=1 t

23、o m do for j:=1 to m do 对对m m条边进行松弛条边进行松弛 with edgesj do with edgesj do;end;end;procedure relax(u,v,w:longint);procedure relax(u,v,w:longint);begin begin if du+wdv then dv:=du+w;if du+wdv then dv:=du+w;end;end;uvSW有负环的判定：如果还能松弛如果还能松弛 则有负环则有负环for i:=1 to for i:=1 to m m do do if du+widv then if du+wi

24、dv then 有负环有负环Bellman-Ford算法：单源最短路单源最短路 可以有负权可以有负权 能判断是否有负环能判断是否有负环 时间复杂度为时间复杂度为O(nm)u4.SPFA算法（单源）SPFASPFA算法的全称是：算法的全称是：S Shortest hortest P Path ath F Faster aster A Algorithmlgorithm SPFASPFA实际上是实际上是Bellman-FordBellman-Ford基础上的优化基础上的优化 西南交通大学段凡丁于西南交通大学段凡丁于19941994年发表的年发表的 给定的图存在给定的图存在，这时类似，这时类似Dij

25、kstraDijkstra等算法便没有了等算法便没有了用武之地用武之地；而而Bellman-FordBellman-Ford算法的复杂度又过高算法的复杂度又过高。SPFASPFA算法算法目前应用最广的最短路径算法。目前应用最广的最短路径算法。期望的期望的时间复杂度时间复杂度 (k2,e是边数是边数)存储边的关系存储边的关系实现方法：建立一个队列，初始时队列里只有起始点.di记录起始点到i所有点的最短路径.然后执行松弛操作，用依次用队列里有的点去更新所有后继结点的最短路，如果被更新成功且不在队列中则把该点加入到队列最后。重复执行直到队列为空 判断有无负环：如果某个点进入队列的次数超过N次则存在负

26、环uvijIf fi+di,xfx then fx=fi+di,xIf fi+di,xfx then fx=fi+di,xProcedure SPFA;/伪代码，循环队列 Begin Begininitialize-queue(Q);/initialize-queue(Q);/队列初始化队列初始化enqueue(Q,s);/enqueue(Q,s);/起点进入队列起点进入队列while not empty(Q)do beginwhile not empty(Q)do begin u:=dequeue(Q);/u:=dequeue(Q);/出队列结点出队列结点u u for each vadju

27、 do begin for each vadju do begin if du+(u,v)dv)then begin if du+(u,v)dv)then begin dv=du+(u,v)dv=du+(u,v)if(not v in Q)then if(not v in Q)then enqueue(Q,v);enqueue(Q,v);end;end;end;end;End;End;u例题：香甜的黄油(P195 例13-6)题意：题意：n个顶点个顶点m条边的无向图，选一个顶点条边的无向图，选一个顶点s，使，使其他其他n-1个顶点到达个顶点到达s点的路线距离和最小。点的路线距离和最小。求最小的

28、距离和。求最小的距离和。N=800;m=1450.u分析：枚举每一个结点枚举每一个结点i，作为源点求单源最短路径。求最小的，作为源点求单源最短路径。求最小的最短路径和。最短路径和。N=800 如果普通的如果普通的Dijkstra算法，时间O(n3)书上采用的堆优化的Dijkstra算法，时间O(n2*ln(n)uN800,m1450采用采用spfa算法：算法：时间：时间：O(n*km)k=2 procedure spfa(start:longint);procedure spfa(start:longint);while headtail do while headtail do begin

29、begin head:=(head+1)mod maxn;head:=(head+1)mod maxn;i:=qhead;i:=qhead;p:=hi;p:=hi;while p0 do /while p0 do /更新更新i i的邻接点的邻接点 begin begin if di+wpdvp then if di+wpdvp then begin begin dvp:=di+wp;dvp:=di+wp;if not fvp then if not fvp then begin begin tail:=(tail+1)mod maxn;tail:=(tail+1)mod maxn;qtail:=vp;fvp:=true;qtail:=vp;fvp:=true;end;end;end;end;p:=nextp;p:=nextp;end;end;end;end;谢谢 谢！谢！QQ:452378421