数据结构第三讲

《数据结构第三讲》由会员分享，可在线阅读，更多相关《数据结构第三讲（89页珍藏版）》请在金锄头文库上搜索。

1、第三讲 图1 1本章出题特点本章出题特点 在历年统考里在历年统考里,大多以客观题不劳形式出现大多以客观题不劳形式出现,具体如下具体如下:年份年份客观客观主观主观20091(2分分)1(10分分)20102(4分分)20111(2分分)1(8分分)20124(8分分)2知识点归纳图图应用应用遍历方式遍历方式存储结构存储结构关键路径关键路径最小生成树最小生成树广度优先广度优先深度优先深度优先邻接表邻接表最短路径最短路径拓扑排序拓扑排序邻接矩阵邻接矩阵基本概念基本概念了解了解掌握掌握掌握掌握掌握、应用掌握、应用基本概念基本概念3一、图的概念和相关术语一、图的概念和相关术语图的定义图的定义 图图(Gr

2、aph)G由由两两个个集集合合V(Vertex)和和E(Edge)组组成成,记记为为G=(V,E),其其中中V是是顶顶点点的的有有限限集集合合,记记为为V(G),E是是连连接接V中两个不同顶点中两个不同顶点(顶点对顶点对)的边的有限集合的边的有限集合,记为记为E(G)。 顶点集合为空的图称为空图。顶点集合为空的图称为空图。 E(G)为空时为空时,图中只有顶点而没有边。图中只有顶点而没有边。4图的基本术语图的基本术语 1. 端点和邻接点端点和邻接点 在在一一个个无无向向图图中中,若若存存在在一一条条边边(vi,vj),则则称称vi和和vj为为此此边边的的两两个个端端点点,并并称它们互为称它们互为

3、邻接点邻接点。 在在一一个个有有向向图图中中,若若存存在在一一条条边边,则则称称此此边边是是顶顶点点vi的的一一条条出出边边,同同时时也也是是顶顶点点vj的的一一条条入入边边；称称vi和和vj分分别别为为此此边边的的起起始始端端点点(简简称称为为起起点点)和和终终止止端端点点(简简称称终终点点)；称称vi和和vj互互为为邻接点邻接点。13024(a)13024(b)52. 路径和路径长度路径和路径长度 在在一一个个图图G=(V,E)中中,从从顶顶点点vi到到顶顶点点 vj的的 一一 条条 路路 径径 是是 一一 个个 顶顶 点点 序序 列列(vi,vi1,vi2,vim,vj),若若此此图图G

4、是是无无向向图图,则则边边 (vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)属属于于 E(G)； 若若 此此 图图 是是 有有 向向 图图 ,则则,属属于于E(G)。 路路径径长长度度是是指指一一条条路路径径上上经经过过的的边边的的数数目目。若若一一条条路路径径上上除除开开始始点点和和结结束束点点可可以以相相同同外外,其其余余顶顶点点均均不不相相同同,则则称称此此 路路 径径 为为 简简 单单 路路 径径 。 例例 如如 ,有有 图图 中中,(v0,v2,v1)就是一条简单路径就是一条简单路径,其长度为其长度为2。21036 3. 连通、连通图和连通分量连通、连通

5、图和连通分量 在在无无向向图图G中中,若若从从顶顶点点vi到到顶顶点点vj有有路路径径,则则称称vi和和vj是是连通连通的。的。 若若图图G中中任任意意两两个个顶顶点点都都连连通通,则则称称G为为连连通通图图,否否则则称称为为非连通图非连通图。 无无向向图图G中中的的极极大大连连通通子子图图称称为为G的的连连通通分分量量。显显然然,任任何何连连通通图图的的连连通通分分量量只只有有一一个个,即即本本身身,而而非非连连通通图图有有多多个个连连通通分量。分量。1023102(b)(a)3“极大极大”的含义：指的是的含义：指的是对子图再增加图对子图再增加图G中的其它中的其它顶点，子图就不再连通。顶点，

6、子图就不再连通。7 4. 顶点的度、入度和出度顶点的度、入度和出度 在在无无向向图图中中,顶顶点点所所具具有有的的边边的的数数目目称为该称为该顶点的度顶点的度。 在在有有向向图图中中,以以顶顶点点vi为为终终点点的的入入边边的的数数目目,称称为为该该顶顶点点的的入入度度。以以顶顶点点vi为为始始点点的的出出边边的的数数目目,称称为为该该顶顶点点的的出出度度。一一个个顶顶点点的的入入度度与与出出度度的的和和为为该该顶顶点点的的度。度。 若若一一个个图图中中有有n个个顶顶点点和和e条条边边,每每个个顶点的度为顶点的度为di(1in),则有：则有：13024(a)13024(b)8 5. 完全图完全

7、图 若无向图中的每两个顶点之间都若无向图中的每两个顶点之间都存在着一条边存在着一条边,有向图中的每两个顶点有向图中的每两个顶点之间都存在着方向相反的两条边之间都存在着方向相反的两条边,则称则称此图为此图为完全图完全图。 显然显然,完全无向图包含有完全无向图包含有n(n-1)/2条条边边,完全有向图包含有完全有向图包含有n(n-1)条边。条边。 例如例如,图图(a)所示的图是一个具有所示的图是一个具有4个顶点的完全无向图个顶点的完全无向图,共有共有6条边。图条边。图(b)所示的图是一个具有所示的图是一个具有4个顶点的完全个顶点的完全有向图有向图,共有共有12条边。条边。 (b)10231023(

8、a)9 6. 子图子图 设设 有有 两两 个个 图图 G=(V,E)和和G=(V,E),若若 V是是 V的的 子子 集集 ,即即V V,且且E是是E的的子子集集,即即E E,则则称称G是是G的的子子图图。例例如如图图(b)是是图图(a)的的子图子图,而图而图(c)不是图不是图(b)的子图。的子图。(a)1302413024(b)13024(c)10 7. 回路或环回路或环 若若一一条条路路径径上上的的开开始始点点与与结结束束点点为为同同一一个个顶顶点点,则则此此路路径径被被称称为为回回路路或或环环。开开始始点点与与结结束束点点相相同同的的简简单单路路径被称为径被称为简单回路简单回路或或简单环简

9、单环。 例例如如,右右图图中中,(v0,v2,v1,v0)就就是是一一条简单回路条简单回路,其长度为其长度为3。102311 8. 强连通图和强连通分量强连通图和强连通分量 在有向图在有向图G中中,若从顶点若从顶点vi到到顶点顶点vj有路径有路径,则称从则称从vi到到vj是是连通连通的。的。 若图若图G中的任意两个顶点中的任意两个顶点vi和和vj都连通都连通,即从即从vi到到vj和从和从vj到到vi都都存在路径存在路径,则称图则称图G是是强连通图强连通图。例如例如,右边两个图都是强连通图。右边两个图都是强连通图。 有向图有向图G中的中的极大极大强连通子强连通子图称为图称为G的的强连通分量强连通

10、分量。显然。显然,强强连通图只有一个强连通分量连通图只有一个强连通分量,即本即本身身,非强连通图有多个强连通分量。非强连通图有多个强连通分量。1023102(b)(a)12 例例 有有n个顶点的有向强连通图最多需要多少条边？最个顶点的有向强连通图最多需要多少条边？最少需要多少需要多 少条边？少条边？ 答：有答：有n个顶点的个顶点的有向强连通图有向强连通图最多有最多有n(n-1)条边条边(构成一个有向完全图的情况构成一个有向完全图的情况)；最少有；最少有n条边条边(n个顶点个顶点依次首尾相接构成一个环的情况依次首尾相接构成一个环的情况)。 13练习题： 若一个非连通无向图有10条 边，请问，该图

11、至少有多少 个顶点？答：要保证图非连通，则至少需要两个连通分量，可让一个分量里只有一个顶点，另一个分量为一个完全图。5个顶点的无向完全图共有10个顶点，所以至少需要6个顶点。14真题演练真题演练（1）若无向图）若无向图G=（V，E）中含有）中含有7个顶点，个顶点，要保证要保证G在在任何情况下任何情况下都是连通的，则需要都是连通的，则需要的边数最少为的边数最少为 （ ） A、6 B、15 C、16 D、21（2）一个无向图有）一个无向图有16条边，若度为条边，若度为4的顶点的顶点有有3个，度为个，度为4的顶点有的顶点有3个，其余顶点的度个，其余顶点的度数均小于数均小于3，则该图至少有（，则该图至

12、少有（ ）个顶点。）个顶点。 A、10 B、11 C、12 D、1315二、图的存储结构二、图的存储结构邻接矩阵存储方法邻接矩阵存储方法 邻邻接接矩矩阵阵是是表表示示顶顶点点之之间间相相邻邻关关系系的的矩矩阵阵。设设G=(V,E)是是具具有有n(n0)个个顶顶点点的的图图,顶顶点点的的顺顺序序依依次次为为(v0,v1,vn-1),则则G的邻接矩阵的邻接矩阵A是是n阶方阵阶方阵,其定义如下：其定义如下： (1) 如果如果G是无向图是无向图,则：则： Aij= 1:若若(vi,vj)E(G) 0:其他其他 (2) 如果如果G是有向图是有向图,则：则： Aij= 1:若若E(G) 0:其他其他161

13、7(3) 如果如果G是带权无向图是带权无向图,则：则： Aij= wij :若若vivj且且(vi,vj)E(G) :其他其他(a) 带权无向图带权无向图 354126abcde3(b) 邻接矩阵邻接矩阵 6 2 6 3 4 32 3 1 4 3 5 3 5 18(b) 邻接矩阵邻接矩阵 6 2 3 3 1 4 4 5 (a) 带权有向图带权有向图 354126abcde3(4) 如果如果G是带权有向图是带权有向图,则：则： Aij= wij :若若vivj且且E(G) :其他其他19思考题：思考题：对于有对于有n个顶点个顶点e条边的无向图，邻接矩阵表示时有多少条边的无向图，邻接矩阵表示时有多

14、少个元素，多少个非个元素，多少个非0元素？元素？对于有对于有n个顶点个顶点e条边的有向图，邻接矩阵表示时有多少条边的有向图，邻接矩阵表示时有多少个元素，多少个非个元素，多少个非0元素？元素？20邻接矩阵的特点如下：邻接矩阵的特点如下： (1) 图的邻接矩阵表示是图的邻接矩阵表示是唯一唯一的。的。 (2) 无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵。因因此此,按按照照压压缩缩存存储储的的思思想想,在在具具体体存存放放邻邻接接矩矩阵阵时时只只需需存存放放上上(或或下下)三角形阵的元素即可。三角形阵的元素即可。 (3) 不不带带权权的的有有向向图图的的邻邻接接矩矩阵阵一一般

15、般来来说说是是一一个个稀稀疏疏矩矩阵阵,因因此此,当当图图的的顶顶点点较较多多时时,可可以以采采用用三三元元组组表表的的方方法法存存储储邻接矩阵。邻接矩阵。 (4) 对对于于无无向向图图,邻邻接接矩矩阵阵的的第第i行行(或或第第i列列)非非零零元元素素(或或非非元素元素)的个数正好是第的个数正好是第i个顶点个顶点vi的度。的度。21 (5) 对对于于有有向向图图,邻邻接接矩矩阵阵的的第第i行行(或或第第i列列)非非零零元元素素(或或非非元素元素)的个数正好是第的个数正好是第i个顶点个顶点vi的出度的出度(或入度或入度)。 (6) 用用邻邻接接矩矩阵阵方方法法存存储储图图,很很容容易易确确定定图

16、图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连。但但是是,要要确确定定图图中中有有多多少少条条边边,则则必必须须按按行行、按按列列对对每每个个元元素素进进行行检检测测,所所花花费费的的时时间间代代价价很很大大。这这是是用用邻邻接矩阵存储图的局限性。接矩阵存储图的局限性。228.2.2 邻接表存储方法邻接表存储方法 图图的的邻邻接接表表存存储储方方法法是是一一种种顺顺序序分分配配与与链链式式分分配配相相结结合合的的存存储储方方法法。在在邻邻接接表表中中,对对图图中中每每个个顶顶点点建建立立一一个个单单链链表表,第第i个个单单链链表表中中的的结结点点表表示示依依附附于于顶顶点点vi

17、的的边边(对对有有向向图图是是以顶点以顶点vi为尾的弧为尾的弧)。每个单链表上附设一个表头结点。每个单链表上附设一个表头结点。23 其中其中,表结点由三个域组成表结点由三个域组成,adjvex指示与顶点指示与顶点vi邻邻接的点在图中的位置接的点在图中的位置,nextarc指示下一条边或弧的结指示下一条边或弧的结点点,info存储与边或弧相关的信息存储与边或弧相关的信息,如权值等。如权值等。 表头结点由两个域组成表头结点由两个域组成,data存储顶点存储顶点vi的名称或的名称或其他信息其他信息,firstarc指向链表中第一个结点。指向链表中第一个结点。 advexnextarcinfodata

18、firstarc表头节点表节点24014 MAX_VEX-12 02 2 01234v1v2 v3 v4 v5 3 04 (b) 逆邻接表逆邻接表(a) 有向图有向图v1v2v3v4v5MAX_VEX-113 2 3 01234(a) 正邻接表正邻接表v1v2 v3 v4 v5 25思考题：思考题：对于有对于有n个顶点个顶点e条边的无向图，邻接表表示时条边的无向图，邻接表表示时有多少个表头结点，多少个表结点？有多少个表头结点，多少个表结点？对于有对于有n个顶点个顶点e条边的有向图，邻接表表示时条边的有向图，邻接表表示时有多少个表头结点，多少个表结点？有多少个表头结点，多少个表结点？26邻接表的

19、特点如下：邻接表的特点如下： (1) 邻邻接接表表表表示示不不唯唯一一。这这是是因因为为在在每每个个顶顶点点对对应应的的单单链链表表中中,各各边边结结点点的的链链接接次次序序可可以以是是任任意意的的,取取决决于于建建立立邻邻接接表表的的算算法法以及边的输入次序。以及边的输入次序。 (2) 对对于于有有n个个顶顶点点和和e条条边边的的无无向向图图,其其邻邻接接表表有有n个个顶顶点点结结点点和和2e个个边边结结点点。显显然然,在在总总的的边边数数小小于于n(n-1)/2的的情情况况下下,邻邻接接表比邻接矩阵要节省空间。表比邻接矩阵要节省空间。 (3) 对对于于无无向向图图,邻邻接接表表的的顶顶点点

20、vi对对应应的的第第i个个链链表表的的边边结结点点数数目正好是顶点目正好是顶点vi的度。的度。 (4) 对对于于有有向向图图,邻邻接接表表的的顶顶点点vi对对应应的的第第i个个链链表表的的边边结结点点数数目目仅仅仅仅是是vi的的出出度度。其其入入度度为为邻邻接接表表中中所所有有adjvex域域值值为为i的的边边结点数目。结点数目。27真题演练真题演练（1）无向图的邻接矩阵是一个）无向图的邻接矩阵是一个 （ ） A、对称矩阵、对称矩阵 B、零矩阵、零矩阵 C、上三角矩阵、上三角矩阵 D、非对称矩阵、非对称矩阵（2）关于图的存储叙述中，正确的是（关于图的存储叙述中，正确的是（ ）A、用邻接矩阵存储

21、图，占用的存储空间大小只与图中顶点、用邻接矩阵存储图，占用的存储空间大小只与图中顶点数有关，而与边数无关数有关，而与边数无关B、用邻接矩阵存储图，占用的存储空间大小只与图中边数、用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关有关，而与顶点个数无关C、用邻接表存储图，占用的存储空间大小只与图中顶点数、用邻接表存储图，占用的存储空间大小只与图中顶点数有关，而与边数无关有关，而与边数无关D、用邻接表法存储图，占用的占用的存储空间大小只与图、用邻接表法存储图，占用的占用的存储空间大小只与图中边数有关，而与顶点个数无关中边数有关，而与顶点个数无关28三、图的遍历三、图的遍历 图的

22、遍历算法有图的遍历算法有深度优先搜索算法深度优先搜索算法和和广度优先广度优先搜索算法搜索算法。采用的数据结构是。采用的数据结构是(正正)邻接链表邻接链表。 从给定图中任意指定的顶点从给定图中任意指定的顶点(称为初始点称为初始点)出发出发,按照按照某种搜索方法沿着图的边访问图中的所有顶点某种搜索方法沿着图的边访问图中的所有顶点,使每个顶使每个顶点点仅被访问一次仅被访问一次,这个过程称为图的遍历。这个过程称为图的遍历。 如如果果给给定定图图是是连连通通的的无无向向图图或或者者是是强强连连通通的的有有向向图图,则则遍遍历历过过程程一一次次就就能能完完成成,并并可可按按访访问问的的先先后后顺顺序序得得

23、到到由由该图所有顶点组成的一个序列。该图所有顶点组成的一个序列。29DFS序列：序列：21034部分合法的部分合法的DFSDFS序列：序列：2 3 0 1 42 3 0 1 4；2 1 0 4 32 1 0 4 3；2 4 3 0 12 4 3 0 1不合法的不合法的DFSDFS序列举例：序列举例：2 0 1 3 42 0 1 3 430部分合法的部分合法的BFSBFS序列：序列：2 1 3 4 0;2 3 1 4 0;2 4 1 3 02 1 3 4 0;2 3 1 4 0;2 4 1 3 0不合法的不合法的BFSBFS序列举例：序列举例：2 1 0 3 4 2 1 0 3 4 ；2 3 0

24、 4 12 3 0 4 1但但是是，若若对对上上图图采采用用上上面面的的邻邻接接表表存存储储,假假设设初初始始顶顶点点编编号号v=2, 进进行行广广度度优优先先遍遍历历的的话话，序序列列就是唯一的了。此时的遍历序列如下：就是唯一的了。此时的遍历序列如下：BFS序列：序列：2134031真题演练真题演练 (1)有有N个顶点、个顶点、E条边且用邻接表存储的有向图条边且用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是进行广度优先遍历，其算法时间复杂度是 （ ） A、O（N） B、O（E） C、O（N+E） D、O（N*E） (2)如果从无向图的任一顶点出发进行一次深度优如果从无向图的任一顶点

25、出发进行一次深度优先遍历即可访问所有顶点，则该图一定是（先遍历即可访问所有顶点，则该图一定是（ ） A. 完全图完全图 B. 连通图连通图 C.有回路有回路 D.一棵树一棵树32四、图的应用四、图的应用最小生成树最小生成树拓扑排序拓扑排序最短路径最短路径关键路径关键路径33最小生成树生成树的概念生成树的概念 一一个个连连通通图图的的生生成成树树是是一一个个极极小小连连通通子子图图,它它含含有有图图中中全全部部顶点顶点,但只有构成一棵树的但只有构成一棵树的(n-1)条边。条边。 命题：如果在一棵生成树上添加一条边命题：如果在一棵生成树上添加一条边,必定构成一个环。必定构成一个环。因因为为这这条条

26、边边使使得得它它依依附附的的那那两两个个顶顶点点之之间间有有了了第第二二条条路路径径。一一棵棵有有n个个顶顶点点的的生生成成树树(连连通通无无回回路路图图)有有且且仅仅有有(n-1)条条边边,如如果果一一个个图图有有n个个顶顶点点和和小小于于(n-1)条条边边,则则是是非非连连通通图图。如如果果它它多多于于(n-1)条边条边,则一定有回路。则一定有回路。 但是但是,有有(n-1)条边的图不一定都是生成树。条边的图不一定都是生成树。 34 由由深深度度优优先先遍遍历历得得到到的的生生成成树树称称为为深深度度优优先先生生成成树树；由由广广度度优优先先遍遍历历得得到到的的生生成成树树称称为为广广度度

27、优优先先生生成成树树。这这样样的的生生成成树树是是由由遍遍历历时时访访问问过过的的n个个顶顶点点和和遍遍历历时时经经历历的的n-1条条边组成。边组成。 对于非连通图对于非连通图,每个连通分量中的顶点集和遍历时走过每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树的边一起构成一棵生成树,各个连通分量的生成树组成非连各个连通分量的生成树组成非连通图的生成森林。通图的生成森林。 35从从1 1号顶点开始的深度优先号顶点开始的深度优先遍历序列：遍历序列：1 0 3 2 41 0 3 2 4从从1 1号顶点开始的深度优先号顶点开始的深度优先遍历序列：遍历序列：1 0 2 3 41 0 2 3 43

28、6普里姆算法普里姆算法 普里姆普里姆(Prim)算法是一种构造性算法。算法是一种构造性算法。 假假 设设 G=(V,E)是是 一一 个个 具具 有有 n个个 顶顶 点点 的的 带带 权权 连连 通通 无无 向向 图图,T=(U,TE)是是G的的最最小小生生成成树树,其其中中U是是T的的顶顶点点集集,TE是是T的的边边集集,则由则由G构造最小生成树构造最小生成树T的步骤如下：的步骤如下： 37 (1) 初始化初始化U=v。v到其他顶点的所有边为候选边；到其他顶点的所有边为候选边； (2) 重复以下步骤重复以下步骤n-1次次,使得其他使得其他n-1个顶点被加入到个顶点被加入到U中：中： 从候选边中

29、挑选权值最小的边输出从候选边中挑选权值最小的边输出,设该边在设该边在V-U中的中的顶点是顶点是k,将将k加入加入U中中,删除和删除和k关联的边；关联的边； 考察当前考察当前V-U中的所有顶点中的所有顶点vi,修改候选边：若修改候选边：若(vk,vi)的的权值小于原来和权值小于原来和vi关联的候选边关联的候选边,则用则用(vk,vi)取代后者作为候选边。取代后者作为候选边。普里姆算法普里姆算法过程过程：vkUVUkiUVUv3801234651951418271682131270432165148531621 012 34 56closestlowcost19181400000000016484

30、12403337213 025 000U V-U(i, closesti)iU，closestiVU候选边候选边 ：398.4.5 克鲁斯卡尔算法克鲁斯卡尔算法 克克鲁鲁斯斯卡卡尔尔(Kruskal)算算法法是是一一种种按按权权值值的的递递增增次次序序选选择择合合适适的的边边来来构构造造最最小小生生成成树树的的方方法法。假假设设G=(V,E)是是一一个个具具有有n个个顶点的带权连通无向图顶点的带权连通无向图,T=(U,TE)是是G的最小生成树。的最小生成树。 (1) 置置U的初值等于的初值等于V(即包含有即包含有G中的全部顶点中的全部顶点),TE的初的初值为空集值为空集(即图即图T中每一个顶点

31、都构成一个分量中每一个顶点都构成一个分量)。 (2) 将图将图G中的边按权值从小到大的顺序依次选取：若选中的边按权值从小到大的顺序依次选取：若选取的边未使生成树取的边未使生成树T形成回路形成回路,则加入则加入TE；否则舍弃；否则舍弃,直到直到TE中包含中包含(n-1)条边为止。条边为止。40035214516354652025314NOViVjW102123523143425450356125723580169246104566003311000041190123465514182716821312742真题演练真题演练例：下列关于最小生成树的叙述中，正确的例：下列关于最小生成树的叙述中，正确

32、的是是 （ ）A、最小生成树的代价是唯一的、最小生成树的代价是唯一的B、所有权值最小的边一定会出现在所有的、所有权值最小的边一定会出现在所有的最小生成树中最小生成树中C、使用普里姆算法从不同顶点开始得到的、使用普里姆算法从不同顶点开始得到的最小生成树一定相同最小生成树一定相同D、使用普里姆算法和克鲁斯卡尔算法得到、使用普里姆算法和克鲁斯卡尔算法得到的最小生成树一定相同的最小生成树一定相同43真题演练真题演练已知无向网的邻接矩阵如图所示，要求：已知无向网的邻接矩阵如图所示，要求：（1）画出该图；）画出该图；（2）按照克鲁斯卡尔算法给出该网的最小）按照克鲁斯卡尔算法给出该网的最小生成树的过程。生成

33、树的过程。 4 3 4 5 6 9 3 5 5 6 6 5 7 6 5 4 9 7 3 4 3 6 3 2 5 2 6 6 4 6 44（1）该无向网如下图所示）该无向网如下图所示0 V11 V22 V33 V44 V55 V66 V77 V8V1V3V8V2V4V5V7V63654623 6795346545(2)生成过程如下：生成过程如下：V1V3V8V2V4V5V7V6V1V3V8V2V4V5V7V62V1V3V8V2V4V5V7V623V1V3V8V2V4V5V7V6233V1V3V8V2V4V5V7V62334V1V3V8V2V4V5V7V6233442V1V3V8V2V4V5V7V

34、633445V1V3V8V2V4V5V7V633445546最短路径最短路径 对对于于带带权权的的图图,考考虑虑路路径径上上各各边边上上的的权权值值,则则通通常常把把一一条条路路径径上上所所经经边边的的权权值值之之和和定定义义为为该该路路径径的的路径长度路径长度或称或称带权路径长度带权路径长度。 从从源源点点到到终终点点可可能能不不止止一一条条路路径径,把把带带权权路路径径长长度度最最短短的的那那条条路路径径称称为为最最短短路路径径,其其路路径径长长度度(权值之和权值之和)称为称为最短路径长度最短路径长度或者或者最短距离最短距离。47从一个顶点到其余各顶点的最短路径从一个顶点到其余各顶点的最短

35、路径 问问题题：给给定定一一个个带带权权有有向向图图G与与源源点点v,求求从从v到到G中中其其他顶点的最短路径他顶点的最短路径,并限定各边上的权值大于或等于并限定各边上的权值大于或等于0。 48 采用采用狄克斯特拉狄克斯特拉(Dijkstra)算法算法求解求解 基基本本思思想想是是：设设G=(V,E)是是一一个个带带权权有有向向图图, 把把图图中中顶顶点点集集合合V分成两组：分成两组： 第第一一组组为为已已求求出出最最短短路路径径的的顶顶点点集集合合(用用S表表示示,初初始始时时S中中只只有有一一个个源源点点,以以后后每每求求得得一一条条最最短短路路径径v,vk,就就将将vk加加入入到到集集合

36、合S中中,直到全部顶点都加入到直到全部顶点都加入到S中中,算法就结束了算法就结束了) 第二组为其余未确定最短路径的顶点集合第二组为其余未确定最短路径的顶点集合(用用U表示表示)。49 按按最最短短路路径径长长度度的的递递增增次次序序依依次次把把第第二二组组的的顶顶点点加加入入S中中。在在加加入入的的过过程程中中,总总保保持持从从源源点点v到到S中中各各顶顶点点的的最最短短路径长度路径长度不大于不大于从源点从源点v到到U中任何顶点的最短路径长度。中任何顶点的最短路径长度。 此此外外,每每个个顶顶点点对对应应一一个个距距离离,S中中的的顶顶点点的的距距离离就就是是从从v到到此此顶顶点点的的最最短短

37、路路径径长长度度,U中中的的顶顶点点的的距距离离从从v到到此此顶顶点点只包括只包括S中的顶点为中间顶点的当前最短路径长度中的顶点为中间顶点的当前最短路径长度。50 (1) 初初始始时时,S只只包包含含源源点点,即即S=v,v的的距距离离为为0。U包包含含除除v外外的的其其他他顶顶点点,U中中顶顶点点u距距离离为为边边上上的的权权(若若v与与u有有边边)或或(若若u不是不是v的出边邻接点的出边邻接点)。即图的邻接矩阵中即图的邻接矩阵中v所在的行元素值。所在的行元素值。 (2) 从从U中中选选取取一一个个距距离离v最最小小的的顶顶点点k,把把k加加入入S中中(该该选选定定的的距距离就是离就是v到到

38、k的最短路径长度的最短路径长度)。 (3) 以以k为为新新考考虑虑的的中中间间点点,修修改改U中中各各顶顶点点的的距距离离：若若从从源源点点v到到顶顶点点u(uU)的的距距离离(经经过过顶顶点点k)比比原原来来距距离离(不不经经过过顶顶点点k)短短,则则修修改改顶顶点点u的的距距离离值值,修修改改后后的的距距离离值值为为顶顶点点k的的距距离离加加上上边边上的权。上的权。 (4) 重复步骤重复步骤(2)和和(3)直到所有顶点都包含在直到所有顶点都包含在S中。中。狄克斯特拉算法的过程狄克斯特拉算法的过程51顶点顶点V到到j的最小距离的最小距离MIN(cvk+wkj,cvj)52 S U dist

39、0 1 2 3 4 5 600 1,2,3,4,5,6 0,4,6,6, 1,2,3,4,5,6 0,4,6,6, 0,0,1 1 2,3,4,5,6 0,4, 2,3,4,5,6 0,4,5 5,6,6,1111, , 0,1,0,1,2 2 3,4,5,6 3,4,5,6 0,4,5,6,11, 0,4,5,6,11,9 9,0,1,2,0,1,2,3 3 4,5,6 4,5,6 0,4,5,6,11,9, 0,4,5,6,11,9, 0,1,2,3,0,1,2,3,5 5 4,6 4,6 0,4,5,6, 0,4,5,6,1010,9,9,1717 0,1,2,3,5,0,1,2,3,5

40、,4 4 6 6 0,4,5,6,10,9, 0,4,5,6,10,9,1616 0,1,2,3,5,4,0,1,2,3,5,4,6 6 0,4,5,6,10,9,16 0,4,5,6,10,9,16 path 0 1 2 3 4 5 60,0,0,0,-1,-1,-1 0,0,0,0,-1,-1,-1 0,0,0,0,1 1,0, ,0, 1 1,-1,-1,-1,-10,0,1,0, 1, 0,0,1,0, 1, 2 2,-1,-10,0,1,0, 1, 2,-10,0,1,0, 1, 2,-10,0,1,0, 0,0,1,0, 5 5, 2, , 2, 5 5 0,0,1,0, 5, 2

41、, 0,0,1,0, 5, 2, 4 4 0,0,1,0, 5, 2, 40,0,1,0, 5, 2, 453438164256147660123456distpath004660000040115 5969101711525101641656201548.5.3 每对顶点之间的最短路径每对顶点之间的最短路径 问问题题：对对于于一一个个各各边边权权值值均均大大于于零零的的有有向向图图,对对每每一一对对顶顶点点vivj,求出求出vi与与vj之间的最短路径和最短路径长度。之间的最短路径和最短路径长度。 可可以以通通过过以以每每个个顶顶点点作作为为源源点点循循环环求求出出每每对对顶顶点点之之间间的的

42、最最短短路路径径。除除此此之之外外,弗弗洛洛伊伊德德(Floyd)算算法法也也可可用用于于求求两两顶顶点点之之间最短路径。间最短路径。 55 假假设设有有向向图图G=(V,E)采采用用邻邻接接矩矩阵阵cost存存储储,另另外外设设置置一一个个二二维维数数组组A用用于于存存放放当当前前顶顶点点之之间间的的最最短短路路径径长长度度,分分量量Aij表表示当前顶点示当前顶点vi到顶点到顶点vj的最短路径长度。的最短路径长度。 弗弗洛洛伊伊德德算算法法的的基基本本思思想想是是递递推推产产生生一一个个矩矩阵阵序序列列A0,A1,Ak,An,其其中中Akij表表示示从从顶顶点点vi到到顶顶点点vj的的路路径

43、径上上所经过的顶点编号不大于所经过的顶点编号不大于k的最短路径长度。的最短路径长度。56 初初始始时时,有有A-1ij=costij。当当求求从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不不大大于于k+1的的最最短短路路径径长长度度时时,要要分分两两种种情情况考虑：况考虑： 一一种种情情况况是是该该路路径径不不经经过过顶顶点点编编号号为为k+1的的顶顶点点,此此时时该该路路径径长长度度与与从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不不大大于于k的最短路径长度相同；的最短路径长度相同； 另另一一种种情情况况是是从从顶顶点点

44、vi到到顶顶点点vj的的最最短短路路径径上上经经过过编编号号为为k+1的顶点。的顶点。57Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j)58 那么那么,该路径可分为两段该路径可分为两段: (1) 从顶点从顶点vi到顶点到顶点vk+1的最短路径的最短路径; (2) 从顶点从顶点vk+1到顶点到顶点vj的最短路径。的最短路径。 此此时时最最短短路路径径长长度度等等于于这这两两段段路路径径长长度度之之和和。这这两两种种情情况况中中的的较较小小值值,就就是是所所要要求求的的从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过的顶点编号不大于过的顶点编号不大于k+1的最短路径

45、。的最短路径。59 弗洛伊德思想可用如下的表达式来描述：弗洛伊德思想可用如下的表达式来描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1)60 采用弗洛伊德算法求解过程采用弗洛伊德算法求解过程 01235327312461 考考虑虑顶顶点点v0,A0ij表表示示由由vi到到vj,经由顶点经由顶点v0的最短路径。的最短路径。v2-v0-v1：不改变。：不改变。v2-v0-v3：不改变。：不改变。01235327312462 考考虑虑顶顶点点v1,A1ij表表示示由由vi到到vj,经由顶点经由顶点v1的最短路径。的最短路径。v0-v1-v2

46、,路路 径径 长长 度度 为为 9,将将A02改为改为9。path02改为改为1。 01235327312463 考考虑虑顶顶点点v2,A2ij表表示示由由vi到到vj,经由顶点经由顶点v2的最短路径。的最短路径。v3-v2-v0,长度为长度为4,将将A30改为改为4；v3-v2-v1,长度为长度为4,将将A31改为改为4。v1-v2-v0,长度为长度为7,将将A10改为改为7。将将path30、path31和和path10均改为均改为2。因此。因此,有：有： 01235327312464 考虑顶点考虑顶点v3,A3ij表示由表示由vi到到vj,经由顶点经由顶点v3的最短路径。的最短路径。 v

47、0-v3-v2：长度为：长度为8,A02改为改为8； v1-v3-v2-v0,长度为长度为6,A10改为改为6； v1-v3-v2,长度为长度为3, A12改为改为3。将将path02、path10后后path12均改为均改为3。 01235327312465从从0到到0路径为：路径为：0,0路径长度为：路径长度为：0从从0到到1路径为：路径为：0,1路径长度为：路径长度为：5从从0到到2路径为：路径为：0,3,2路径长度为：路径长度为：8从从0到到3路径为：路径为：0,3路径长度为：路径长度为：7从从1到到0路径为：路径为：1,3,2,0路径长度为：路径长度为：6从从1到到1路径为：路径为：

48、1,1路径长度为：路径长度为：0从从1到到2路径为：路径为：1,3,2 路径长度为：路径长度为：3从从1到到3路径为：路径为：1,3路径长度为：路径长度为：2A=Path=66从从2到到0路径为：路径为：2,0路径长度为：路径长度为：3从从2到到1路径为：路径为：2,1路径长度为：路径长度为：3从从2到到2路径为：路径为：2,2路径长度为：路径长度为：0从从2到到3路径为：路径为：2,3路径长度为：路径长度为：2从从3到到0路径为：路径为：3,2,0 路径长度为：路径长度为：4从从3到到1路径为：路径为：3,2,1 路径长度为：路径长度为：4从从3到到2路径为：路径为：3,2路径长度为：路径长

49、度为：1从从3到到3路径为：路径为：3,3路径长度为：路径长度为：067拓朴排序拓朴排序设设G=(V,E)是一个具有是一个具有n个顶点的有向图个顶点的有向图,V中顶点序列中顶点序列v1,v2,vn称为一个称为一个拓扑序列拓扑序列,当且仅当该顶点序列满足当且仅当该顶点序列满足下列条件：下列条件： 若若是是图图中中的的边边(即即从从顶顶点点vi到到vj有有一一条条路路径径),则则在序列中顶点在序列中顶点vi必须排在顶点必须排在顶点vj之前。之前。 在在一一个个有有向向图图中中找找一一个个拓拓扑扑序序列列的的过过程程称称为为拓拓扑扑排序。排序。 68 (1) 从从有有向向图图中中选选择择一一个个没没

50、有有前前驱驱(即即入入度度为为0)的的顶顶点点并并且输出它。且输出它。 (2) 从从网网中中删删去去该该顶顶点点,并并且且删删去去从从该该顶顶点点发发出出的的全全部部有向边。有向边。 (3) 重重复复上上述述两两步步,直直到到剩剩余余的的网网中中不不再再存存在在没没有有前前驱驱的顶点为止。的顶点为止。拓扑排序步骤拓扑排序步骤690 0 12 4 5 3 0 12 4 5 3 41253全部可能的拓扑排序序列：041253 041523 045123450123 401253 405123 40152370关键路径关键路径 若用带权有向图若用带权有向图(DAG)描述工程的预计进度描述工程的预计进

51、度,以顶点以顶点表示事件表示事件,有向边表示活动有向边表示活动,边边e的权的权c(e)表示完成活动表示完成活动e所所需的时间需的时间(比如天数比如天数),或者说活动或者说活动e持续时间。持续时间。 图中入度为图中入度为0的顶点（的顶点（源点源点）的）的开始事件开始事件(如开工仪如开工仪式式),出度为出度为0的顶点（的顶点（汇点汇点）表示工程）表示工程结束事件结束事件。则称这。则称这样的有向图为样的有向图为AOE网网(Activity On Edge)。 71v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a

52、11=2 一个一个AOE网网源点源点汇点汇点72 几个定义：几个定义： (1) 事件事件v的最早可发生时间：假设事件的最早可发生时间：假设事件x是源点是源点,事件事件y为为汇点汇点,并规定事件并规定事件x的发生时间为的发生时间为0。定义图中任一事件。定义图中任一事件v的最早的最早(event early)可发生时间可发生时间ve(v)等于等于x到到v所有路径长度的最大值所有路径长度的最大值,即：即： ve(v)= 上式中的上式中的MAX是对是对x到到v的所有路径的所有路径p取最大值取最大值,c(p)表示路径表示路径p的长度的长度(路径上边长之和路径上边长之和) ,即：即：c(p)= 完成整个工

53、程所需的最少时间完成整个工程所需的最少时间,等于事件等于事件y的最早可发生时的最早可发生时间间ve(y)。 73v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 源点源点汇点汇点74 整个工程完成的最短时间指的是整个工程完成的最短时间指的是：从有向图的源点到汇点的：从有向图的源点到汇点的最长路径的长度最长路径的长度，具有最大长度的路径叫关键路径。，具有最大长度的路径叫关键路径。 “关键活动关键活动”指的是：该弧上的权值增加将使有向图上的指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。最长

54、路径的长度增加。 注意：在一个注意：在一个AOE网中，可以有不止一条的关键路径。网中，可以有不止一条的关键路径。 v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 源点源点汇点汇点75 (2) 事事件件v的的最最迟迟可可发发生生时时间间：定定义义在在不不影影响响整整个个工工程程进进度度的的前前提提下下,事事件件v必必须须发发生生的的时时间间称称为为v的的最最迟迟(event late)可可发发生生时时间间,记记作作vl(v)。vl(v)应应等等于于ve(y)与与v到到y的的最最长长路路径径长长度度

55、之之差差(y是汇点是汇点),即：即： vl(v)=ve(y) - (3) 关关键键活活动动:若若活活动动v满满足足ve(v)+c(ai)=vl(w),则则称称活活动动ai为为关关键活动，键活动，ai=。 对对关关键键活活动动来来说说, ,不不存存在在富富余余时时间间。显显然然, ,关关键键路路径径上上的的活活动动都都是是关关键键活活动动。找找出出关关键键活活动动的的意意义义在在于于, ,可可以以适适当当地地增增加加对对关关键键活活动动的的投投资资( (人人力力、物物力力等等),),相相应应地地减减少少对对非非关关键键活活动动的投资的投资, ,从而减少关键活动的持续时间从而减少关键活动的持续时间

56、, ,缩短整个工程的工期。缩短整个工程的工期。 76ve(v)最早开始时间ve(v)最迟开始时间v000v139v21010v31223v42222v51717v62031v72828v8333377 只要计算出各项点的只要计算出各项点的ve(v)和和vl(v)的值的值,就能找出所有的关就能找出所有的关键活动。为了便于计算键活动。为了便于计算,引入下面两个递推式引入下面两个递推式,其中其中,x和和y分别分别是源点和汇点。是源点和汇点。 ve(x)=0 ve(w)= wx上式中的上式中的MAX对所有射入对所有射入w的边的边取最大值。取最大值。 vl(y)=0 vl(v)= vy78 (1) 对于

57、源点对于源点x,置置ve(x)=0； (2) 对对AOE网网进进行行拓拓扑扑排排序序。如如发发现现回回路路,工工程程无无法法进进行行,则则退退出；否则继续下一步。出；否则继续下一步。 (3) 按按顶顶点点的的拓拓扑扑次次序序,反反复复用用式式8.4,依依次次求求其其余余各各项项点点v的的ve(v)值值。(实实际际上上,步步骤骤(2)和和步步骤骤(3)可可以以合合在在一一起起完完成成,即即一一边边对对顶顶点点进行拓扑排序进行拓扑排序,一边求出各点的一边求出各点的ve(v)之值。之值。) (4) 对于汇点对于汇点y,置置vl(y)=ve(y)； 求求AOE网的关键活动的过程网的关键活动的过程79

58、(5) 按按顶顶点点拓拓扑扑次次序序之之逆逆序序,反反复复用用式式8.5,依依次次求求其其余余各各项项点点v的的vl(v)的的值值。即即对对v射射出出的的所所有有边边,检检查查是是否否满满足足式式8.3,若若是是,则则输出该边的有关信息输出该边的有关信息,指明该边所对应的活动是关键活动。指明该边所对应的活动是关键活动。 (6) 活活动动ai的的最最早早开开始始时时间间e(i)是是该该活活动动的的起起点点所所表表示示的的事事件件最最早发生时间。如果由边早发生时间。如果由边表示活动表示活动ai,则有则有e(i)=ve(j)。 (7) 活活动动ai的的最最迟迟开开始始时时间间l(i)是是该该活活动动

59、的的终终点点所所表表示示事事件件的的最最迟迟发发生生时时间间与与该该活活动动的的所所需需时时间间之之差差。如如果果用用边边表表示示活活动动ai,则则有有l(i)=vl(k)-ai所需时间。所需时间。80 (8) 一一个个活活动动ai的的最最迟迟开开始始时时间间l(i)和和其其最最早早开开始始时时间间e(i)的的差差额额d(i)=l(i)-e(i)是是该该活活动动完完成成的的时时间间余余量量(富富余余时时间间)。它它是是在在不不增增加加完完成成整整个个工工程程所所需需的的总总时时间间的的情情况况下下,活活动动ai可可以拖延的时间。以拖延的时间。 (9) 当一活动的时间余量为零时当一活动的时间余量

60、为零时,说明该活动必须如期完说明该活动必须如期完成成,否则就会拖延完成整个工程的进度。所以我们称否则就会拖延完成整个工程的进度。所以我们称l(i)-e(i)=0,即即l(i)=e(i)的活动的活动ai是关键活动。是关键活动。 81计算各事件的计算各事件的ve(v)如下：如下：ve(A)=0,ve(B)=ve(A)+c(a1)=6ve(C)=ve(A)+c(a2)=4ve(D)=ve(A)+c(a3)=5ve(E)=max(ve(B)+c(a4),ve(C)+c(a5)=max7,5=782ve(F)=ve(E)+c(a7)=16ve(G)=ve(E)+c(a8)=14ve(H)=ve(D)+c

61、(a6)=7ve(I)=maxve(F)+c(a10),ve(G)+c(a11),ve(H)+c(a9) =max(18,18,11=1883计算各事件的计算各事件的vl(v)如下：如下： vl(I)=ve(I)=18 vl(F)=vl(I)-c(a10)=16 vl(G)=vl(I)-c(a11)=14 vl(H)=vl(I)-c(a9)=1484 vl(E)=min(vl(F)-c(a7),vl(G)-c(a8)=7,7=7 vl(D)=vl(H)-c(a6)=12 vl(C)=vl(E)-c(a5)=6 vl(B)=vl(E)-c(a4)=6 vl(A)=min(vl(B)-c(a1),

62、vl(C)-c(a2),vl(D)-c(a3)=0,2,7=085 计算各活动的计算各活动的e(a)、l(a)和和d(a)如下：如下： 活动活动a1：e(1)=ve(A)=0,l(1)=vl(B)-6=0,d(1)=0 活动活动a2：e(2)=ve(A)=0,l(2)=vl(C)-4=2,d(2)=2 活动活动a3：e(3)=ve(A)=0,l(3)=vl(D)-5=7,d(3)=7 活动活动a4：e(4)=ve(B)=6,l(4)=vl(E)-1=6,d(4)=0 活动活动a5：e(5)=ve(C)=4,l(5)=vl(E)-1=6,d(5)=286活动活动a6：e(6)=ve(D)=5,l

63、(6)=vl(H)-2=12,d(6)=7活动活动a7：e(7)=ve(E)=7,l(7)=vl(F)-9=7,d(7)=0活动活动a8：e(8)=ve(E)=7,l(8)=vl(G)-7=7,d(8)=0活动活动a9：e(9)=ve(H)=7,l(9)=vl(G)-4=10,d(9)=3活动活动a10：e(10)=ve(F)=16,l(10)=vl(I)-2=16,d(10)=0活动活动a11：e(11)=ve(G)=14,l(11)=vl(I)-4=14,d(11)=0 87 由此可知由此可知,关键活动有关键活动有a11、a10、a8、a7、a4、a1,因此因此关键路径有两条：关键路径有两条：A-B-E-F-I和和A-B-E-G-I。 88v0v5v4v7v3v2v1v6v8a1=5a2=6a3=3a8=5a4=12a5=3a10=4a9=1a12=5a11=4a6=3a7=3a13=2v9a14=2假设一个工程的进度计划用假设一个工程的进度计划用AOE网表示，如图所示。网表示，如图所示。 求出每个事件的最早发生时间和最晚发生时间。求出每个事件的最早发生时间和最晚发生时间。 该工程完工至少需要多少时间该工程完工至少需要多少时间? 求出所有关键路径和关键活动。求出所有关键路径和关键活动。89