1、第第7 7章章 图图q 理解图的基本概念及有关术语，掌握图的两种存储结构理解图的基本概念及有关术语，掌握图的两种存储结构(邻接矩阵和邻接表邻接矩阵和邻接表)的表示方法；的表示方法；q 熟练掌握图的两种遍历熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜深度优先搜索遍历和广度优先搜索遍历索遍历)的算法思想、设计步骤，并能列出按上述两种遍历的算法思想、设计步骤，并能列出按上述两种遍历算法得到的序列；算法得到的序列；q 理解最小生成树的概念，能按理解最小生成树的概念，能按Prim构造最小生成树；构造最小生成树；q 领会求最短路径、拓扑排序以及关键路径的算法思想。领会求最短路径、拓扑排序以及关键路径
2、的算法思想。学习要点学习要点7.1 图的基本概念图的基本概念 图是由图是由一个一个顶点集顶点集 V和和一个描述顶点之间关系一个描述顶点之间关系（边或者弧）的集合（边或者弧）的集合R构成的数据结构。构成的数据结构。Graph=(V,VR)其中，其中，VR|v,wV 且且 P(v,w)表示从表示从 v 到到 w 的一条弧，并称的一条弧，并称 v 为为弧尾弧尾或或初始点，初始点，w 为为弧头弧头或终端点。或终端点。谓词谓词 P(v,w)定义了弧定义了弧 的意义或信息。的意义或信息。v 图的定义图的定义&图的应用举例图的应用举例例例1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点 边：
3、连接地点的公路边：连接地点的公路例例2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 V0V0V4V4 V3V3V1V1V2V2 V0V0V2V2 V3V3V1V17.1.2 图的术语图的术语 V0V0V4V4 V3V3V1V1V2V2 V0V0V2V2 V3V3V1V1&有向图和无向图有向图和无向图&顶点、边、弧、弧头、弧尾顶点、边、弧、弧头、弧尾V VW WV VW W3 31 12 23 31 12 2&完全图、
4、稠密图、稀疏图完全图、稠密图、稀疏图7 71 12 26 65 54 43 35 52 23 36 64 41 1&度、入度、出度度、入度、出度&边的权、网边的权、网 1 12 25 54 43 3176324 58B BC CA A21435&路径、路径长度路径、路径长度 V0V0V4V4 V3V3V1V1V2V2V0V0V1V1&回路、简单路径、简单回路回路、简单路径、简单回路 V0V0V4V4 V3V3V1V1V2V2 V0V0V2V2 V3V3V1V1&子图子图 V0V0V4V4 V3V3V1V1V2V2 V0V0V4V4 V3V3V1V1V2V2 V0V0 V3V3V1V1&连通图、
5、连通分量连通图、连通分量 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4&强连通图、强连通分量强连通图、强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V1V1 V2V2 V3V3 V1V1 V0V0 V2V2 V3V3&生成树、生成森林生成树、生成森林 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2图是一种结构复杂的数据结构，表现在不仅各个顶图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间
6、的逻辑关系也错点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，综复杂。从图的定义可知，一个图的信息包括两部分，即即图中顶点的信息图中顶点的信息以及以及描述顶点之间的关系（边或者描述顶点之间的关系（边或者弧）的信息弧）的信息。因此无论采用什么方法建立图的存储结。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。构，都要完整、准确地反映这两方面的信息。图通常有图通常有邻接矩阵、邻接表、邻接多重表和十字链邻接矩阵、邻接表、邻接多重表和十字链表表等表示方法。等表示方法。7.2 图的存储结构图的存储结构 7.2.1 邻接矩阵邻接矩阵
7、定义定义：在邻接矩阵表示中，除了用一维数组存放：在邻接矩阵表示中，除了用一维数组存放顶点本身信息外，还用一个矩阵表示各个顶点之间顶点本身信息外，还用一个矩阵表示各个顶点之间的邻接关系。这个矩阵称为的邻接关系。这个矩阵称为邻接矩阵邻接矩阵。假设图假设图G(V,E)有有n个确定的顶点，即个确定的顶点，即Vv0,v1,vn-1，则表示，则表示G中各顶点相邻关系为一个中各顶点相邻关系为一个nn的矩阵，矩阵的元素为的矩阵，矩阵的元素为：Aij=1 若若(vi,vj)或或是是E(G)中的边中的边 0 若若(vi,vj)或或不是不是E(G)中的边中的边 V0V1V2V3 0 01 11 10 00 00 0
8、0 00 00 00 00 01 11 10 00 00 0A=例例 V0V4V3V1V20 01 10 01 10 01 10 01 10 01 10 01 10 01 11 11 10 01 10 00 00 01 11 10 00 0B=&邻接矩阵邻接矩阵 V0V2V1V3V485679343 36 65 53 34 4 6 64 48 89 95 58 87 7 9 97 7C=&邻接矩阵邻接矩阵 从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：矩阵是对称的；矩阵是对称的；第第i行或第行或第i 列列1的个数为顶点的个数为顶点i 的度；的度；矩阵中矩阵中1的个数的
9、一半为图中边的数目；的个数的一半为图中边的数目；很容易判断顶点很容易判断顶点i和顶点和顶点j之间是否有边相连之间是否有边相连(看看矩阵中矩阵中i行行j列值是否为列值是否为1)。&邻接矩阵邻接矩阵 从有向图的邻接矩阵可以得出如下结论：从有向图的邻接矩阵可以得出如下结论：矩阵不一定是对称的；矩阵不一定是对称的；第第i 行中行中1的个数为顶点的个数为顶点i 的出度；的出度；第第i列中列中1的个数为顶点的个数为顶点 i的入度；的入度；矩阵中矩阵中1的个数为图中弧的数目；的个数为图中弧的数目；很容易判断顶点很容易判断顶点i和顶点和顶点j是否有弧相连。是否有弧相连。&邻接矩阵邻接矩阵 图的邻接矩阵数据类型
10、描述：图的邻接矩阵数据类型描述：在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组来存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下：#define INFINITY 1000#define MAX_VERTEX_NUM 20&邻接矩阵邻接矩阵 7.2.2 邻接表邻接表 邻接表是图的一种顺序存储与链式存储结合的存邻接表是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图就是对于图G中的每个顶点中的每个顶点vi，将所有邻接于，将所有邻接于vi的顶点链成
11、一个单链表，这个单链表就称为顶点的顶点链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有的邻接表表头放到数组中，就的邻接表，再将所有的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为顶点结点。结点，每个单链表设的一个头结点称为顶点结点。对图中每个顶点对图中每个顶点Vi建立一个单链表，链表中的结点表建立一个单链表，链表中的结点表示依附于顶点示依附于顶点Vi的边，每个链表结点为两个域：的边，每个链表结点为两个域：每个链表附设一个头结点，头结点结构为：每个链表附设一个头结点，头结点结构为：其中：
12、顶点域其中：顶点域data存放顶点信息存放顶点信息；表头指针表头指针firstarc指向链表的第一个结点。指向链表的第一个结点。顶点域顶点域表头指针表头指针datafirstarc邻接点域邻接点域指针域指针域adjvexnextarc&无向图的邻接表无向图的邻接表顶点顶点：通常按编号顺序将顶点数据存储在一维数组中；：通常按编号顺序将顶点数据存储在一维数组中；与同一顶点关联的边与同一顶点关联的边：用线性链表存储：用线性链表存储特点特点：设无向图中顶点数为：设无向图中顶点数为n，边数为，边数为e，则它的邻接表需要则它的邻接表需要n个头结点和个头结点和2e个表结点。个表结点。顶点顶点Vi的度的度 T
13、D(Vi)=链表链表i中的表结点数。中的表结点数。V0V4V3V1V20V01V12V23V34V42 21 13 34 42 22 21 11 10 00 03 34 4下标下标 编号编号 linklink返回用链表存储用链表存储同一顶点为同一顶点为起点起点的弧的弧&有向图邻接表有向图邻接表 V0 V1 V2 V30V01V1 2V23V31 12 23 30 0用链表存储用链表存储同一顶点为同一顶点为起点起点的弧的弧&有向图的逆邻接表有向图的逆邻接表 V0 V1 V2 V30V01V1 2V23V33 30 00 02 2&结论结论&结论结论7.2.3 十字链表十字链表 十字链表是将十字链
14、表是将有向图有向图的邻接表和逆邻接表结合起的邻接表和逆邻接表结合起来的一种有向图来的一种有向图链式链式存储结构。存储结构。结点结构结点结构 有向图的每一条弧有一个弧结点，每一个顶点必有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点，其结构为：有一个顶点结点，其结构为：弧结点弧结点顶点结点顶点结点tailvexheadvexinfohlinktlinkdatafirstinfirstout建立有向图的十字链表：建立有向图的十字链表：7.2.4 邻接多重表邻接多重表 邻接多重表是无向图的另一种链式存储结构。邻接多重表是无向图的另一种链式存储结构。每一个顶点有一个顶点结点，顶点结点结构为：每
15、一个顶点有一个顶点结点，顶点结点结构为：图的每一条边有一个边结点，边结点的结构为：图的每一条边有一个边结点，边结点的结构为：datafirstedgeivex ilink jvex jlinkmark图的邻接多重表数据类型描述：图的邻接多重表数据类型描述：#define MAX_VERTEX_NUM 20typedef emnu unvisited,visited VisitIf;typedef struct EBoxVisitIf mark;int ivex,jvex;struct EBox ilink,jlink;EBox;typedef struct VexBoxVertexType d
16、ata;EBox fistedge;VexBox;typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;7.3 图的遍历图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。沿着某条搜索路径对图中所有顶点各作一次访问。图访问的四个难点：图访问的四个难点：首结点首结点、非连通图、非连通图、回路、多个相连顶点、回路、多个相连顶点我们可以设置一个全局型标志数组我们可以设置一个全局型标志数组visited来标志来标志某个顶点
17、是否被访过，未访问的值为某个顶点是否被访过，未访问的值为0，访问过的，访问过的值为值为1。根据搜索路径的方向不同，图的遍历有两种方法：根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索和广度优先搜索。深度优先搜索和广度优先搜索。深度优先搜索遍历类似于树的先序遍历。假定给定图深度优先搜索遍历类似于树的先序遍历。假定给定图G的的初态是所有顶点均未被访问过，在初态是所有顶点均未被访问过，在G中任选一个顶点中任选一个顶点v作为遍作为遍历的初始点，则深度优先搜索遍历可定义如下：历的初始点，则深度优先搜索遍历可定义如下：7.3.1 深度优先搜索深度优先搜索1)首先访问顶点首先访问顶点v，并将其访问标
18、记置为访问过，即，并将其访问标记置为访问过，即visitedv=TRUE；2)然后搜索与顶点然后搜索与顶点v有边相连的下一个顶点有边相连的下一个顶点w，若，若w未被访问未被访问过，则访问它，并将过，则访问它，并将w的访问标记置为访问过，然后从的访问标记置为访问过，然后从w开始重复此过程；若开始重复此过程；若w已访问，再访问与已访问，再访问与v有边相连的其有边相连的其它顶点；它顶点；3)若与若与v有边相连的顶点都被访问过，则退回到前一个访问有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完止。顶点并重复刚才过程，直到图中所有顶点都被访问完止。4)深度优先搜
19、索是一种递归的过程深度优先搜索是一种递归的过程从图中某顶点从图中某顶点v出发：出发：V0 V7 V6 V5 V4 V3 V2 V11)访问顶点访问顶点v；2)依次从依次从v的未被访问的邻接点的未被访问的邻接点出发，对图进行深度优先遍历；出发，对图进行深度优先遍历；先序遍历（先序遍历（DLR）若二叉树非空若二叉树非空1)访问根结点；访问根结点；2)先序遍历左子树；先序遍历左子树；3)先序遍历右子树；先序遍历右子树；深度优先遍历深度优先遍历如果将图顶点的邻接点看如果将图顶点的邻接点看作二叉树结点的左、右孩作二叉树结点的左、右孩子深度优先遍历与先序遍子深度优先遍历与先序遍历是不是很类似？历是不是很类
20、似？深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V5 V5 V6 V6 V3 V3 V7V7深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V3 V3 V6 V6 V7 V7 V5V5V6V1V2V4V5V3V7V8V1V2V4 V5V3V7V6V8由于没有规定访问邻接由于没有规定访问邻接点的顺序点的顺序,深度优先序深度优先序列不是唯一的列不是唯一的对某顶点的深度优先遍历的递归算法：对某顶点的深度优先遍历的递归算法：Boolean visitedMAX;void DFSTraverse(Graph G,int v)for(v=0;vG.vexnum;+v
21、)visitedv=FALSE;for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);以以v为起点对为起点对G进行进行DFS搜索搜索/访问顶点访问顶点v/对对v的尚未访问过的邻的尚未访问过的邻 接点接点w递归调用递归调用DFS在遍历时，对图中每个顶点至多调用一次在遍历时，对图中每个顶点至多调用一次DFS 函函数，因为一旦某个顶点被标志成已被访问，就不再数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则对每个顶点查找其邻
22、接点的过程。其耗费的时间则取决于所采用的存储结构。取决于所采用的存储结构。深度优先搜索的算法复杂度：深度优先搜索的算法复杂度：广度优先搜索遍历类似于树的按层次遍历。设图广度优先搜索遍历类似于树的按层次遍历。设图G的初的初态是所有顶点均未访问，在态是所有顶点均未访问，在G 中任选一顶点中任选一顶点v作为初始点，作为初始点，则广度优先搜索的基本思想是：则广度优先搜索的基本思想是：1)首先访问顶点首先访问顶点v，并将其访问标志置为已被访问，即，并将其访问标志置为已被访问，即visitedv=TRUE；2)接着依次访问与顶点接着依次访问与顶点v有边相连的所有顶点有边相连的所有顶点W1，W2，Wt；3)
23、然后再按顺序访问与然后再按顺序访问与W1，W2，Wt有边相连又未曾有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问访问过的顶点；依此类推，直到图中所有顶点都被访问完为止完为止。7.3.2 广度优先搜索广度优先搜索即广度优先搜索遍历图的过程中以即广度优先搜索遍历图的过程中以v为起始点，由近至远，为起始点，由近至远，依次访问和依次访问和v有路径相通且路径长度为有路径相通且路径长度为1，2，的顶点。的顶点。V6V6V1V1V2V2V4V4V5V5V3V3V7V7V8V8 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2
24、 V7V7 V6V6 V5V5 V4V4在遍历过程中在遍历过程中所经过的路径所经过的路径求图求图G 的以的以V0起点的的广度优先序列：起点的的广度优先序列：V0,V1,V2,V3,V4,V5,V6,V7由于没有规定访问邻由于没有规定访问邻接点的顺序接点的顺序,广度优先广度优先序列不是唯一的序列不是唯一的从图中某顶点从图中某顶点v v出发：出发：1)1)访问顶点访问顶点v v；(容易实现容易实现)2)2)访问访问v v的所有未被访问的邻接点的所有未被访问的邻接点w w1 1,w,w2 2,w wk k；(容易实现容易实现)3)3)依次从这些邻接点依次从这些邻接点(在步骤在步骤2 2）访问的顶点）
25、访问的顶点)出发，访问它们出发，访问它们的所有未被访问的邻接点的所有未被访问的邻接点;依此类推，直到图中所有访问过依此类推，直到图中所有访问过的顶点的邻接点都被访问；的顶点的邻接点都被访问；为实现为实现 3)3)，需要保存在步骤，需要保存在步骤2 2）中访问的顶点，而且访问这）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。V0 V7 V6 V5 V4 V3 V2 V1广度优先遍历算法（类似于树的按层遍历）广度优先遍历算法（类似于树的按层遍历）在广度优先遍历算法中，需设置在广度优先遍历算法中，需设置一队列一队列
26、Q Q，保存已访问的顶点，保存已访问的顶点，并控制遍历顶点的顺序。并控制遍历顶点的顺序。7.4 最小生成树最小生成树1、问题提出、问题提出 要在要在n个城市间建立通信联络网个城市间建立通信联络网顶点顶点 表示城市表示城市权权 城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小（即建立该通信网所需花费的总代价）最小最小代价生成树最小代价生成树1654327131791812752410最小生成树最小生成树16543271317918127524102、问题分析、问
27、题分析 n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路；条线路；n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路；条线路；问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1条，条，能把能把 所有城市（顶点）均连起来，且总耗费（各边所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。权值之和）最小。3、定义、定义 对于带权的连通图对于带权的连通图G，其生成树也是带权的。我，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为且将权最小的生成树称为最小生成树最
28、小生成树。Prim方法构造过程方法构造过程V1V6V5V4V3V26513566425V1V31V1V6V314V1V6V4V3142V1V1V6V4V3V21425V1V6V5V4V3V214253 Prim算法可用下述过程描述：算法可用下述过程描述：（1）Uu1，T=；（2）while（UV）do （u，v）minwuv；uU，vVU TT（u，v）UUv （3）结束。）结束。普里姆普里姆(Prim)算算法法辅助数组各分量值的变化：辅助数组各分量值的变化：有关数据的存储结构有关数据的存储结构设置一个辅助数组设置一个辅助数组closedge,它包括两个域：它包括两个域：lowcost用来保存
29、集合用来保存集合V-U中中各顶点与集合各顶点与集合U中各顶点构成的中各顶点构成的边中具有最小权值的边的权值；边中具有最小权值的边的权值；adjvex用来保存依附于该边用来保存依附于该边的在集合的在集合U中的顶点。中的顶点。V1V6V5V4V3V26513566425 普里姆普里姆(Prim)算算法法void Prim(Mgraph G,VertexType u)k=LocateVex(G,u);for(j=0;kG.vexnum;+j)if(j!=k)closedgej=u,G.arcskj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(c
30、losedge);printf(closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=0;jG.vexnum;+j)if(G.arcskjcolsedgej.lowcost)closedgej=G.vexsk,G.arcskj;辅助数组初始化辅助数组初始化初始初始U=u寻找当前最小权值寻找当前最小权值第第k个顶点归并到集合个顶点归并到集合U新顶点并入新顶点并入U后重新选择后重新选择最小边最小边克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法 初始条件：初始条件：假设假设G=(V,E)是一个具有是一个具有n个顶点的连个顶点的连通网络，通网络，G=(
31、U,T)是是G 的最小生成树，的最小生成树，U的初值等于的初值等于V，即包含有即包含有G中的全部顶点，中的全部顶点，T的初值为空集。的初值为空集。基本思想：基本思想：将图将图G中的边按权值从小到大的顺序依次中的边按权值从小到大的顺序依次选取，若选取的边使生成树选取，若选取的边使生成树G不形成环路，则把它并不形成环路，则把它并入入T中，保留作为生成树中，保留作为生成树G的一条边，若选取的边使生的一条边，若选取的边使生成树成树G形成环路，则将其舍弃，如此进行下去，直到形成环路，则将其舍弃，如此进行下去，直到T中包含中包含n-1条边为止。此时的条边为止。此时的T即为最小生成树。即为最小生成树。165
32、4326513566425问题提出问题提出 用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中：顶点顶点表示城市表示城市 边边表示城市间的交通联系表示城市间的交通联系 权权表示此线路的长度表示此线路的长度 问题：如何找到城市问题：如何找到城市A到城市到城市B之间一条距离最近之间一条距离最近的通路？的通路？数学模型：从某顶点出发，沿图的边到达另一顶数学模型：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路点所经过的路径中，各边上权值之和最小的一条路径径最短路径最短路径7.5 最短路径最短路径51643208562301371732913长度
33、长度最短路径最短路径8131921207.5.2 单源点最短路单源点最短路径径依最短路径的长度递增的次序求得各条路径依最短路径的长度递增的次序求得各条路径其中，从源点到顶点其中，从源点到顶点v的最短路径是所有最短的最短路径是所有最短路径中长度最短者。路径中长度最短者。源点v1v2迪杰斯特拉迪杰斯特拉算法算法 在这条路径上，必定只含一条弧，并且这条弧的在这条路径上，必定只含一条弧，并且这条弧的权值最小。权值最小。路径长度最短的最短路径的特点：路径长度最短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该它只可能有两种情况：或者是直接从源点到该点点(只含一条弧只含一条弧)；或者是从源点经过
34、顶点或者是从源点经过顶点v1，再，再到达该顶点到达该顶点(由两条弧组成由两条弧组成)。下一条路径长度次短的最短路径的特点：下一条路径长度次短的最短路径的特点：其余最短路径的特点：其余最短路径的特点：它可能的情况：或者是直接从源点到该点它可能的情况：或者是直接从源点到该点(只含一只含一条弧条弧)；或者是从源点经过顶点或者是从源点经过顶点v1、v2 中的一点或中的一点或两点再到达该顶点两点再到达该顶点(由多条弧组成由多条弧组成)。它或者是直接从源点到该点它或者是直接从源点到该点(只含一条弧只含一条弧)；或者是或者是从源点经过已求得最短路径的顶点，再到达该顶点。从源点经过已求得最短路径的顶点，再到达
35、该顶点。再下一条路径长度次短的最短路径的特点再下一条路径长度次短的最短路径的特点:迪杰斯特拉迪杰斯特拉算法算法求最短路径的迪杰斯特拉算法：求最短路径的迪杰斯特拉算法：设置辅助数组设置辅助数组Dist，其中每个分量，其中每个分量Distk 表表示示 当前所求得的从源点到其余各顶点当前所求得的从源点到其余各顶点 k 的最短路的最短路径。径。一般情况下，一般情况下，Distk=或者或者=+。迪杰斯特拉迪杰斯特拉算法算法1）在所有从源点出发的弧中选取一条权值最小）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。的弧，即为第一条最短路径。2）修改其它各顶点的）修改其它各顶点的Distk值
36、。值。假设求得最短路径的顶点为假设求得最短路径的顶点为w，若若 Distw+G.arcswkDistk则将则将 Distk 改为改为 Distw+G.arcswk。INFINITYvvarcsGvDistii.0V0和和Vi之间存在弧之间存在弧V0和和Vi之间不存在弧之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。迪杰斯特拉迪杰斯特拉算法算法138 30 32V2:813-1330 32V1:13-13302220V3:13-192220V4:19终点终点 从从V0到各终点的最短路径及其长度到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:2051
37、6432085623013717329迪杰斯特拉迪杰斯特拉算法算法顶点对之间的最短路径概念顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有所有顶点对之间的最短路径是指：对于给定的有向网向网G=(V,E),要对要对G中任意一对顶点有序对中任意一对顶点有序对u、v(uv),找出找出u到到v的最短距离和的最短距离和v到到u的最短距离。的最短距离。解决此问题的一个有效方法是解决此问题的一个有效方法是:轮流以每一个顶点轮流以每一个顶点为源点为源点,重复执行迪杰斯特拉算法重复执行迪杰斯特拉算法n次次,即可求得每一即可求得每一对顶点之间的最短路径对顶点之间的最短路径,总的时间复杂度为总的
38、时间复杂度为O(n3)。下面将介绍用弗洛伊德下面将介绍用弗洛伊德(Floyd)算法来实现此功能算法来实现此功能,时间复杂度仍为时间复杂度仍为O(n3),但该方法比调用但该方法比调用n次迪杰斯特次迪杰斯特拉方法更直观一些。拉方法更直观一些。7.5.3 每一对顶点对之间的最短路每一对顶点对之间的最短路径径顶点对之间的最短路径概念顶点对之间的最短路径概念 弗洛伊德算法使用前面定义的图的邻接矩阵弗洛伊德算法使用前面定义的图的邻接矩阵G.arcsNN来存储带权有向图。算法的基本思想是来存储带权有向图。算法的基本思想是:设置一个设置一个N*N的矩阵的矩阵DNN，其中除对角线的元素都，其中除对角线的元素都等
39、于等于0外，其它元素外，其它元素Dij的值表示顶点的值表示顶点i到顶点到顶点j的最短的最短路径长度，运算步骤为：路径长度，运算步骤为：开始时，以任意两个顶点之间的有向边的权值作为路开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为径长度，没有有向边时，路径长度为，此时，此时,Dij=G.arcsij,以后逐步尝试在原路径中加入其它顶点作为中间顶点，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体少了，则以此新路径代替原路径，
40、修改矩阵元素。具体做法为：做法为：第一步，让所有边上加入中间顶点第一步，让所有边上加入中间顶点0，取，取Dij与与Di0+D0j中较小的值作中较小的值作Dij的值的值.第二步，让所有边上加入中间顶点第二步，让所有边上加入中间顶点1，取，取Dij与与Di1+D1j中较小的值，完成后得到中较小的值，完成后得到Dij，如，如此进行下去，当第此进行下去，当第n步完成后，得到步完成后，得到 Dij,即为我们即为我们所求结果所求结果,Dij表示顶点表示顶点i到顶点到顶点j的最短距离。的最短距离。因此，弗洛伊德算法可以描述为因此，弗洛伊德算法可以描述为:D(-1)ij=G.arcsij;/G.arcs为图的
41、邻接矩阵为图的邻接矩阵 D(k)ij=minD(k-1)ij,D(k-1)ik+D(k-1)kj其中其中 k=0,1,2,n-1弗洛伊德算法弗洛伊德算法311426BCA弗洛伊德算法弗洛伊德算法7.6 有向无环图及其应用有向无环图及其应用 一个无环的有向图称做有向无环图，简称一个无环的有向图称做有向无环图，简称DAG图。图。下面是有向树、下面是有向树、DAG图和有向图的例子。图和有向图的例子。有向树有向树 DAG图图 有向图有向图有向无环图可以用来描述含有公共子式的表达式。有向无环图可以用来描述含有公共子式的表达式。例如下述表达式：例如下述表达式：(a+b)(b(c+d)+(c+d)e)(c+
42、d)e)二叉树描述表达式二叉树描述表达式 有向无环图描述有向无环图描述7.6.1 有向无环图有向无环图有向无环图也是描述一项工程或系统的进行过程的有向无环图也是描述一项工程或系统的进行过程的有效工具。有效工具。对整个工程和系统，人们关心两个方面的问题：对整个工程和系统，人们关心两个方面的问题：一是工程能否顺利进行：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。二是估算整个工程完成所必须的最短时间。下面我们通过对有向图进行下面我们通过对有向图进行拓扑排序拓扑排序和和关键路径关键路径操操作来解决这两个问题。作来解决这两个问题。&有向无环图的应用有向无环图的应用在工程实践中，一个工程项
43、目往往由若干个子项目在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：组成，这些子项目间往往有多种关系：先后关系先后关系，即必须在一子项目完成后，才能开始，即必须在一子项目完成后，才能开始实施另一个子项目；实施另一个子项目；子项目之间无次序要求子项目之间无次序要求，即两个子项目可以同时，即两个子项目可以同时进行，互不影响。进行，互不影响。我们把这些子项目、工序、课程看成一个个顶点称我们把这些子项目、工序、课程看成一个个顶点称之为之为活动活动。这种用顶点表示活动、弧表示活动间优先。这种用顶点表示活动、弧表示活动间优先关系的有向无环图称为关系的有向无环图称为顶点表示活动
44、的网顶点表示活动的网(Activity On Vertex network)，简称，简称AOV网网。7.6.2 拓扑排拓扑排序序如下图存在环路，则表示顶点之间的先后关系进如下图存在环路，则表示顶点之间的先后关系进入了死循环。如果用入了死循环。如果用AOV网描述的是一项工程，那网描述的是一项工程，那么这个么这个AOV网网一定不能存在环一定不能存在环。因此，对给定的因此，对给定的AOV网络首先要判定网络中是否网络首先要判定网络中是否存在环路。存在环路。V3V2V0V1在在AOV网中，如果从顶点网中，如果从顶点Vi到到Vj之间存在有向边之间存在有向边,则表示活动则表示活动i必须必须先于先于活动活动j
45、进行。如果顶进行。如果顶点点Vi到顶点到顶点Vj存在一条有向路径时，称存在一条有向路径时，称Vi为为Vj的前趋的前趋，Vj为为Vi的后继。这种前趋后继关系有的后继。这种前趋后继关系有传递性传递性。课程流程图课程流程图C1C2C3C4C5C6C7C8C9C10C11C12程序设计离散数学数据结构汇编语言算法分析计算机原理编译方法操作系统高等数学线性代数电子电路数值分析无 C1C1,C2C1C3,C4C11C5,C3C3,C6无C9C9C9,C10,C1课程编号 课程名称 先决条件 C4C1C2C3C12C9C10C11C6C7C8C5所谓所谓“拓扑排序拓扑排序”就是将就是将AOV网中的各个顶点网
46、中的各个顶点(各个活各个活动动)排列成一个排列成一个线性有序序列，使得所有要求的前趋、后线性有序序列，使得所有要求的前趋、后继关系都能得到满足继关系都能得到满足。由于由于AOV网络中有些顶点之间没有次序要求，它们在网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般结果一般并不是唯一的并不是唯一的。通过拓扑排序还可以判断出此。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图网络是否包含有有向环路，若有向图G所有顶点都在所有顶点都在拓扑排序序列中，则拓扑排序序列中，则AOV网络必定不包含有有
47、向环路。网络必定不包含有有向环路。如上例，可以得到不止一个拓扑排序：如上例，可以得到不止一个拓扑排序：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 显然，对于任何一项工程中各个活动的安排，必须按显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。拓扑有序序列中的顺序进行才是可行的。C4C1C2C3C12C9C10C11C6C7C8C5对于给定的对于给定的AOV网拓扑排序的步骤：网拓扑排序的步骤：1)任选一个入度为任选一个入度为0的顶点输出；的顶点输出；2)
48、删除此顶点和以它为出发点的所有弧；删除此顶点和以它为出发点的所有弧；3)重复执行上述两步，直至图中无入度为重复执行上述两步，直至图中无入度为0的顶点；的顶点；4)若输出顶点数小于图中顶点数，则说明图中存在若输出顶点数小于图中顶点数，则说明图中存在环，无法产生其拓扑排序，否则输出的顶点序列环，无法产生其拓扑排序，否则输出的顶点序列即为此图的一个拓扑排序。即为此图的一个拓扑排序。拓扑排序的步骤拓扑排序的步骤V2V3V1V4V6V5V2V2V5V2V3V5V2V3V4V6V5V2V3V6V5输出输出V1输出输出V4输出输出V6输出输出V3输出输出V5拓扑序列为：拓扑序列为：V1,V4,V6,V3,V
49、5,V2AOV网上的输出网上的输出拓扑排序算法实现拓扑排序算法实现firstarc 4 4 3 2adjvexnextarc14 1 3012345v1v2v3v4v5v6dataV2V3V1V4V6V5Status Topo_Sort(AlGraph G)FindInDegree(G,indegree);InitStack(S);for(i=0;iverticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);if(countG.vexnum)return
50、 ERROR;else return OK;void FindInDegree(ALGraph G,int indegreeMAX);for(i=0;iG.vexnum;+i)indegreei=0;for(i=0;iadjvex+;p=p-nextarc;7.6.3 关键路径关键路径1、什么是、什么是AOE网？网？如果在无环的带权有向图中如果在无环的带权有向图中,用有向边表示一个工用有向边表示一个工程中的程中的活动活动，用边上权值表示活动持续时间，用边上权值表示活动持续时间,用顶点用顶点表示表示事件事件(每个事件表示在它之前的活动已完成，在每个事件表示在它之前的活动已完成，在它之后的活动可以
