清华大学朱明方数据结构5.ppt

第五章第五章 图图5.1 图的基本概念图的基本概念 一一.图的定义图的定义 二二.顶点的度顶点的度 三三.路径与连通路径与连通5.2 图的存储结构图的存储结构 一一.邻接矩阵邻接矩阵 二二.邻接表邻接表 三三.边集数组边集数组 四四.邻接多重表邻接多重表5.3 图的遍历图的遍历 一一.深度优先遍历深度优先遍历 二二.广度优先遍历广度优先遍历5.4 最短距离问题最短距离问题5.1 图的基本概念图的基本概念一一.图的定义图的定义 图图图形结构简称。允许集合中的元素间有任意前后件关系。图形结构简称。允许集合中的元素间有任意前后件关系。即数据元素间是多对多的联系。每个元素构成一个顶点。即数据元素间是多对多的联系。每个元素构成一个顶点。图的二元组定义为：图的二元组定义为：G=(V,E)V顶点集合，顶点集合，EV上的一个二元关系。上的一个二元关系。例如，图：例如，图：G1=(V(G1),E(G1)V(G1)=A,B,C E(G1)=A,B,A,C,B,C,C,B 每个序偶对应一条每个序偶对应一条有向边有向边(带箭头的边带箭头的边)G2=(V(G2),E(G2)V(G2)=v1,v2,v3 E(G2)=(v1,v2),(v1,v3),(v2,v3)每个无序对对应一条每个无序对对应一条无向边无向边(无箭头的边无箭头的边)AB CG1 V1V2 V3G25.1 图的基本概念图的基本概念一一.图的定义图的定义 E(G1)、E(G2)可以看成是边可以看成是边(有向边或无向边有向边或无向边)的集合。的集合。根据图的二元组定义，根据图的二元组定义，G=(V,E)有：有：图图由顶点集合由顶点集合V和边集合和边集合E组成。组成。图图G1中的边为有向边中的边为有向边有向图。有向图。图图G2中的边为无向边中的边为无向边无向图。无向图。若图若图G =(V,E)与图与图G=(V,E)满足：满足：V(G)V(G),E(G)E(G)则称则称G 为为G的子图。的子图。例如，图例如，图G：图图G：G 为为G的子图的子图 AB CG1 V1V2 V3G2AB DE FCAB CE5.1 图的基本概念图的基本概念二二.顶点的度顶点的度 无向图：无向图：边边(Vi,Vj)，端点端点Vi,Vj互为邻接点。互为邻接点。顶点的度顶点的度顶点连接的边数顶点连接的边数D(Vi)，若图中每两个顶点间都有边若图中每两个顶点间都有边完全图完全图边数边数为最大值为最大值n(n-1)/2。有向图：有向图：边边 Vi,Vj Vi的出边、的出边、Vj的入边；的入边；起点起点ViVj的入边邻接点的入边邻接点；终点终点VjVi的出边邻接点的出边邻接点。顶点入度顶点入度顶点连接的入边数；顶点连接的入边数；D-(Vi)顶点出度顶点出度顶点连接的出边数；顶点连接的出边数；D+(Vi)顶点的度顶点的度=顶点入度顶点入度+顶点出度。顶点出度。设顶点设顶点i的度为的度为D(Vi)，图中有图中有n个顶点个顶点,则其边数则其边数m为：为：m=握手定理。握手定理。推论推论：图中度为奇数的顶点有偶数个。：图中度为奇数的顶点有偶数个。AB DE F例如：例如：AB CD例如：例如：5.1 图的基本概念图的基本概念三三.路径与连通路径与连通无向图，若存在边：无向图，若存在边：(vp,vi1)，(vi1,vi2)，(vin-1,vin)，(vin,vq)，有向图，若存在边：有向图，若存在边：vp,vi1,vi1,vi2 ,vin-1,vin ,vin,vq ，则：则：顶点序列顶点序列(vp,vi1，vin,vq)为为vp到到vq的一条的一条路经路经。路径长度路径长度路径上所有边的数目。路径上所有边的数目。顶点顶点vi到到vj有路径有路径vi到到vj连通连通。无向图中，任意两顶点都连通无向图中，任意两顶点都连通连通图连通图。极大的连通子图极大的连通子图连通分量连通分量。有向图中，任意两顶点都连通有向图中，任意两顶点都连通强连通图强连通图。极大的强连通子图极大的强连通子图强连通分量强连通分量。(c)强连通图强连通图 (d)强连通分量强连通分量(a)连通图连通图(b)连通分连通分量量AB C DEA BD CAB CDA BD CA BD C5.1 图的基本概念图的基本概念三三.路径与连通路径与连通 实际问题中抽象出来的图，图中每条边上可以标有具体实际问题中抽象出来的图，图中每条边上可以标有具体 意义的数值意义的数值 边上的数值边上的数值边的权。边的权。边上有权的图边上有权的图带权图带权图(有值图、网有值图、网)。例如，例如，(a)带权无向图带权无向图 (b)带权有向图带权有向图 A BE D57 1083215C 4 8 10 6 1 7 5 2ab ec d5.2 图的存储结构图的存储结构一一.邻接矩阵表示邻接矩阵表示 方法：方法：用一个一维数组存储顶点信息；用一个一维数组存储顶点信息；用一个矩阵用一个矩阵(二维数组二维数组)表示顶点的邻接关系。表示顶点的邻接关系。设图设图G中有中有n个顶点，其序号分别为个顶点，其序号分别为1，2，n,数组数组D(1:n)存储顶点信息；存储顶点信息；二维数组二维数组A(1:n,1:n)存储存储n个顶点的邻接关系个顶点的邻接关系邻接矩阵邻接矩阵 例如例如,图图:邻接矩阵：邻接矩阵：12 3bac12 3BAC1231231 2 31 2 35.2 图的存储结构图的存储结构一一.邻接矩阵表示邻接矩阵表示 带权图的邻接矩阵表示带权图的邻接矩阵表示:设用二维数组设用二维数组A(1:n,1:n)存储带权图存储带权图n个顶点的邻接关系；个顶点的邻接关系；表示表示任一边的权值。任一边的权值。例如，图：例如，图：邻接矩阵：邻接矩阵：10 1120 12 3 bac12312312 3BAC12 16461 2 31 2 35.2 图的存储结构图的存储结构一一.邻接矩阵表示邻接矩阵表示 邻接矩阵中容易实现：邻接矩阵中容易实现：查找图中任意一条边或边上的权查找图中任意一条边或边上的权(带权图带权图)；查找任意顶点的邻接点；查找任意顶点的邻接点；确定任一顶点的度。确定任一顶点的度。前例：前例：查找的时间复杂度查找的时间复杂度O(n)，n顶点数顶点数 当边数当边数n2时，存储空间利用率低。时，存储空间利用率低。123 结点结点1的边、的边、度度、邻接点邻接点123 结点结点1的出边、的出边、出出 度度、邻接点邻接点 结点结点1的入度、的入度、入边入边、邻接点邻接点 5.2 图的存储结构图的存储结构二二.邻接表表示邻接表表示 方法：方法：(1)对图中每个顶点建立一个邻接关系的单链表对图中每个顶点建立一个邻接关系的单链表顶点邻接表顶点邻接表；(2)用一个向量存各邻接表头指针。用一个向量存各邻接表头指针。邻接表结点邻接表结点(边结点边结点)：表头结点：表头结点：若是无权图，表结点中无权值域。若是无权图，表结点中无权值域。例如，图：例如，图：邻接表：邻接表：出边邻接关系。出边邻接关系。顶点号顶点号权值权值下一邻接点下一邻接点元素元素第一个邻接结点指针第一个邻接结点指针 12 3bac 1 2 3BACABCabc21123020303020305.2 图的存储结构图的存储结构二二.邻接表表示邻接表表示 邻接表中，邻接表中，便于：便于：找任一顶点的边找任一顶点的边(或出边或出边)；找任一顶点的邻接点找任一顶点的邻接点(或出边邻接点或出边邻接点)、度度(出度出度)平均查找的时间复杂度：平均查找的时间复杂度：O(e/n)不便于：不便于：查找任一顶点的入边和入边邻接点查找任一顶点的入边和入边邻接点(有向图有向图)。逆邻接表：逆邻接表：对每个顶点建立链接入边邻接点的单链表。对每个顶点建立链接入边邻接点的单链表。例如，图：例如，图：逆邻接表：逆邻接表：逆邻接表中，逆邻接表中，便于：便于：查找任一顶点的入边或入边上的权；查找任一顶点的入边或入边上的权；查找任一顶点的入边邻接点、入度。查找任一顶点的入边邻接点、入度。1a2b3c30113020 12 3bac5.2 图的存储结构图的存储结构二二.邻接表表示邻接表表示三三.十字邻接表十字邻接表(有向图有向图)四四.表结构：把邻接表与逆邻接表结合为一个表。表结构：把邻接表与逆邻接表结合为一个表。五五.链表结点：链表结点：六六.表头结点：表头结点：七七.例如，图：例如，图：八八.九九.十字邻接表：十字邻接表：十十.邻接矩阵的第邻接矩阵的第i行行邻接表中第邻接表中第i个单链表个单链表十一十一.邻接矩阵的第邻接矩阵的第i列列逆邻接表中第逆邻接表中第i个单链表个单链表1a2b3c310 12 3bac3200121302300十字链表。十字链表。元素元素入边指针入边指针出边指针出边指针边起点边起点边终点边终点权值权值下一入边指针下一入边指针 下一出边指针下一出边指针5.2 图的存储结构图的存储结构三三.边集数组表示边集数组表示方法：方法：用一个一维数组存储顶点信息；用一个一维数组存储顶点信息；利用一个数组存图中所有的边利用一个数组存图中所有的边,数组元素个数数组元素个数图边数；图边数；数组中每个元素存储一条边的起点、终点、权值，数组中每个元素存储一条边的起点、终点、权值，次序任意。次序任意。无向图，边起点可以任意选定；无权图，省去权值存储。无向图，边起点可以任意选定；无权图，省去权值存储。例如，图：例如，图：边集数组：边集数组：适合：适合：对边依次处理的运算。对边依次处理的运算。123112起点起点.233终点终点.1234起点起点1123终点终点2332权值权值12164612 3BAC12 1646 12 3bac 5.2 图的存储结构图的存储结构四四.邻接多重表表示邻接多重表表示(无向图无向图)方法：方法：图中每一条边用一个存储结点表示，图中每一条边用一个存储结点表示，有一端点相同的边连接在一起。有一端点相同的边连接在一起。边边(i,j)结点：结点：顶点结点：顶点结点：例如，图：例如，图：邻接多重表：邻接多重表：适合：适合：对指定边进行操作。对指定边进行操作。12 3bac顶点值顶点值指向第一条边指向第一条边标志标志 顶点顶点i指向指向i的下一条边的下一条边顶点顶点j指向指向j的下一条边的下一条边1a2b3c2312010305.3 图的遍历图的遍历 遍历：遍历：从某顶点出发从某顶点出发,按一定搜索方法按一定搜索方法,不重复访问所有顶点。不重复访问所有顶点。问题：问题：可能存在多条路径都能到达同一顶点。可能存在多条路径都能到达同一顶点。解决办法：解决办法：对已访问过的顶点做标记对已访问过的顶点做标记(用一个辅助数组用一个辅助数组)。遍历方法：遍历方法：深度优先搜索遍历，广度优先搜索遍历。深度优先搜索遍历，广度优先搜索遍历。一一.深度优先搜索遍历深度优先搜索遍历(纵向优先搜索遍历纵向优先搜索遍历)思路：思路：与树的先根遍历类似。与树的先根遍历类似。方法：方法：访问一个顶点访问一个顶点vi，并将其标记为已访问；并将其标记为已访问；从从vi的一个未访问过的邻接点出发，的一个未访问过的邻接点出发，做深度优先搜索遍历；做深度优先搜索遍历；当当vi的所有邻接点均已访问时，则回退到上一个顶点的所有邻接点均已访问时，则回退到上一个顶点vk，从从vk的另一未访问的邻接点开始做深度优先遍历的另一未访问的邻接点开始做深度优先遍历。显见：是一个递归过程。显见：是一个递归过程。5.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.例如，图：例如，图：三三.四四.从顶点从顶点1出发出发(初始顶点初始顶点)，做深度优先遍历的过程为：，做深度优先遍历的过程为：五五.访问访问v1(结点值结点值A)，标记标记v1,取取v2做深度优先遍历；做深度优先遍历；六六.访问访问v2(B)，标记标记v2,取取v5做深度优先遍历；做深度优先遍历；七七.访问访问v5(E)，标记标记v5,取取v6做深度优先遍历；做深度优先遍历；八八.访问访问v6(F)，标记标记v6,回退回退 v5 v2；九九.ABCDEFG 1 2 3 456 75.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.例如，图：例如，图：三三.四四.访问访问v7(G)，标记标记v7,取取v3做深度优先遍历做深度优先遍历;五五.访问访问v3(C),标记标记v3,回退回退 v7,取取v4做深度优先遍历做深度优先遍历;六六.访问访问v4(D)，标记标记v4,回退回退 v7 v2 v1；过程结束。过程结束。七七.遍历结果：遍历结果：A,B,E,F,G,C,D八八.1.深度优先遍历的递归算法描述深度优先遍历的递归算法描述ABCDEFG 1 2 3 456 75.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.1.深度优先遍历的递归算法描述深度优先遍历的递归算法描述三三.遍历算法描述与其存储方式有关。遍历算法描述与其存储方式有关。四四.假设用邻接矩阵表示图假设用邻接矩阵表示图：五五.例如，图：例如，图：邻接矩阵邻接矩阵六六.七七.若定义数组若定义数组MARK(1:n)记录记录n个顶点的访问标志：个顶点的访问标志：八八.定义数组定义数组A(1:n,1:n)表示图的邻接矩阵。表示图的邻接矩阵。ABCDEFG 1 2 3 456 712345671 2 3 4 5 6 75.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.1.深度优先遍历的递归算法深度优先遍历的递归算法三三.若以若以vi(顶点顶点i)为初始顶点，深度优先搜索遍历算法：为初始顶点，深度优先搜索遍历算法：四四.输入：顶点数组输入：顶点数组V(1:n)，邻接矩阵邻接矩阵A(1:n,1:n)，五五.标志数组标志数组MARK(1:n)，顶点数顶点数n，初始顶点号初始顶点号i六六.输出：深度优先遍历序列输出：深度优先遍历序列七七.PROCEDURE DFS1(A,V,MARK,n,i)以以Vi为初始顶点深度优先搜为初始顶点深度优先搜索遍历索遍历八八.PROCESS (V(i)访问顶点访问顶点i九九.MARK(i)1 标记顶点标记顶点i已访问已访问十十.FOR j=1 TO n DO 依次搜索依次搜索Vi的所有邻接点的所有邻接点十一十一.IF A(i,j)=1 AND MARK(j)=0 THEN十二十二.kj;DFS1(A,V,MARK,n,k)十三十三.十四十四.RETURN 5.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.1.深度优先遍历的递归算法深度优先遍历的递归算法三三.若以邻接表表示图。若以邻接表表示图。邻接表：邻接表：四四.例如图：例如图：V LINK 五五.若定义顶点存储结点空间为若定义顶点存储结点空间为 V(1:n)和和LINK(1:n)，六六.边结点存储空间为边结点存储空间为 NUM(1:2m)和和 NEXT(1:2m),七七.(有向图为有向图为LINK(1:n),NUM(1:m)m 边数，边数，n 顶点顶点数，数，八八.访问标记数组访问标记数组 MARK(1:n).ABCDEFG 1 2 3 456 71A2B3C4D5E6F7G21112223370707060505406405.3 图的遍历图的遍历一一.深度优先搜索遍历深度优先搜索遍历二二.1.深度优先遍历的递归算法深度优先遍历的递归算法三三.设以设以i为初始顶点为初始顶点,深度优先搜索遍历算法深度优先搜索遍历算法(省去输入、输省去输入、输出说明出说明)四四.PROCEDURE DFS2(V,LINK,NUM,NEXT,n,i)五五.PROCESS (V(i)六六.MARK(i)1七七.P LINK(i)取取Vi的邻接表表头指针的邻接表表头指针i八八.WHILE p0 DO 依次搜索依次搜索Vi的每个邻接点的每个邻接点九九.j NUM(p)取邻接点顶点号取邻接点顶点号十十.IF MARK(j)=0 THEN十一十一.DFS2(V,LINK,NUM,NEXT,n,j)从未访问过的从未访问过的Vj出发出发遍历遍历十二十二.P NEXT(p)取取Vi的下一邻接点的下一邻接点十三十三.十四十四.RETURN5.3 图的遍历图的遍历一、深度优先搜索遍历一、深度优先搜索遍历1.深度优先遍历的递归算法深度优先遍历的递归算法 如果是带权图，算法如果是带权图，算法 DFS1 中，对顶点中，对顶点vi的邻接点的搜索条件的邻接点的搜索条件 应修改为：应修改为：A(i,j)0 AND A(i,j)AND MARK(j)=0 以上算法的前提：连通图。以上算法的前提：连通图。若是非连通图，只要以图中每一个未访问过的顶点为初始顶点若是非连通图，只要以图中每一个未访问过的顶点为初始顶点 调用调用 DFS1 或或 DFS2 即可。即可。例如：例如：FOR i=1 TO n DO IF MARK(i)=0 THEN CALL DFS1(A,V,MARK,n,i)即可对邻接矩阵表示的非连通图进行深度优先搜索遍历。即可对邻接矩阵表示的非连通图进行深度优先搜索遍历。其余类推。其余类推。思考：算法思考：算法DFS1、DFS2的的C语言描述语言描述?5.3 图的遍历图的遍历 一、深度优先搜索遍历一、深度优先搜索遍历 2.深度优先遍历的非递归算法深度优先遍历的非递归算法 基本思想：基本思想：设置一个栈，用以记录刚访问过的顶点设置一个栈，用以记录刚访问过的顶点 i 的边结点的边结点(邻接点邻接点)；从被访问过的邻接点返回到顶点从被访问过的邻接点返回到顶点i 时，从栈顶弹出一个边接时，从栈顶弹出一个边接 点点(邻接点邻接点)；然后从刚出栈的边结点然后从刚出栈的边结点(邻接点邻接点)出发沿单链表出发沿单链表(矩阵第矩阵第i 行行)找找 到下一个邻接点进行处理。到下一个邻接点进行处理。具体的算法描述，不同的存储方式会有所不同。具体的算法描述，不同的存储方式会有所不同。以下为邻接矩阵和邻接表存储方式下算法的基本思路。以下为邻接矩阵和邻接表存储方式下算法的基本思路。5.3 图的遍历图的遍历一、深度优先搜索遍历一、深度优先搜索遍历 2.深度优先遍历的非递归算法深度优先遍历的非递归算法 邻接表存储方式下，算法的基本思路：邻接表存储方式下，算法的基本思路：设顶点表存储空间为设顶点表存储空间为V(1:n)和和LINK(1:n)，边结点存储空间为边结点存储空间为 NUM(1:2m)和和NEXT(1:2m)m 边数，边数，n顶点数。顶点数。设置一个栈设置一个栈S，栈顶指针栈顶指针top，初始栈空初始栈空(top=0);(1)访问并标记初始顶点访问并标记初始顶点i，取边结点的结点号取边结点的结点号p=LINK(i)；(2)如果如果p0：若若j=NUM(p)未访问过，则访问并标记顶点未访问过，则访问并标记顶点j，做：做：PUSH(S,p,top)，p=LINK(j)，转转(2)；若顶点若顶点 j 已访问过，则已访问过，则 p=NEXT(p),转转(2)；(3)如果如果p=0：若若top0，则则 POP(S,p,top);p=NEXT(p),转转(2)；若若top=0，则遍历过程结束。则遍历过程结束。5.3 图的遍历图的遍历一、深度优先搜索遍历一、深度优先搜索遍历 2.深度优先遍历的非递归算法深度优先遍历的非递归算法 邻接矩阵存储方式下，算法的基本思路邻接矩阵存储方式下，算法的基本思路：设邻接矩阵为设邻接矩阵为A(1:n,1:n)；设置一个栈设置一个栈S(1:n,1:2)，栈顶指针栈顶指针top，初始栈空初始栈空(top=0)；访问并标记初始顶点访问并标记初始顶点i，j1；(1)如果如果 j n：若若A(i,j)=1且顶点且顶点 j 未访问过，访问并标记未访问过，访问并标记 j，PUSH(S,i,j,top)，ij，j1，转转(1)；否则，否则，j j+1，转转(1)；如果如果 j n，转转(2)；(2)如果如果 top0，POP(S,i,j,top),j j+1,转转(1)；如果如果 top=0，则遍历过程结束。则遍历过程结束。思考：两种存储方式下的算法描述？思考：两种存储方式下的算法描述？5.3 图的遍历图的遍历二二.广度优先搜索遍历广度优先搜索遍历(横向优先搜索遍历横向优先搜索遍历)思路：思路：与树的按层遍历类似与树的按层遍历类似 方法：方法：访问并标记初始顶点访问并标记初始顶点vi；访问并标记访问并标记vi所有未访问过的邻接点所有未访问过的邻接点 vi1，vi2，viS；依次访问并标记依次访问并标记vi1，vi2，viS的所有未访问的邻接点；的所有未访问的邻接点；依次类推，直到所有与依次类推，直到所有与vi连通的顶点都被访问。连通的顶点都被访问。显然，先被访问的顶点，其邻接点也先被访问。显然，先被访问的顶点，其邻接点也先被访问。实现时需要设置一个队列，用于记住访问顶点的次序：实现时需要设置一个队列，用于记住访问顶点的次序：访问初始顶点，并将其顶点号入队；访问初始顶点，并将其顶点号入队；重复操作：重复操作：队头顶点号出队；队头顶点号出队；依次访问它的每一个未访问的邻接点，并将其顶点号入队；依次访问它的每一个未访问的邻接点，并将其顶点号入队；直到队列空，遍历过程结束。直到队列空，遍历过程结束。5.3 图的遍历图的遍历二二.广度优先搜索遍历广度优先搜索遍历(横向优先搜索遍历横向优先搜索遍历)例如，图：例如，图：从顶点从顶点1出发出发(初始顶点初始顶点),进行广度优先搜索遍历的过程为：进行广度优先搜索遍历的过程为：设置一个队列，初始为空；设置一个队列，初始为空；访问访问v1(结点值结点值A)，标记标记v1，顶点号入队；顶点号入队；重复操作：重复操作：顶点号顶点号1出队，依次访问其邻接点出队，依次访问其邻接点2、3、4，标记它们，标记它们，并依次入队；并依次入队；顶点顶点2出队，依次访问其邻接点出队，依次访问其邻接点5、6、7(顶点顶点1已访问已访问)，标记它们并依次入队；标记它们并依次入队；ABCDEFG 1 2 3 456 7 5.3 图的遍历图的遍历 二二.广度优先搜索遍历广度优先搜索遍历 例如，图：例如，图：顶点顶点3出队，其邻接点出队，其邻接点1、7都已访问；都已访问；顶点顶点4出队，其邻接点出队，其邻接点1、7都已访问；都已访问；依次类推，到顶点依次类推，到顶点7出队，队列空，遍历过程结束。出队，队列空，遍历过程结束。遍历结果为：遍历结果为：A,B,C,D,E,F,G ABCDEFG 1 2 3 456 7 5.3 图的遍历图的遍历 二二.广度优先搜索遍历广度优先搜索遍历 具体的遍历算法描述与存储方式有关。具体的遍历算法描述与存储方式有关。邻接表存储方式下的算法描述，邻接表存储方式下的算法描述，P120 如果以邻接矩阵存储图，且：如果以邻接矩阵存储图，且：设：邻接矩阵为设：邻接矩阵为A(1:n,1:n)，顶点数组为顶点数组为V(1:n)，标志数组标志数组MARK(1:n),工作队列工作队列Q(1:n)，队头指针队头指针front，队尾指针队尾指针rear,结点结点i的入队操作为：的入队操作为：ADDQ(Q,i)，出队操作为：出队操作为：DELQ(Q,i),初始队列空，初始队列空，front=rear=0,邻接矩阵存储方式下的算法描述：邻接矩阵存储方式下的算法描述：5.3 图的遍历图的遍历 二二.广度优先搜索遍历广度优先搜索遍历 PROCESS (V(i);MARK(i)1;ADD(Q,i)WHILE frontrear DO DEL(Q,i)FOR j=1 TO n DO IF A(i,j)=1 AND MARK(j)=0 THEN PROCESS (V(j);MARK(j)1 ADD(Q,j)RETURN 5.4 最短距离问题最短距离问题 一一.最短距离的概念最短距离的概念 无权图中：无权图中：路径长度路径长度图中两顶点间的路径上所包含的边数。图中两顶点间的路径上所包含的边数。最短距离最短距离两顶点间的各条路径中最短的路径长度。两顶点间的各条路径中最短的路径长度。该路径称为该路径称为最短路径。最短路径。带权图中：带权图中：带权路径长度带权路径长度图中两顶点之间路径上所有边的权值之和。图中两顶点之间路径上所有边的权值之和。最短路径最短路径两顶点间的各条路径中带权路径长度最短的路径。两顶点间的各条路径中带权路径长度最短的路径。最短路径的长度称为最短路径的长度称为最短距离。最短距离。求图中某顶点到其余各顶点的最短路经求图中某顶点到其余各顶点的最短路经单原点最短路径问题。单原点最短路径问题。求最短路径的出发顶点求最短路径的出发顶点源点源点，目的顶点，目的顶点终点终点。本节讨论：带权图的单源点最短路径问题。本节讨论：带权图的单源点最短路径问题。5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 求单源点最短路径问题，包括：求单源点最短路径问题，包括：(1)求出源点到图中其余各顶点的最短距离。求出源点到图中其余各顶点的最短距离。(2)找出源点到图中其余各顶点具有最短距离的路径。找出源点到图中其余各顶点具有最短距离的路径。一般方法一般方法(迪克斯特拉迪克斯特拉(Dijkstra)算法算法)：基本思想：基本思想：按照最短路径长度的递增次序，逐步求出从源点按照最短路径长度的递增次序，逐步求出从源点 到其余各顶点的最短距离及路径。到其余各顶点的最短距离及路径。做法：做法：(1)首先求出从源点首先求出从源点i到其余顶点的最短距离最小的到其余顶点的最短距离最小的 一条路径，设终点为一条路径，设终点为m；(2)以顶点以顶点m为中间点，用为中间点，用vivm的最短路径和最短距离的最短路径和最短距离 对其余顶点的当前最短距离做必要修改，得到新的对其余顶点的当前最短距离做必要修改，得到新的 当前最短当前最短 路径和最短距离；路径和最短距离；(3)依次类推，直到求出源点到其余各顶点的全部最短距离依次类推，直到求出源点到其余各顶点的全部最短距离 和最短路径。和最短路径。5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 算法的基本思路：设算法的基本思路：设vi为源点。为源点。设置辅助空间：设置辅助空间：向量向量S(1:n)：存放已找到最短路径存放已找到最短路径(相对于相对于vi)的顶点号。的顶点号。向量向量DIST(1:n)：存放当前最短距离。存放当前最短距离。初始，初始，vi到各顶点的边数值，若没有边则置到各顶点的边数值，若没有边则置。向量向量PATH(1:n)：存放表示存放表示vi到其余顶点的当前最短路径的到其余顶点的当前最短路径的 单链表的头指针。单链表的头指针。若顶点若顶点j还未找到路径，还未找到路径，PATH(j)=0。(1)找出不在找出不在S中，且中，且DIST值最小的顶点值最小的顶点m，m记入记入S，即即S(m)=1，此时，此时，DIST(m)为为vi vm的最短路径长度；的最短路径长度；使使 PATH(m)指向指向vi vm的的最短路径，最短路径，5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 (2)以以vm为中间点，修改为中间点，修改vi到未到未在在S中的其余顶点中的其余顶点vj的最短路径的最短路径 和长度：和长度：若若 DIST(j)DIST(m)+(m j)边权值，则修改边权值，则修改DIST(j)：DIST(j)=DIST(m)+(m j)边权值；边权值；若修改了若修改了DIST(j)，则要修改相应的路径：则要修改相应的路径：删除已有的删除已有的vi vm路径；路径；复制复制vi vm路径到路径到vi vj路径上路径上;顶点顶点 j 接在接在vi vm路径之后路径之后,生成新的生成新的vi vj当前最短路径。当前最短路径。(3)重复重复(1)、(2)、(n-2)次，则求得次，则求得vi到其余各顶点的最短路径到其余各顶点的最短路径 及其长度。及其长度。5.4 最短距离问题最短距离问题二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 例如，对有向图：例如，对有向图：求求v1到其余顶点的最短路径过程：到其余顶点的最短路径过程：（初始，仅有（初始，仅有v1在在S中）中）4 8 10 6 1 7 5 2ab ec d 12 5 3 4SDISTPATH11002043004010507111204050 5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 第一步第一步:求出求出v1 v2的最短路径及其长度，的最短路径及其长度，v2加入加入S中；中；以以v2为中间点重新考虑为中间点重新考虑v1到到v3、v4、v5 的最短路径及长度：的最短路径及长度：4 8 10 6 1 7 5 2ab ec d 12 5 3 4SDISTPATH1100214301040105071112040501230 5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 第二步第二步:求出求出v1v5的最短路径及其长度，的最短路径及其长度，v5加入加入S中；中；以以v5为为中间点重新考虑中间点重新考虑v1到到v3、v4 的最短路径及长度：的最短路径及长度：4 8 10 6 1 7 5 2ab ec d 12 5 3 4SDISTPATH1100214301040851711120550123040 5.4 最短距离问题最短距离问题 二二.求单源点最短路径问题的方法求单源点最短路径问题的方法 第三步第三步:求出求出v1 v4的最短路径及其长度，的最短路径及其长度，v4加入加入s中；中；以以v4为中间点重新考虑为中间点重新考虑v1到到v3 的最短路径及长度：的最短路径及长度：v1 v3的最短路径及其长度已求出的最短路径及其长度已求出(重复上述步骤重复上述步骤n-2次次)，v1到其余所有结点的的最短路径与长度都以求出，过程结束。到其余所有结点的的最短路径与长度都以求出，过程结束。4 8 10 6 1 7 5 2ab ec d 12 5 3 4SDISTPATH1100214301041851711120550123040 5.4 最短距离问题最短距离问题 三三.算法描述算法描述 1.假设图的顶点数为假设图的顶点数为n，用邻接矩阵用邻接矩阵A(1:n,1:n)表示带权图表示带权图 vi到其余各顶点的最短路径的边结点结构为：到其余各顶点的最短路径的边结点结构为：NUM路径上的顶点号，路径上的顶点号，NEXT路径上下一个边结点的结点号。路径上下一个边结点的结点号。输入：图的邻接矩阵输入：图的邻接矩阵A(1:n,1:n)，图的顶点数图的顶点数n，源顶点源顶点i。输出：输出：vi到其余各顶点的最短路径及长度。到其余各顶点的最短路径及长度。设定：数组设定：数组S(1:n)保存已求出最短路径的终点号；保存已求出最短路径的终点号；数组数组DIST(1:n)保存各终点的当前最短距离；保存各终点的当前最短距离；向量数组向量数组PATH(1:n)保存表示各终点当前最短路径保存表示各终点当前最短路径 的链表的头指针的链表的头指针。求源点求源点vi到其余各顶点的最短路径和长度的到其余各顶点的最短路径和长度的 迪克斯特拉算法描述如下迪克斯特拉算法描述如下:NUM NEXT 5.4 最短距离问题最短距离问题 三三.算法描述算法描述 1.假设图的顶点数为假设图的顶点数为n，用邻接矩阵用邻接矩阵A(1:n,1:n)表示带权图表示带权图 FOR j=1 TO n DO IF i=j THEN S(j)1 初始化初始化S ELSE S(j)0 DIST(j)A(i,j)初始化初始化DIST IF (DIST(j)AND (ji)THEN 初始化初始化PATH NEW(p2);NUM(p2)j;NEXT(p2)0 NEW(p1);NUM(p1)i;NEXT(p1)p2 PATH(j)p1 ELSE PATH(j)0 5.4 最短距离问题最短距离问题 三三.算法描述算法描述 1.假设图的顶点数为假设图的顶点数为n，用邻接矩阵用邻接矩阵A(1:n,1:n)表示带权图表示带权图 FOR k=1 TO n-2 DO w ;m i FOR j=1 TO n DO 找出第找出第k个已求得最短路径和长度的终点个已求得最短路径和长度的终点m IF (S(j)=0 AND (DIST(j)w)THEN w DIST(j);m j IF (mi)THEN S(m)1 找出的找出的m，加入到加入到S中中 ELSE EXIT vi与剩余顶点已没有路径与剩余顶点已没有路径 FOR j=1 TO n DO 以以m为中间点，对未在为中间点，对未在S中的顶点中的顶点 修改相应的修改相应的DIST和和PATH元素元素 IF (S(j)=0)AND (DIST(m)+A(m,j)DIST(j)THEN DIST(j)DIST(m)+A(m,j)修改修改vivj的当前最短距离的当前最短距离 p PATH(j)5.4 最短距离问题最短距离问题 三三.算法描述算法描述 1.假设图的顶点数为假设图的顶点数为n，用邻接矩阵用邻接矩阵A(1:n,1:n)表示带权图表示带权图 WHILE p 0 DO 清除清除vivj的此前最短路径的此前最短路径 PATH(j)NEXT(p);DISPOSE(p);p PATH(j)p PATH(m)WHILE p 0 DO 复制复制vivm的最短路径到的最短路径到vivj的路径上的路径上 NEW(q);NUM(q)NUM(p)IF PATH(j)=0 THEN PATH(j)q ELSE NEXT(s)q s q;p NEXT(p)NEW(q);NUM(q)j;NEXT(q)0 j加到加到ViVj最短路径最后最短路径最后 NEXT(S)q RETURN 5.4 最短距离问题最短距离问题 三三.算法描述算法描述 2.假设用邻接表表示由各顶点的带权图假设用邻接表表示由各顶点的带权图 邻接表的表头结点和边结点结构如下：邻接表的表头结点和边结点结构如下：表头结点：表头结点：边结点结构：边结点结构：数组数组S、DIST、PATH的定义同邻接矩阵表示。的定义同邻接矩阵表示。迪克斯特拉算法相应部分改动如下迪克斯特拉算法相应部分改动如下(相对于邻接矩阵表示相对于邻接矩阵表示)：S、DIST、PATH 定义、初始化思路类似。定义、初始化思路类似。找出第找出第k个已求得最短路径与长的终点个已求得最短路径与长的终点m方法不变。方法不变。修改：以修改：以m为中间点对未加入为中间点对未加入S的顶点修改相应的的顶点修改相应的DIST和和 PATH元素部分，即第二层的最后一个元素部分，即第二层的最后一个FOR循环。循环。元素元素第一条边结点第一条边结点VLINK顶点号顶点号 边权值边权值下一邻接点下一邻接点NUMWEINEXT 5.4 最短距离问题最短距离问题 三三.算法描述算法描述 2.假设用邻接表表示由各顶点的带权图假设用邻接表表示由各顶点的带权图 第二层的第二个第二层的第二个FOR循环修改为：循环修改为：p=LINK(m)WHILE p0 DO 以以m为中间点，重新考虑其未在为中间点，重新考虑其未在S中中 邻接点的邻接点的DIST值、值、PATH值值 j NUM(p);w WEI(p)IF (S(j)=0)AND (DIST(m)+wDIST(j)THEN DIST(j)DIST(m)+w 修改修改vivj的当前最短距离的当前最短距离 t PATH(j)WHILE t 0 DO 清除清除vivj的的此前最短路径此前最短路径 PATH(j)NEXT(t);DISPOSE(t);t PATH(j)5.4 最短距离问题最短距离问题 三三.算法描述算法描述 2.假设用邻接表表示由各顶点的带权图假设用邻接表表示由各顶点的带权图 t PATH(m)WHILE t0 DO 复制复制ViVm的最短路径到的最短路径到ViVj的路径上的路径上 NEW(q);NUM(q)NUM(t);WEI(q)WEI(t)IF PATH(j)=0 THEN PATH(j)q ELSE NEXT(s)q