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

1、数 据 结 构山东师大附中 赵宗昌数 据 结 构山东师大附中 赵宗昌图的存储方式：邻接矩阵，邻接表, 边表拓扑排序 最短路径算法：FloyedDijkstraBellman-FordSPFA算法图的算法3图的存储方式：邻接矩阵，邻接表, 边表图的算法3 邻接矩阵是表示结点间相邻关系的矩阵。a1.n,1.n。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 2

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

3、的顶点上限 maxm=100000; /图的边上限var h:array1.maxn of longint; /hi用来记录顶点i的第一邻接点位置； v:array1.2*maxm of longint; /vi记录第i条边的顶点编号； w:array1.2*maxm of longint; /wi记录第i条边的长度； next:array1.2*maxm of longint; / nexti记录下一个邻接点的位置；数组模拟图的邻接表数组模拟链表实际上就是链表的线性存储，把链i j x2 5 31 3 23 5 22 3 11 2 24 5 41 4 3顶点ihi11321038414512

4、p1234567891011121314vp25315332215441wp33222211224433nextp000042153706911readln(i,j,x);inc(p);vp:=j;wp:=x;nextp:=hi;hi:=p;5i j x顶点ihi11321038414512p1建立邻接表P:=0;For i:=1 to m begin readln(i,j,x); add(i,j,x); add(j,i,x);end;Procedure add(i,j,x) inc(p); vp:=j; wp:=x; textp:=hi; hi:=p;建立邻接表P:=0;Procedure

5、add(i,j,x)访问结点i的邻接点: p:=hi; while p0 do begin 处理i邻接点vp; 边wp（i,vp）; p:=nextp; end;访问结点i的邻接点: p:=hi;3 . 边表 图的边表就是用3个一维数组（或者记录）来存储每条边的两个顶点及边长，数组的元素个数等于图中边的数量。下标1234567u3141221v5254353w22431323 . 边表 图的边表就是用3个一维数组（或者记录）来存储每二 . 拓扑排序引例 士兵排队有n个士兵(1n10000)，士兵的编号依次为1、2、3、n。指挥官要把这n个士兵从高到矮依次排成一行。但现在指挥官无法直接获得每个人

6、的具体身高，只能获得“p1比p2高”这样的比较结果。现在已知有m（m=100000）个高矮关系，请按照从高到低输出一种合理的排队序列。【输入】第一行为一个正整数n。第二行为一个正整数m。以下m行，每行两个正整数x、y，表示x比y高。【输出】一行n个空格隔开的正整数，表示一种合理的排队序列。二 . 拓扑排序引例 士兵排队如：810 2 11 41 54 54 63 53 75 65 87 8把士兵看成点，一个高矮关系看成一条有向边一种合法的排队顺序是：2 3 1 4 7 5 6 8如：8把士兵看成点，一个高矮关系看成一条有向边一种合法的排队拓扑排序的定义及算法：对一个有向无环图G，将G中所有顶点

7、排成一个线性序列，使得图中任意一对顶点u和v，若 E，则在线性序列中u出现在v之前，这个线性序列称为图G的一个拓扑序列。生成拓扑序列的过程叫做拓扑排序。拓扑排序算法描述: 1.从有向图中选择一个没有前驱(入度为0)的顶点并且输出它。2.从图中删去该顶点,并且删去从该顶点发出的全部有向边。3.返回1，直到剩余的图中不存在没有前趋的顶点为止。4.剩余图中还有顶点，说明该有向图中存在环，无拓扑序列。如果一个图有拓扑序列，拓扑序列可能不是唯一的。拓扑排序的定义及算法：对一个有向无环图G，将G中所有顶点排成算法实现：1.图的存储：邻接表readln(n);readln(e);for p:=1 to e

8、do begin readln(i,j); inc(dj); / 入度 vp:=j; nextp:=hi; hi:=p; end;算法实现：1.图的存储：邻接表2.Bfs实现：head:=0; tail:=0;for i:=1 to n do if di=0 then /入度为0的入队 begin inc(tail); qtail:=i; end;while head0 do /i结点的邻接点去边 begin dec(dvp); /入度减1 if dvp=0 then /入度为0的结点入队 begin inc(tail);qtail:=vp; end; p:=nextp; end; end;2

9、.Bfs实现：3.输出拓扑序列（按入队序列输出队列元素）for i:=1 to n-1 do write(qi, );write(qn);3.输出拓扑序列（按入队序列输出队列元素）拓扑排序的应用 （动态规划）图的最长路问题给定有向图G，有n个顶点，m条边，题目保证图G中不出现环，试求出图G中最长路的长度。【输入格式】第一行：n，m 两个数字，分别表示顶点数和边数第2行第m+1行：每行三个数字x，y ，z ，分别表示一条边的两个端点和长度【输出格式】一个数max，表示图G中最长路的长度。【数据范围】对于50%的数据，n=10000，m=100000对于100%的数据，n=100000，m=100

10、0000拓扑排序的应用 （动态规划）图的最长路问题样例输入：4 41 2 12 4 51 3 33 4 2样例输出：612341532样例输入：12341532分析：保证图G中不出现环 拓扑排序动态规划123415325436fi:以结点i为终点的最长路径f i =max f j +d j,i j是i的前驱结点目标：max f i 分析：保证图G中不出现环 拓扑排拓扑排序的同时+DP求fi：邻接表存储入度为0的的结点入队,f=0;while head0 do /i结点的邻接点去边 begin dec(dvp); /i的邻接点vp入度减1 if fi+wpfvp then fvp:=fi+wp;

11、 / 由i更新vp if dvp=0 then /入度为0的结点入队 begin inc(tail);qtail:=vp; end; p:=nextp; end; end;拓扑排序的同时+DP求fi：奖金问题奖金问题三 . 最短路径算法Floyd算法Dijkstra算法Bellman-Ford算法SPFA算法三 . 最短路径算法Floyd算法明确：1 各种算法的特点及其使用范围2 时间复杂度3 最短路径的技术原理/松弛技术（三角不等式）procedure relax(u,v：longint); begin if diss,vdiss,u+wu,v then diss,v:=diss,u+wu,

12、v; end;明确：1 各种算法的特点及其使用范围/松弛技术（三角不等式4 不存在 负权回路ijkn12-83长度为-1的负权回路4 不存在 负权回路ijkn12-83长度为-1的负权回路1 . floyd算法（计算每一对顶点间的最短路径）目标：把图中任意两点i与j之间的最短距离都求出来 di,j。原理：根据图的传递闭包思想：ijkif di,k+dk,jdi,j then di,j=di,k+dk,j1 . floyd算法（计算每一对顶点间的最短路径）目标：把for k:=1 to n do /枚举中间点 for i:=1 to n do /起点 for j:=1 to n do /终点 i

13、f di,k+dk,jdi,j then di,j:=di,k+dk,j;算法实现：初始化条件：D i, i =0 Di,j=边权，i与j有直接相连的边Di,j= + ，i与j无直接相连的边。 / 一般设 maxlongint/2 ?为了保存原来的邻接矩阵a：令d=a，如果不需要保存a，直接在a上做即可。时间复杂度：O(n3)邻接矩阵存储可以负权，但不能有负权回路for k:=1 to n do /枚举中间计算某一顶点到其它所有顶点的最短路径 （单源最短路径问题）开始点（源点）：startDi:顶点i到start的最短距离。初始：Dstart=0；Di=astart,i （无边设为maxlon

14、gint div 2）12534107571734492 . Dijkstra算法计算某一顶点到其它所有顶点的最短路径 start其它n-1个点集合1：已求点集合2：未求点1、在集合2中找一个到start距离最近的顶点k : mindk2、把顶点k加到集合1中，同时修改集合2 中的剩余顶点j的dj是否经过k后变短。如果变短修改djIf dk+ak,jdj then dj=dk+ak,j3、重复1，直至集合2空为止。start其它n-1个点集合1：已求点集合2：未求点1、在集fillchar(f,sizeof(f),false);for i:=1 to n do di:=astard,i; fs

15、tart:=true; / 加入集合1for i:=2 to n do begin min:=maxlongint/2; k:=0; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; if (k=mb) then exit; /找到目标 if (k=0)or(min=maxlongint) then exit;/更新结束 fk:=true; / 加入集合1 for j:=1 to n do /修改集合2中的dj if (not fj) and (dk+ak,jdj) then dj:=dk+ak,j;

16、 end;fillchar(f,sizeof(f),false);时间复杂度：O(n2)不能有负权的边堆优化：O(n*ln(n)时间复杂度：O(n2)3 . Bellman-Ford算法同Dijkstra算法相比，Bellman-Ford算法能够在图中存在负权边的情况下解决单源最短路问题。其基本思路为：如果两点之间有最短路，那么最多经过图中所有顶点各一次（如果经过某个顶点两次，那么我们走出了一个环。如果环的权值为非负，显然不划算；如果权值为负，则最短路不存在），也就是说，这条路最多有n-1条边。根据最短路的最优子结构性质，最多包含k条边的最短路可以有最多包含k-1条边的最短路“加一条边”来求得

17、，因此通过反复松弛每条边n-1遍，即可求得源点到所有点的最短路。3 . Bellman-Ford算法同Dijkstra算法相procedure bellman_ford;/边表存图begin for i:=1 to n-1 do n-1遍松弛 for j:=1 to m do 对m条边进行松弛 with edgesj do relax(u,v,w);end;procedure relax(u,v,w:longint); begin if du+wdv then dv:=du+w; end;uvSWprocedure bellman_ford;/边表存图p有负环的判定：如果还能松弛 则有负环fo

18、r i:=1 to m do if du+widv then 有负环有负环的判定：如果还能松弛 则有负环Bellman-Ford算法： 单源最短路 可以有负权 能判断是否有负环 时间复杂度为O(nm)Bellman-Ford算法：4 . SPFA算法（单源）SPFA算法的全称是：Shortest Path Faster AlgorithmSPFA实际上是Bellman-Ford基础上的优化西南交通大学段凡丁于1994年发表的给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地；而Bellman-Ford算法的复杂度又过高。SPFA算法目前应用最广的最短路径算法。期望的时间复杂度

19、O(ke) (k2,e是边数)邻接表存储边的关系4 . SPFA算法（单源）SPFA算法的全称是：Short实现方法：建立一个队列，初始时队列里只有起始点. di记录起始点到i所有点的最短路径.然后执行松弛操作，用依次用队列里有的点去更新所有后继结点的最短路，如果被更新成功且不在队列中则把该点加入到队列最后。重复执行直到队列为空判断有无负环：如果某个点进入队列的次数超过N次则存在负环uvijIf fi+di,xfx then fx=fi+di,x实现方法：uvijIf fi+di,xfx Procedure SPFA;/伪代码，循环队列 Begininitialize-queue(Q); /队列初始化enqueue(Q,s); /起点进入队列while not empty(Q) do begin u:=dequeue(Q); /出队列结点u for each vadju do begin if du+(u,v)dv) then begin dv=du+(u,v) if (not v in Q) then enqueue(Q,v); end;end;