第六章 图PPT讲稿.ppt

《第六章 图PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第六章 图PPT讲稿.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 图第1页，共113页，编辑于2022年，星期三【学习目的要求学习目的要求】1.掌握图的基本概念。掌握图的基本概念。2.熟练掌握图的存储结构。熟练掌握图的存储结构。3.熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。4.掌握最小生成树的普里姆和克鲁斯卡尔算法。掌握最小生成树的普里姆和克鲁斯卡尔算法。5.掌握最短路径的两个经典算法掌握最短路径的两个经典算法:迪杰斯特拉和弗洛伊德算法。迪杰斯特拉和弗洛伊德算法。6.掌握拓扑排序的概念，会求拓扑序列。掌握拓扑排序的概念，会求拓扑序列。7.了解关键路径。了解关键路径。第第6章章 图图 第2页

2、，共113页，编辑于2022年，星期三6.1 图的基本术语图的基本术语6.2 图的存储结构图的存储结构6.3 图的遍历图的遍历6.4 最小生成树最小生成树6.5 最短路径最短路径6.6 拓扑排序拓扑排序6.7 关键路径关键路径第第6章章 图图 第3页，共113页，编辑于2022年，星期三由结点集合及结点间的关系集合组成的一种数据结构。由结点集合及结点间的关系集合组成的一种数据结构。记为记为GG(V,E)其中：其中：V是是G的的顶点顶点集合，是有穷非空集；集合，是有穷非空集；E是是G的的边边集合，集合，是有穷集。是有穷集。6.1.1 6.1.1 图的结构定义图的结构定义图的结构定义图的结构定义:

3、6.1 图的基本术语图的基本术语【注意注意】顶点集顶点集V（G）不可不可为空集，边集为空集，边集E（G）可可以为空集。以为空集。若若E（G）为空集，则）为空集，则图图G只有顶点而没有边只有顶点而没有边，称为，称为零图零图。第4页，共113页，编辑于2022年，星期三 2.无向图（无向图（Undigraph）如果图中每条边都是顶点的无序对，即每条边在图如果图中每条边都是顶点的无序对，即每条边在图示时都没有箭头，则称此图为无向图。示时都没有箭头，则称此图为无向图。B CA D F E例如例如:G=(V,E)其中其中V=A,B,C,D,E,FE=(A,B),(A,E),(B,E),(C,D),(D,

4、F),(B,F),(C,F)第5页，共113页，编辑于2022年，星期三 3.3.有向图（有向图（DigraphDigraph）由于由于“弧弧”是有方向的，因此称由顶点集和弧集构成的是有方向的，因此称由顶点集和弧集构成的图为图为有向图有向图。EACBD例如例如:G=(V,E)其中其中V=A,B,C,D,EE=,第6页，共113页，编辑于2022年，星期三6.1.2 图的基本术语图的基本术语1.完全图（完全图（Completed Graph）【无向完全图无向完全图】:（1）若一个无向图有若一个无向图有 n个顶点，且每个顶点，且每一个顶点与其他一个顶点与其他 n-1 个顶点之间都有边，个顶点之间都

5、有边，这样的图称为这样的图称为无向完全图无向完全图。（2）对于一个具有对于一个具有n个顶点的无向个顶点的无向完全图，它共有完全图，它共有 条边。条边。n(n-1)/2第7页，共113页，编辑于2022年，星期三【有向完全图有向完全图】:（1）若一个有向图有）若一个有向图有n个顶点，且个顶点，且每一个顶点与其他每一个顶点与其他 n-1个顶点之间个顶点之间都有一条以该顶点为弧尾的弧，这都有一条以该顶点为弧尾的弧，这样的图称为样的图称为有向完全图有向完全图。（2）对于一个具有）对于一个具有n个顶点的有向个顶点的有向完全图，它共有完全图，它共有n（n-1）条弧。条弧。1.完全图（完全图（Complet

6、ed Graph）第8页，共113页，编辑于2022年，星期三2.子图（子图（Subgraph）子图子图：设有两个图设有两个图 G1(V1,E1)和和 G2(V2,E2)。若。若 V2 V1 且且 E2 E1,则称则称 图图G2 是是 图图G1 的子图。的子图。(a)图图1 (b)图图第10页，共113页，编辑于2022年，星期三2.子图（子图（Subgraph）第11页，共113页，编辑于2022年，星期三3.路径（路径（Path）路径上边的数目称为路径上边的数目称为路径长度路径长度。对于有向图，其路径也是有向的，路径由弧组成。对于有向图，其路径也是有向的，路径由弧组成。BACDFE从从A到

7、到D的路径可以为：的路径可以为：ABEBFCD、AEBFCD等等路径路径：在图在图在图在图GG(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 vi vi 出发出发出发出发,沿一些边经过沿一些边经过沿一些边经过沿一些边经过顶点顶点顶点顶点vp1,vpvp2,vpm，到达顶点，到达顶点vjvj。则称顶点序列。则称顶点序列。则称顶点序列。则称顶点序列(vi,vp1,1,vpvp2,vpm,vj vpm,vj)为从顶点为从顶点为从顶点为从顶点vi vi 到顶点到顶点到顶点到顶点 vj vj 的的的的路径路径路径路径。第12页，共113页，编辑于2022年，星期三4.简单路径简单路径 简单

8、路径简单路径：指一条路径上所有顶点（起始点和终止点除外）彼此指一条路径上所有顶点（起始点和终止点除外）彼此都是都是不同不同的的BACDFE从从A到到D的路径可以为：的路径可以为：ABEBFCD、AEBFCD等等其中其中ABEBFCD不是简单路径，不是简单路径，AEBFCD是简单路径是简单路径第13页，共113页，编辑于2022年，星期三5.回路（回路（Cycle）和简单回路）和简单回路 回路回路：指在一条路径中，如果其指在一条路径中，如果其起始点和终止点是同一起始点和终止点是同一顶点顶点 简单回路简单回路：简单路径相应的回路简单路径相应的回路BACDFE简单回路：简单回路：ABEA、CFDC等

9、等第14页，共113页，编辑于2022年，星期三v0,v1,v2,v0,v4是一条是一条路径路径，但不是简单路径，但不是简单路径 v0,v1,v2,v4是一条是一条简单路径简单路径,其长度为其长度为3v0,v1,v2,v4,v0是一条是一条回路回路【阅读阅读】第15页，共113页，编辑于2022年，星期三6.连通图（连通图（Connected Graph）和强连通图）和强连通图 在在无向图无向图G中，若从中，若从Vi 到到Vj有路径，则称有路径，则称Vi和和Vj是是连通的。连通的。BACDFE 若图若图G G中中任意两个顶点任意两个顶点之间都有之间都有路径相通路径相通，则称此则称此图为图为连通

10、图连通图;第16页，共113页，编辑于2022年，星期三 对于对于有向图有向图而言，若有向图而言，若有向图G中中每一对不同顶点每一对不同顶点Vi和和Vj之间之间有从有从Vi到到Vj和从和从Vj到到Vi的路径，则称的路径，则称G为为强连通强连通图图。6.连通图（连通图（Connected Graph）和强连通图）和强连通图ABECF第17页，共113页，编辑于2022年，星期三7.连通分量和强连通分量连通分量和强连通分量 若若无向图无向图为为非连通图非连通图，则图中各个极大连通子图，则图中各个极大连通子图称作此图的称作此图的连通分量连通分量。第18页，共113页，编辑于2022年，星期三7.连通

11、分量和强连通分量连通分量和强连通分量 若若有向图有向图为为非强连通图非强连通图，则图中各个极大强连，则图中各个极大强连通子图称作此图的通子图称作此图的强连通分量强连通分量。第19页，共113页，编辑于2022年，星期三8.邻接点（邻接点（Adjacent）和相关边）和相关边而边而边则是与顶点则是与顶点Vi和和Vj相关联的边。相关联的边。假若顶点假若顶点Vi 和顶点和顶点Vj 之间存在一条边，则称顶之间存在一条边，则称顶点点Vi和和Vj互为互为邻接点邻接点第20页，共113页，编辑于2022年，星期三 9.度、入度和出度度、入度和出度所谓所谓顶点的度顶点的度，就是指和该顶点，就是指和该顶点相关联

12、的边数相关联的边数。例如例如:顶点顶点B的度的度=3顶点顶点A的度的度=2ACDFEB右侧图中右侧图中第21页，共113页，编辑于2022年，星期三顶点的顶点的出度出度:以顶点以顶点v 为弧尾为弧尾的弧的数目的弧的数目;ABECF对有向图来说，对有向图来说，顶点的顶点的入度入度:以顶点以顶点v v为弧头为弧头的弧的数目的弧的数目。顶点的顶点的度度=出度出度+入度入度例如例如:顶点顶点B的入度的入度=2顶点顶点B的出度的出度=1顶点顶点B的度的度=3由于弧有方向性，则有入由于弧有方向性，则有入度和出度之分度和出度之分第22页，共113页，编辑于2022年，星期三10.权和网（权和网（Net）在一

13、个图中，每条边都可以标上具有某种含义的数在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的值，该数值称为该边的权权。边上带权的图边上带权的图称为称为带权图带权图，也称为，也称为网（有向网网（有向网和无向网）和无向网）。第23页，共113页，编辑于2022年，星期三 假设一个连通图有假设一个连通图有 n 个顶点和个顶点和 e 条边，其中条边，其中 n-1 条边和条边和 n 个顶点构成一个个顶点构成一个极小连通子图极小连通子图，称该极小连通子图为此，称该极小连通子图为此连通图的连通图的生成树生成树。对非连通图，则称由各对非连通图，则称由各个连通分量的生成树的个连通分量的生成树的集合为

14、此非连通图的集合为此非连通图的生生成森林成森林。BACDFE【补充生成树补充生成树】第24页，共113页，编辑于2022年，星期三第25页，共113页，编辑于2022年，星期三邻接矩阵邻接矩阵:表示结点间相邻关系的矩阵，用一个表示结点间相邻关系的矩阵，用一个二维数组二维数组来表来表示集合示集合V V。此二维数组称为。此二维数组称为邻接矩阵邻接矩阵。若若G G是一个具有是一个具有n n个结点的图，其邻接矩阵是一个个结点的图，其邻接矩阵是一个n n阶阶方阵方阵。6.2.1 邻接矩阵邻接矩阵第26页，共113页，编辑于2022年，星期三【无向图的邻接矩阵无向图的邻接矩阵】定义定义 设设G=(V,E)

15、是有是有n(n 1)个顶点的个顶点的无向图无向图，则，则G的邻接的邻接矩阵是一个矩阵是一个nn 矩阵矩阵:Ai,j=Aj,i=0 (vi,vj)E(G)1 (vi,vj)E(G)第27页，共113页，编辑于2022年，星期三 V1V2V4V3V50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0无向图的邻接矩阵为无向图的邻接矩阵为对称方阵对称方阵；邻接矩阵邻接矩阵第第i行（或第行（或第i列）的元素之和列）的元素之和则是顶点则是顶点Vi的的度度。【无向图的邻接矩阵无向图的邻接矩阵】(v1 v2 v3 v4 v5)v1V2V3V4v5第28页，共113页，编

16、辑于2022年，星期三定义定义 设设G=(V,E)是有是有n(n1)个顶点的有向图，个顶点的有向图，G的邻接矩的邻接矩阵是具有如下性质的阵是具有如下性质的nn方阵方阵:【有向图的邻接矩阵有向图的邻接矩阵】1 当当 E(G)0 当当 E(G)Ai,j=第29页，共113页，编辑于2022年，星期三有向图的邻接矩阵为有向图的邻接矩阵为非对称矩阵非对称矩阵；邻接矩阵邻接矩阵第第 i 行的元素之和行的元素之和为顶点为顶点Vi的的出度出度；邻接矩；邻接矩阵阵第第 j 列的元素之和列的元素之和为顶点为顶点Vj的的入度入度。V1V2V3V40 1 1 00 0 0 00 0 0 11 0 0 0【有向图的邻

17、接矩阵有向图的邻接矩阵】第30页，共113页，编辑于2022年，星期三【优点】：【优点】：借助于邻接矩阵，容易判定任意两个顶点之间是借助于邻接矩阵，容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。否有边（或弧）相连，并容易求得各个顶点的度。对于无向图，顶点对于无向图，顶点Vi 的度是邻接矩阵第的度是邻接矩阵第i 行（或第行（或第i列）列）的元素之和。的元素之和。对于有向图，第对于有向图，第i 行的元素之和为顶点行的元素之和为顶点Vi 的出度；第的出度；第j 列列的元素之和为顶点的元素之和为顶点Vj的入度。的入度。【缺点缺点】：占用的存储单元个数只与图中结点个数有关，而占用

18、的存储单元个数只与图中结点个数有关，而与边的数目无关。与边的数目无关。第31页，共113页，编辑于2022年，星期三【带权图（网）的邻接矩阵带权图（网）的邻接矩阵】Aij=Wi 对于无向图，对于无向图，(Vi，Vj)E(G)；对于无向图对于无向图,E(G)；Wi为权为权 其他其他 定义定义第32页，共113页，编辑于2022年，星期三对于有向图，顶点对于有向图，顶点Vi的度是邻接矩阵中的度是邻接矩阵中第第i行和第行和第i列的列的非零元素非零元素的个数的个数之和之和;顶点顶点Vi的的出度出度是邻接矩阵中是邻接矩阵中第第i行的非零元素的个数行的非零元素的个数;顶点顶点Vi的的入入度度是邻接矩阵中是

19、邻接矩阵中第第i列的非零元素的个数列的非零元素的个数。对于无向图，顶点对于无向图，顶点Vi的度是邻接矩阵中的度是邻接矩阵中第第i行（或第行（或第i列）的列）的非零元素非零元素的的个数个数。10 2 3 6 5 【带权图（网）的邻接矩阵带权图（网）的邻接矩阵】第33页，共113页，编辑于2022年，星期三6.2.2 邻接表邻接表邻接表是图的一种邻接表是图的一种顺序顺序和和链式链式分配相结合的存储分配相结合的存储结构。它包括两个部分结构。它包括两个部分:一部分是向量，另一部分是一部分是向量，另一部分是链表。链表。在邻接表中，为图中每个顶点建立一个单链表在邻接表中，为图中每个顶点建立一个单链表，第，

20、第i i 个单链表中的结点表示顶点个单链表中的结点表示顶点Vi Vi 的所有邻接顶点的所有邻接顶点（对有（对有向图是从向图是从vivi顶点出去的边）。顶点出去的边）。第34页，共113页，编辑于2022年，星期三 邻接表是图的一种链式存贮结构。在邻接表中，对图邻接表是图的一种链式存贮结构。在邻接表中，对图的每个顶点建立一个单链表，第的每个顶点建立一个单链表，第i 个单链表中的结点表个单链表中的结点表示顶点示顶点Vi 的所有邻接顶点。的所有邻接顶点。链表中每个结点由二个域组成：链表中每个结点由二个域组成：vextex nextvextex：顶点：顶点Vi的邻接点的邻接点next：指向：指向Vi下

21、一个邻接点的指针下一个邻接点的指针 第35页，共113页，编辑于2022年，星期三在每个链表上附设一个表头结点，由两个域组成：在每个链表上附设一个表头结点，由两个域组成：data fristarc data ：存贮与顶点存贮与顶点Vi有关信息的数据；有关信息的数据；fristarc：指向：指向Vi的第一个邻接点的指针。的第一个邻接点的指针。表头结点通常以顺序结构的形式存储，以便随机访问表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的邻接点链表。任一顶点的邻接点链表。第36页，共113页，编辑于2022年，星期三V1V2V3V4V531 424320 21 0 1 01234 在无向图的

22、邻接表中，在无向图的邻接表中，顶点顶点Vi的度恰为第的度恰为第 i 个链表中个链表中的结点数的结点数。V1V2V4V3V5【无向图的邻接表无向图的邻接表】第37页，共113页，编辑于2022年，星期三21 3 0 V1V2 V3V40123 有向图的邻接表中，有向图的邻接表中，第第i个链表中的结点个数是顶点个链表中的结点个数是顶点Vi的的出度出度。在有向图的邻接表中不易找到指向该顶点的弧。在有向图的邻接表中不易找到指向该顶点的弧。【有向图的邻接表有向图的邻接表】V1V2V3V4第38页，共113页，编辑于2022年，星期三V1V2V3V43 0 2 0 0123【有向图的逆邻接表有向图的逆邻接

23、表】V1V2V3V4 有向图的逆邻接表中，有向图的逆邻接表中，第第i个链表中的结点个数是顶个链表中的结点个数是顶点点Vi的入度的入度。在有向图的逆邻接表中，对每个顶点，链接的是指向在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。该顶点的弧。第39页，共113页，编辑于2022年，星期三【优点优点】：当边数当边数顶点个数的平方顶点个数的平方(mw1-w2-w8-w7-w3-w5-w6-w4 Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4【例例】-求广度优先遍历序列求广度优先遍历序列第60页，共113页，编辑于2022年，星期三广度优先搜索序列广度优先搜索序列BFS

24、BFS（结果不唯一）：（结果不唯一）：V1 V2 V3 V4 V5 V6 V7 V8V1V2V3V4V5V6V7V8【练习练习】-写出广度优先遍历序列写出广度优先遍历序列第61页，共113页，编辑于2022年，星期三由图中的全部顶点和广度优先搜索过程所经过的边集，由图中的全部顶点和广度优先搜索过程所经过的边集，即构成了图的广度优先生成树。即构成了图的广度优先生成树。【广度优先生成树（广度优先生成树（BFS生成树）生成树）】第62页，共113页，编辑于2022年，星期三【定义表结点和头结点的定义表结点和头结点的c语言描述语言描述】Typedef struct arcnode int vextex

25、;struct arcnode*next;ARCNODE;Typedef struct vexnode int data;ARCNODE*firstarc;VEXNODE;【广度优先搜索遍历算法广度优先搜索遍历算法】邻接表为存储结构邻接表为存储结构000021012332031012VEXNODE类型类型 ARCNODE类型类型 第63页，共113页，编辑于2022年，星期三000021012332031012【从从0出发广度优先搜索遍历示意图出发广度优先搜索遍历示意图】邻接表为存储结构邻接表为存储结构111101233121032021第64页，共113页，编辑于2022年，星期三00002

26、10123320310121p1p1pp1pppp=NULLp=NULLppp=NULLpp=NULL012312013032120rear2rear1rearfrontfrontfront3rearfrontfront第67页，共113页，编辑于2022年，星期三【练习练习】写出从顶点写出从顶点A出发按深度优先搜索和广度优先搜索出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。算法遍历得到的顶点序列。第68页，共113页，编辑于2022年，星期三【练习答案练习答案】-结果不唯一结果不唯一 写出从顶点写出从顶点A出发按深度优先搜索和广度优先搜索出发按深度优先搜索和广度优先搜索算法遍历得到

27、的顶点序列。算法遍历得到的顶点序列。广度优先遍历序列为广度优先遍历序列为ABDCEF深度优先遍历序列为深度优先遍历序列为ABCFED，第69页，共113页，编辑于2022年，星期三【练习练习】已知一个有向图的邻接表如图所示已知一个有向图的邻接表如图所示,求出从顶点求出从顶点1出出发根据深度优先搜索和广度优先搜索算法遍历得到的顶发根据深度优先搜索和广度优先搜索算法遍历得到的顶点序列。点序列。第70页，共113页，编辑于2022年，星期三【练习答案练习答案】结果唯一结果唯一 已知一个有向图的邻接表如图所示已知一个有向图的邻接表如图所示,求出从顶点求出从顶点1出出发根据深度优先搜索和广度优先搜索算法

28、遍历得到的发根据深度优先搜索和广度优先搜索算法遍历得到的顶点序列。顶点序列。深度优先遍历序列为深度优先遍历序列为13452，广度优先遍历序列为广度优先遍历序列为13254 第71页，共113页，编辑于2022年，星期三 假设要在假设要在 n 个城市之间建立通讯联络网，则个城市之间建立通讯联络网，则连通连通 n 个城市只需要修建个城市只需要修建 n-1条线路，条线路，如何在最如何在最节省经费的前提下建立节省经费的前提下建立这个这个通讯网通讯网？问题：问题：6.4(连通网的连通网的)最小生成树最小生成树 图的生成树不唯一，从不同结点出发进行搜索，或图的生成树不唯一，从不同结点出发进行搜索，或者按照

29、不同的搜索次序进行搜索，都可以得到不同的生者按照不同的搜索次序进行搜索，都可以得到不同的生成树。成树。第72页，共113页，编辑于2022年，星期三 可以用连通网来表示可以用连通网来表示n个城市以及个城市以及n个城市之间可能设个城市之间可能设置的通信线路。置的通信线路。1245631234555666 对于对于n个顶点的连通网可以建立许多不同的生成树，每个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通讯网。现在，我们要选择这样一棵生成树都可以是一个通讯网。现在，我们要选择这样一棵生成树，也就是总的耗费最少。一棵生成树，也就是总的耗费最少。网的顶点网的顶点城市城市 边边两城市之

30、间的线路两城市之间的线路 边的权值边的权值相应的代价相应的代价第73页，共113页，编辑于2022年，星期三 构造网的一棵最小生成树，即：构造网的一棵最小生成树，即：在在 e 条带权的边中条带权的边中选取选取 n-1 条边（不构成回路），使条边（不构成回路），使“权值之和权值之和”为最小为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）第74页，共113页，编辑于2022年，星期三 取图中任意一个顶点取图中任意一个顶点 v 作为生成树的根，之后往生成树作为生成树的根，之后往生成树上添加新的顶点上添加新的顶点 w。

31、在添加的顶点在添加的顶点 w 和已经在生成树上的顶和已经在生成树上的顶点点v 之间必定存在一条边，并且该边的权值在所有连通顶点之间必定存在一条边，并且该边的权值在所有连通顶点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直。之后继续往生成树上添加顶点，直至生成树上含有至生成树上含有 n-1 个顶点为止。个顶点为止。（1）普里姆算法的基本思想）普里姆算法的基本思想:第75页，共113页，编辑于2022年，星期三abcdegf195141827168213127【例如例如】aedcbgf148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+

32、21=67第76页，共113页，编辑于2022年，星期三【练习练习】请用请用Prim算法构造以下网络的最小生成树。算法构造以下网络的最小生成树。第77页，共113页，编辑于2022年，星期三V0V1V2V5V3V41234532345V0V1V3V5V4V221332【练习答案练习答案】-Prim算法算法V0V1V3V5V4V221332第78页，共113页，编辑于2022年，星期三具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然，然后从权值最小的边开始，若它的添加不使后从权值最小的边开始，若它的添加不使SG 中产生中产生回路，则在回路，则在 SG 上加上

33、这条边，如此重复，直至加上上加上这条边，如此重复，直至加上 n-1 条边为止。条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上为使生成树上边的权值之和达到边的权值之和达到最小最小，则应使生成树中每一条边的权值尽可能地小。，则应使生成树中每一条边的权值尽可能地小。（2）克鲁斯卡尔算法的基本思想：）克鲁斯卡尔算法的基本思想：第79页，共113页，编辑于2022年，星期三abcdegf195141827168213127aedcbgf148531621【例如例如】7121819第80页，共113页，编辑于2022年，星期三【练习练习】请用请用Kruskal算法构造以下网络的最小生成树。算法构

34、造以下网络的最小生成树。第81页，共113页，编辑于2022年，星期三【练习答案练习答案】-Kruskal算法算法V0V1V2V5V3V41234532345V3V0V1V5V4V23122334455V3V0V1V5V4V212233第82页，共113页，编辑于2022年，星期三第83页，共113页，编辑于2022年，星期三 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本的算法的基本思想思想:依依最短路径的长度最短路径的长度递增递增的次序求得各条路径的次序求得各条路径源点源点v1v2【迪杰斯特拉算法迪杰斯特拉算法】v1v46.5 最短路径最短路径第85页，共113页，编

35、辑于2022年，星期三【示例示例】给定带权有向图给定带权有向图给定带权有向图给定带权有向图G和源点和源点和源点和源点0,0,利用迪杰斯特拉利用迪杰斯特拉（DijkstraDijkstra）算法求从）算法求从）算法求从）算法求从0 0到其余各顶点的最短路径。到其余各顶点的最短路径。到其余各顶点的最短路径。到其余各顶点的最短路径。41032532581241030第86页，共113页，编辑于2022年，星期三【示例答案示例答案】最短路径的求解最短路径的求解过程程因此，最后因此，最后输出出结果果为：1-0:3 3-1-0:112-3-1-0:154-3-1-0:23循环 选择vdist0 dist1

36、 dist2 dist3 dist4初始123400,1 0,1,30,1,3,20,1,3,2,4 0 3 30 0 3 28 11 30 0 3 15 11 23 0 3 15 11 23 0 3 15 11 23 41032532581241030第87页，共113页，编辑于2022年，星期三6.5 最短路径最短路径第88页，共113页，编辑于2022年，星期三6.5 最短路径最短路径终点从V0到各终点的dist 值和最短路径V0Dist 0 V1Dist 1 505045V2Dist 2 10V3Dist 3 25V4Dist 4 45454545V5Dist 5 WW=V2W=V3W

37、=V1W=V4第89页，共113页，编辑于2022年，星期三【练习练习】给定带权有向图给定带权有向图G和源点和源点v0,利用迪杰斯特拉利用迪杰斯特拉（Dijkstra）算法求从）算法求从v0到其余各顶点的最短路径。到其余各顶点的最短路径。第90页，共113页，编辑于2022年，星期三【练习答案答案】最短路径的求解最短路径的求解过程程因此，最后因此，最后输出出结果果为：v2-v0:9 v1-v0:16v3-v1-v0:19v4-v2-v0:21v5-v3-v1-v0:24循环 选择vdist0.dist5初始1234500,20,2,10,2,1,30,2,1,3,4 0,2,1,3,4,5 0

38、 16 9 0 16 9 21 0 16 9 19 21 0 16 9 19 21 240 16 9 19 21 240 16 9 19 21 24第91页，共113页，编辑于2022年，星期三6.6 拓扑排序拓扑排序 AOV网网 拓扑排序拓扑排序 关键路径关键路径 AOE网网第96页，共113页，编辑于2022年，星期三6.6 拓扑排序拓扑排序 网中的顶点表示网中的顶点表示各门课程的教学活动，各门课程的教学活动，有向边表示各门课程有向边表示各门课程的制约关系。的制约关系。课程代号课程代号 课程名称课程名称 先修课程先修课程 0 高等数学高等数学 无无 1 程序设计基础程序设计基础 无无 2

39、C程序设计程序设计 0，1 3 离散数学离散数学 0 4 数据结构数据结构 1，2，3 5 编译方法编译方法 3，4 6 操作系统操作系统 40123456第97页，共113页，编辑于2022年，星期三6.6.1 AOV网网 在有向图中若以顶点表示活动，用有向边表示活动在有向图中若以顶点表示活动，用有向边表示活动之间的优先关系，则这样的有向图称为以顶点表示活动之间的优先关系，则这样的有向图称为以顶点表示活动的网（的网（Activity On Vertex Network），简称），简称AOV网网。6.6 拓扑排序拓扑排序应用：应用：工程流程、生产过程中各道工序的流程、工程流程、生产过程中各道工

40、序的流程、程序流程、课程的流程程序流程、课程的流程第98页，共113页，编辑于2022年，星期三 例如例如:某工程可分为某工程可分为V0V0、V1V1、V2V2、V3V3、V4V4、V5V5、V6,7V6,7个子工个子工程，工程流程可用如下程，工程流程可用如下AOVAOV网表示。其中网表示。其中顶点：表示子工程（也顶点：表示子工程（也称活动），有向边：表示子工程间的顺序关系。称活动），有向边：表示子工程间的顺序关系。V5V5 V3V3 V2V2 V0V0 V1V1 V4V4 V6V66.6.1 AOV网网第99页，共113页，编辑于2022年，星期三 假设下图表示一个工程的施工图，判断该工程是

41、否合假设下图表示一个工程的施工图，判断该工程是否合理？理？V0V0 V1V1 V5V5 V2V2 V4V4 V3V3 V0V0 V1V16.6 拓扑排序拓扑排序 对工程，人们关心的问题：对工程，人们关心的问题：工程能否顺序进行，即工程流程是否工程能否顺序进行，即工程流程是否“合理合理”？能否给出一个活动之间的优先关系的有序序列？能否给出一个活动之间的优先关系的有序序列？第100页，共113页，编辑于2022年，星期三 拓扑排序拓扑排序拓扑排序拓扑排序：构造拓扑有序序列的过程。构造拓扑有序序列的过程。构造拓扑有序序列的过程。构造拓扑有序序列的过程。一个一个AOV网的拓扑有序序列并不是惟一的。网的

42、拓扑有序序列并不是惟一的。6.6.2 拓扑排序拓扑排序何谓何谓“拓扑有序序列拓扑有序序列”？它是由它是由它是由它是由AOV网中的所有顶点构成的一个线性序列，网中的所有顶点构成的一个线性序列，网中的所有顶点构成的一个线性序列，网中的所有顶点构成的一个线性序列，在在在在这个序列中体现了所有顶点间的优先关系这个序列中体现了所有顶点间的优先关系这个序列中体现了所有顶点间的优先关系这个序列中体现了所有顶点间的优先关系。对于某个对于某个AOV网，网，如果它的拓扑有序序列被构造成如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次

43、序进行安排。扑有序序列的次序进行安排。V0V0 V1V1 V5V5 V2V2 V4V4 V3V3 V0V0 V1V1第101页，共113页，编辑于2022年，星期三【例如例如】：对于下列有向图：对于下列有向图BDAC可求得可求得拓扑有序序列拓扑有序序列：A B C D 或或 A C B DBDAC不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B,C,DB,C,D6.6.2 拓扑排序拓扑排序第102页，共113页，编辑于2022年，星期三如何进行拓扑排序？如何进行拓扑排序？1）从有向图中选取一个没有前驱的顶点，并输出之）从有向图中选取一个没有前驱的

44、顶点，并输出之;重复上述两步，直至图空，或者图不空但找不到无前重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止驱的顶点为止。2）从有向图中删去此顶点以及所有以它为尾的弧）从有向图中删去此顶点以及所有以它为尾的弧;【注意注意】这样操作后的结果有两种这样操作后的结果有两种:一种是网中全部顶点均被输出，说明网中不存在有向回路一种是网中全部顶点均被输出，说明网中不存在有向回路;另一种是网中顶点未被全部输出，剩余的顶点均有前驱顶点，另一种是网中顶点未被全部输出，剩余的顶点均有前驱顶点，说明网中存在有向回路说明网中存在有向回路。拓扑排序的步骤拓扑排序的步骤6.6.2 拓扑排序拓扑排序 V0V0V

45、5V2V0 V1V1V1V3V4第103页，共113页，编辑于2022年，星期三abcghdfeabhcdgfe【实例实例】写出下图的拓扑排序序列写出下图的拓扑排序序列序列序列:第104页，共113页，编辑于2022年，星期三【练习练习】写出表示课程以及课写出表示课程以及课程的制约关系的程的制约关系的AOV网网的一个拓扑有序序列。的一个拓扑有序序列。课程代号课程代号 课程名称课程名称 先修课程先修课程 0 高等数学高等数学 无无 1 程序设计基础程序设计基础 无无 2 C程序设计程序设计 0，1 3 离散数学离散数学 0 4 数据结构数据结构 1，2，3 5 编译方法编译方法 3，4 6 操作

46、系统操作系统 40123456第105页，共113页，编辑于2022年，星期三【练习练习】写出下图所示网所有可能的拓扑有序序列。写出下图所示网所有可能的拓扑有序序列。第106页，共113页，编辑于2022年，星期三【练习答案练习答案】写出下图所示网所有可能的拓扑有序序列。写出下图所示网所有可能的拓扑有序序列。可能的拓扑有序序列有：可能的拓扑有序序列有：v1，v2，v3，v4，v5，v6;v1，v2，v3，v5，v4，v6;v1，v2，v4，v3，v5，v6;v2，v1，v4，v3，v5，v6;v2，v1，v3，v4，v5，v6;v2，v1，v3，v5，v4，v6;v2，v4，v1，v3，v5，

47、v6;第107页，共113页，编辑于2022年，星期三 对工程人们关心两类问题：对工程人们关心两类问题：1 1）工程能否顺序进行，即工程流程是否）工程能否顺序进行，即工程流程是否“合理合理”2 2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键？的关键？V3V3V1V1V4V4V6V6V5V5V2V2a a4=34=3a a1=31=3a a2=22=2a a6=36=3a a5=45=4a a3=23=2a a7=27=2a a8=18=1顶点表示事件边表示活动事件Vj发生表示 ak已结束ak VjVi事件Vi发生表示 a

48、k可以开始 AOE网网6.7 关键路径关键路径第108页，共113页，编辑于2022年，星期三 整个工程完成的时间为整个工程完成的时间为：从有向图的从有向图的源点源点到到汇点汇点的最长路径。的最长路径。abcdefghk64521187244例如例如:“关键活动关键活动”指的是指的是：该弧上的：该弧上的权值增加权值增加 将使有向图将使有向图上的上的最长路径的长度增加。最长路径的长度增加。源点汇点6174第109页，共113页，编辑于2022年，星期三1.1.图（图（GraphGraph）是一种）是一种非线性数据结构非线性数据结构，图中的每个元素既，图中的每个元素既可有可有多个直接前驱，也可有多

49、个直接后继多个直接前驱，也可有多个直接后继。图分为。图分为有向图和无向有向图和无向图图，有向图中的边（又称弧）是顶点的有序对，无向图中的边是顶，有向图中的边（又称弧）是顶点的有序对，无向图中的边是顶点的无序对。点的无序对。2.2.图的存储结构常用的有图的存储结构常用的有邻接矩阵、邻接表和边集数组邻接矩阵、邻接表和边集数组三种。图的三种。图的邻邻接矩阵具有惟一性接矩阵具有惟一性，而，而邻接表和边集数组不具有惟一性邻接表和边集数组不具有惟一性。3.3.若要系统地访问图中的每个顶点，可以采用若要系统地访问图中的每个顶点，可以采用深度优先搜索深度优先搜索（DFSDFS）和广度优先搜索（）和广度优先搜索

50、（BFSBFS）遍历算法）遍历算法，遍历后可以得到深，遍历后可以得到深度优先搜索序列、深度优先生成树和广度优先搜索序列、广度度优先搜索序列、深度优先生成树和广度优先搜索序列、广度优先生成树。优先生成树。本章小结本章小结本章小结本章小结第112页，共113页，编辑于2022年，星期三4.4.对于图的应用有求对于图的应用有求最小生成树最小生成树问题、问题、最短路径最短路径问题和问题和拓扑排序拓扑排序问题。求图的最小生成树可以采用问题。求图的最小生成树可以采用普里姆算法（普里姆算法（PrimPrim）和克鲁斯卡）和克鲁斯卡尔算法（尔算法（KruskalKruskal）;求最短路径既可用求最短路径既可