数据结构与算法第六章课件

1、第6章 图6.1 图的基本概念6.2 图的存储结构6.3 图的遍历6.4 无向图的应用6.5 有向图的应用6.6 最短路径6.1 图的基本概念图 图是由顶点集合 V 及顶点间的关系集合 E 所组成的一种数据结构： Graph 其中： V=x|x某个数据对象 是非空的有限顶点集合； E=(x, y) | x, y V /边(Edge)的集合 或 E= | x, y V /弧(Arc)的集合 是顶点之间关系的有限集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。6.1 图的基本概念无向图无向图 G 是由两个集合 V(G) 和

2、E(G) 组成的 其中：V(G) 是顶点的非空有限集； E(G) 是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)有向图有向图 G 是由两个集合 V(G) 和 E(G) 组成的 其中：V(G) 是顶点的非空有限集； E(G) 是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v, w是顶点，v 为弧尾(或始点)，w 为弧头(终点)， 。6.1 图的基本概念例无向图G1V(G1)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)有向图G2V(G2)=1,2,3,4,5,6

3、 E(G2)=, , , , , , 245136G2157324G166.1 图的基本概念图的抽象数据类型class Graph public: Graph ( ); /建立一个空图 void InsertVertex ( Type & vertex ); void InsertEdge (int v1, int v2 ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighb

4、or ( int v ); int GetNextNeighbor ( int v1, int v2 );6.1 图的基本概念图的术语邻接点（或相邻点，关联）如果 e=(u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接点或相邻点；称边 e 与顶点 u ,v 关联；如果 a= 是 E(G) 中的一条弧，则称 u 邻接到v 或 v 邻接于 u；称弧 a 与顶点u , v关联。在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。 FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比在

5、线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。 FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比6.1 图的基本概念图的术语权与图的边或弧相关的数。网带权的无向图称为无向网；带权的有向图称为有向网。有向网无向网6.1 图的基本概念图的术语顶点的度（与树中结点的度不同）无向图中，顶点的度是与每个顶点关联的边数，记作 TD(v)。有向图中，顶点的度分成入度与出度入度：以该顶点为终头的弧的数目，记为 ID(v)出度：以该顶点为始点的弧的数目，记为 OD(v)一个顶点的度等于该顶点的入度与出度之

6、和，即TD(v)=OD(v)+ID(v)6.1 图的基本概念图的术语自环称边 (v, v)E(G) 或弧 E(G)为自环 多重边（或弧）若在 G 中有两条或两条以上相同的边或弧，称之为多重边（或弧）6.1 图的基本概念图的术语简单图图中不含有自环和多重边（或弧）的图称为简单图，否则称为非简单图。本章只讨论简单图，即有两类图形不在本章讨论之列6.1 图的基本概念图的术语完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边，则此图为完全无向图。若有 n 个顶点的有向图有n(n-1) 条边，则此图为完全有向图。稀疏图（sparse graph）边或弧很少的图，通常边数 enlog2n稠密图（D

7、ense graph）无向图中，边数接近n(n-1)/2 ；有向图中，弧数接近n(n-1)。6.1 图的基本概念图的术语路径在图 G 中，顶点序列(vi1, vi2, ,vim) 且(vij,vij+1)E 或 E ，j=1, 2, , m-1，则称此序列为从顶点 vi1 到顶点vim的一条路径。顶点 vi1 称为始点；顶点vim 称为终点。回路始点和终点相同的路径。6.1 图的基本概念图的术语简单路径序列中顶点不重复出现的路径。简单回路始点和终点相同的简单路径。6.1 图的基本概念图的术语路径长度 无权图的路径长度是指此路径上边（或弧）的条数。带权图的路径长度是指路径上各边（或弧）的权之和。

8、6.1 图的基本概念图的术语子图已知图 G(V, E) 和图 G(V, E)。若VV 且 EE，则称 G 为 G 的子图。6.1 图的基本概念图的术语连通图在无向图中， 若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。图中任意两个顶点都连通的无向图称为连通图。连通分量非连通图中极大连通子图称做连通分量。1.含有极大顶点数；2.依附于这些顶点的所有边。6.1 图的基本概念图的术语例ABCDEFGIJLHMKABCDEHMFGIJLK3个连通分量 6.1 图的基本概念图的术语强连通图与强连通分量在有向图中，若对于每一对顶点 vi 和 vj，都存在一条从 vi 到 vj 和从 vj 到 v

9、i 的有向路径，则称此图是强连通图。非强连通图的极大强连通子图称做强连通分量。V1V2V3V4V1V3V4V22个强连通分量 6.1 图的基本概念图的术语生成树n个顶点的连通图的生成树是包含图中全部 n 个顶点的一个极小连通子图；ABCDEHM无向图G ABCDEHM无向图G的生成树 多构成回路少不连通含有n-1条边6.1 图的基本概念图的术语生成森林由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。FGIJLK生成森林ABCDEFGIJLHMK无向图GABCDEHM6.2 图的存储结构是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（

10、边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。6.2 图的存储结构邻接矩阵（Adjacency Matrix）在图的邻接矩阵表示中有一个记录各个顶点信息的顶点表（一维数组）还有一个表示各个顶点之间邻接关系的邻接矩阵设图 G = (V, E) 是一个有 n 个顶点的图，则 G 的邻接矩阵定义如下 Aij= 1 若(vi, vj)E 或 E 0 反之6.2 图的存储结构例，无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0

11、1 1 0 0 arc=V1 V2 V3 V4V1V2V3V46.2 图的存储结构例，有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V46.2 图的存储结构从邻接矩阵中可以反映图的许多特征无向图(1) 对称矩阵（可采用压缩存储）；(2) 每一行（或列）1的个数是该顶点的度；(3) 主对角线全为0（简单图）。有向图(1) 每一行1的个数是该顶点的出度； (2) 每一列1的个数是该顶点的入度；(3) 主对角线全为0（简单图）；(4) 有向图的邻接矩阵不一定对称。6.2 图

12、的存储结构带权图的邻接矩阵Aij 0 i=j 其它 wij 若(vi, vj)E 或 E 6.2 图的存储结构用邻接矩阵表示的图的类的定义 class AdjMatrix / 非带权图 int n； / 顶点的个数 int matrixMaxSize MaxSize； / 邻接矩阵 public: AdjMatrix(int m) n=m； ; / AdjMatrix class AdjMatrix / 带权图 const int INFINITE=； int n； /顶点的个数 float matrixMaxSizeMaxSize； / 邻接矩阵 public: AdjMatrix(int

13、m) n=m； ; / AdjMatrix6.2 图的存储结构class AdjGraph AdjMatrix *adj；DataType *elem； public:AdjGraph(int m) adj=new AdjMatrix(m)； elm=new DataSet(m)；void CreateGraph(); / 建立一个图G的邻接矩阵Matrixint LocateVex(v) ; / 确定图G中顶点v在顶点中的位置 DataType GetVex(v); / 得到图G中顶点v的值int FirstAdjVex(v); / 确定图G中顶点v的第一个邻接点 int NextAdjVe

14、x(v,w);/ 确定图G中顶点v相对于w的下一个邻接点 void DFSTraverse(int v)；/图的深度优先遍历 void BFSTraverse(int v)；/图的广度优先遍历; / AdjGraph6.2 图的存储结构邻接矩阵的优点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接矩阵的缺点n 个顶点需要 nn 个单元存储边；空间效率为O(n2)。 对稀疏图而言尤其浪费空间。6.2 图的存储结构邻接表（Adjacency List）表示法无向图的邻接表为每个顶点建立一个单链表第 i 个单链表中的结点表示与顶点 vi 所关联的所有边注：邻接

15、表不唯一，因各个边结点的链入顺序是任意的。6.2 图的存储结构问题在无向图的邻接表中，如何求每个顶点的度？ 第 i 个链表中的边结点个数是顶点 i 的度若顶点数为 n，边数为 e 时，则在无向图的邻接表中共需多少个结点？ n 个顶点结点，2e 个边结点 6.2 图的存储结构有向图的邻接表和逆邻接表在有向图的邻接表中，第 i 个单链表链接的弧都是顶点vi发出的，也称做出边表。在有向图的逆邻接表中，第 i 个单链表链接的弧都是进入顶点 vi 的，也称做入边表。v1v2v3v4V4V3V2V12301V4V3V2V13020邻接表逆邻接表01230123 用邻接表或逆邻接表表示有向图时，只需 n 个

16、顶点结点，e 个弧结点。6.2 图的存储结构data：结点的数据域，保存顶点的数据值。firstout：结点的指针域，指向与该顶点相关联的第一条边 （弧）的地址表头结点datafirstoutadjvexlink边/弧结点adjvex：该边或弧所指向的顶点的序号link：指向下一条边或弧的指针adjvexlinkdatafirstout6.2 图的存储结构网（带权图）的邻接表边/弧结点adjvexcostlink6.2 图的存储结构邻接表表示的图的类定义class EArcNode /边(或弧)结点 int adjvex； / 该边或弧所指向的顶点的序号EArcNode *link； / 指向

17、下一条边或弧的指针 public:EArcNode(int adj) adjvex=adj; link=NULL; friend class LinkGraph; / EArcNodeclass VNode / 表头结点 DataType data； / 顶点的信息 EArcNode *firstout；/ 指向与该顶点关联的第一条边(弧) public: VNode (DataType e) data=e ; f irstout=NULL; friend class LinkGraph; / VNode6.2 图的存储结构class LinkGraph /邻接表 int n； / 顶点的个数

18、 VNode gheadMaxSize； / 邻接表 public: LinkGraph(int m) n=m； void CreateGraph( ) ； / 建立图g int LocateVex(v) ； / 得到顶点v在图中的序号 DataType GetVex(v) ； / 得到顶点v的值 int FirstAdjVex(v) ； / 得到顶点v的第一个邻接顶点 int NextAdjVex(v, w); / 确定图G中顶点v相对于w的下一个邻接点 void DFSTraverse(int v)； / 图的深度优先遍历 void BFSTraverse(int v)； / 图的广度优先

19、遍历; / LinkGraph6.2 图的存储结构图的操作在邻接表的上的实现 int FirstAdjVex (int v) return gheadv-firstout.adjvex； / FirstAdjVex int NextAdjVex(int v，int w) p=gheadv-firstout； while (p & p-adjVex!=w) p=p-link； if (!p | !p-link) return 0； else return p-link-adjVex； / NextAdjVex6.2 图的存储结构讨论：邻接表与邻接矩阵的比较联系都可以用来存储有向图和无向图；邻接表

20、中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。6.2 图的存储结构区别对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复杂度为O(n+e)。邻接矩阵多用于稠密图的存储（e接近n(n-1)/2）；而邻接表多用于稀疏图的存储（en2）。6.3 图的遍历图的遍历从图中某一顶点出发，按照某种搜索路径访问图中所有的顶点，使得每个顶点被访问一次且仅被访问一次。图的遍历操作要解决的关键问题在图中，如何选取遍历的起始顶点？ 解决方案：从编号小的顶点开始 6.3 图的遍历从某个起

21、点开始可能到达不了所有其它顶点，怎么办？ 解决方案：多次调用从某顶点出发遍历图的算法。图中可能存在回路，某些顶点可能会被重复访问，如何避免遍历因回路而陷入死循环。 解决方案：附设访问标志数组visitedn 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问后，如何选取下一个要访问的顶点？ 解决方案：深度优先遍历和广度优先遍历6.3 图的遍历深度优先遍历DFS（Depth First Search）DFS算法思想从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至V0 的所有邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾

22、被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。6.3 图的遍历例深度优先搜索过程 深度优先生成树6.3 图的遍历从访问图中某一起始点 v 开始，由 v 出发，访问它的第一邻接点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问， 如此进行下去，直到某一顶点所有的邻接点都被访问完。退回到上一步刚访问过的顶点，看是否还有其它没有被访问的邻接点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。6.3 图的遍历连通图的深度优先遍

23、历算法void DFSTraverse( ) /深度优先求图的连通分量 int visitedn； /设置访问标志数组 for (v=0; vn; v+) visitedv=0； /初始化访问标志数组 for (v=0; vn; v+) if (!visitedv) DFS (v)；/每次从尚未访问过的顶点出发/ DFSTraversevoid DFS (int v) /从顶点v出发访问包含该顶点的最大连通子图中的所有顶点 visitedv=1； visit(v)； for (w=firstAdjVex(v); w; w=nextAdjVex(v, w) if (!visitedw) DFS(

24、w)； / DFS6.3 图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回 V1遍历序列：V1V2 V2V4 V4V5 V56.3 图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回 V1遍历序列：V1V2 V2V4 V4V5V8 V86.3 图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返回 V1遍历序列：V1V2 V2V4 V4V5V86.3 图的遍历例，深度优先遍历序列，入栈序列，出栈序列。V1V3V2V4V5V6V7V8深一层递归递归返

25、回 V1遍历序列：V1 V7V2V4V5V8V3 V3V6 V6V76.3 图的遍历不同存储结构下的DFS实现图以邻接矩阵存储 void DFS (int v) visitedv=1; visit(v); for (w=0; w0) if (!visitedw) DFS(w); / DFS图以邻接表存储void DFS(int v) visitedv=1; p=gheadv-firstout; while (p) w=p-adjvex; if (!visitedw ) DFS(w); p=p-link; / DFS6.3 图的遍历例V1V2V4V5V3V7V6V8例01231342datafi

26、rstout 1 6 7 2adjvexlink45 5 3 716785676深度遍历：V1V3 V7 V6 V2 V4 V8 V56.3 图的遍历算法分析图中有 n 个顶点，e 条边。如果用邻接矩阵存储图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。如果用邻接表存储图，在每一个单链 表中可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点(无向图)，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。6.3 图的遍历广度优先遍历BFS（Breadth First Search）思路在访

27、问了起始顶点 v 之后，由 v 出发，依次访问 v 的所有未被访问过的邻接点 w1, w2, , wt，然后再顺序访问 w1, w2, , wt 的所有未被访问过的邻接点。再从这些访问过的顶点出发，再访问它们的所有未被访问过的邻接点， ，如此重复，直到图中所有顶点都被访问完为止。6.3 图的遍历例 广度优先搜索过程 广度优先生成树6.3 图的遍历说明广度优先遍历是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先遍历不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的顶点，以便向下一层访问。与深度优先

28、遍历过程一样，为避免重复访问，需要一个辅助数组 visited n，对被访问过的顶点加以标记。6.3 图的遍历算法思想1）清队列Q；2）对出发顶点 v 做v 入队；标记 v；3）当 Q 不空反复做：出队头元素到 u；访问 u；将 u 的每个未被访问的邻接点 w 入队；标记 w。6.3 图的遍历广度优先搜索算法void BFS (int v) /广度优先求图的连通分量 Q=new Queue( )； /清队列Q Q.Enter(v)； /每次从尚未访问过的顶点中选取一个顶点v visitedv=1； /标记v while (!Q.Empty() /Q不空 u=Q.Leave()； /出队头元素到

29、u visited(u)； /访问u for (w=FirstAdjVex(u); w; w=NextAdjVex(u, w) if (!visitedw) Q.Enter(w)； /将u的每个未被访问的邻接点w 入队 visitedw=1； / BFS6.3 图的遍历BFS从出发点只能遍历一个连通分量，若对任意图的遍历需要对每个分量中一个未被访问的顶点为出发点进行BFS遍历。 void BFSTraverse() /广度优先求图的连通分量 int visitedn； /设置访问标志数组 for (v=0；vn；v+) visitedv=0； /初始化访问标志 for (v=0；vn；v+)

30、if (!visitedv) BFS( v)； / BFSTraverse6.3 图的遍历例，广度优先遍历序列，入队序列，出队序列。V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8V4V1V2V36.3 图的遍历算法分析如果用邻接矩阵存储图，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。如果用邻接表存储图，则循环的总时间代价为 D0 + D1 + + Dn-1 = O(e)，其中的 Di 是顶点 i 的度。而且对所有顶点访问1次，所以遍历图的时间复杂性为O(n+e)。6.3 图的遍历DFS 与 BFS 之比较空间

31、复杂度相同，都是O(n)（借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。6.4 无向图的应用最小生成树生成树包含连通无向图中全部顶点的极小连通子图（n 个顶点、n-1 条边）一个连通图的生成树不唯一使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树对于非连通图，通过图的遍历，得到的是生成森林6.4 无向图的应用最小生成树例（a）深度优先生成树 （b） 广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V86.4 无向图的应用最小生成树最小生成树MST（Minimum-cost Spanning T

32、ree）连通无向网中边权之和最小的生成树最小生成树MST的典型用途假设在 7 个城市之间要建立通信网络线，要求使得每个城市之间连通且费用最少。数学模型连通网表示7个城市间的通信网顶点表示城市边表示城市间的通信线路边的权值表示线路的经济代价28123456710161418122524226.4 无向图的应用最小生成树构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用 n-1 条边来连接网络中的 n 个顶点；不能使用产生回路的边。求一个连通无向网中最小生成树的方法Prim 算法Kruskal 算法都是利用MST的性质构造最小生成树6.4 无向图的应用最小生成树最小生成树

33、的性质若集合 U 是集合 V 的一个非空子集，若 (u, v) 是一条具有最小权值的边，其中 uU，vV-U；则：(u, v) 必在最小生成树上。UV-U6.4 无向图的应用最小生成树Prim 算法Prim 算法的基本思想设连通 N= V, E ，T 是 N 的最小生成树中边的集合， U 是生成树的顶点集合。（1） T= ，U= u （ u 为任一顶点）； （2）在所有 uU，vV-U 的边 (u, v)E 中找一条代价最小的边 (u, v) 加入集合 T 中，同时 v 加入 U； （3）重复（2），直到 U=V 为止。6.4 无向图的应用最小生成树例012634528161222251025

34、1418T = U = 0 Min10, 28=10(0,5), 5Min25, 28=25, (5,4), 4Min28, 25, 22=22, (4,3), 3Min28, 25, 18, 12=12, (3,2), 2Min28, 25, 18, 16=16, (2,1), 1Min25, 18, 14=14, (1,6), 6 U=V，算法结束6.4 无向图的应用最小生成树Prim 算法的实现图的存储：邻接矩阵在构造过程中，还设置了一个辅助数组closedge：每个元素closedgev有两个域 lowcost：存放生成树顶点集合内顶点到生成树外各顶点v的各边上的当前最小权值adjve

35、x：记录生成树顶点集合外各顶点距离集合内哪个顶点最近（即权值最小）6.4 无向图的应用最小生成树从顶点0出发利用Prim算法构造最小生成树过程中辅助数组各分量的值的变化i1 23456closedgeadjvexlowcost0280000100525422424312318216i1 23456edgeadjvexlowcost1140123456U10000005250101142213121216111416.4 无向图的应用最小生成树利用 Prim 算法求最小生成树的算法class AddArray int adjvex; float lowcost;/ AddArrayvoid Mi

36、nSpanTree_Prim (int u, AddArray closedge, AddArray edge, AdjMatrix G)/ 设图以邻接矩阵存储，用Prim算法从顶点u出发构造网G的最小生成树且保存到数组edge中 for(v=0；vn；v+) Uv=0； Uu=1； for (v=0；v n；v+) if（u!=v) closedgev.adjvex=u;6.4 无向图的应用最小生成树 closedgev.lowcost=G.matrixuv; for (t=1；tn；t+) /选择其余的n-1个顶点 k=minimum(closedge)； /求出T的下一个顶点k顶点 u=

37、closedgek.adjvex； edgek.lowcost=G.matrixku; /保存选中边的权值 edgek.adjvex=u; /保存选中边的顶点 Uk=1； for (j=0；jG.matrixkj) closedgej.lowcost=G.matrixkj； closedgej.adjvex=k； / for / MinSpanTree_Prim6.4 无向图的应用最小生成树Prime 算法分析设连通无向网有 n 个顶点，则该算法的时间复杂度为O(n2)适用于稠密的网络6.4 无向图的应用最小生成树Kruscal 算法基本思想 先构造一个只含 n 个顶点、不含有边的零图 T ，

38、然后从权值最小的边开始，若它的添加不使 T 产生回路，则在 T 上加上这条边，如此重复，直至加上 n-1 条边为止。6.4 无向图的应用最小生成树例1012141625226.4 无向图的应用最小生成树算法思想设无向连通图 G=(V, E) 的最小生成树为 T=(U, TE)1）初始化：U=V；TE= ；2）循环直到 T 中的连通分量个数为 1在 E 中寻找最短边 (u, v)；如果顶点 u、v 位于 T 的两个不同的连通分量，则将边 (u, v) 并入 TE，并将这两个连通分量合为一个；在 E 中标记边 (u, v)，使之不参加后续最短边的选取。有向图可以用来描述一个工程（或系统）的进行过程

39、。每个工程由若干个子工程（活动）组成，完成了这些子工程整个工程就结束了。这些子工程间有两种关系有先后顺序：即前一子工程结束后一子工程才能开始无先后顺序：即两个子工程谁先谁后都互不影响 6.5 有向图的应用6.5 有向图的应用例，学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求有先修课程，有些则不要求。C1高等数学C2计算机基础C3离散数学C1, C2 C4数据结构C3, C2C5高级语言程序设计C2C6编译原理C5, C4C7操作系统C4, C9C8普通物理C1C9计算机原理C8 课程代号课程名称先修课程6.5 有向图的应用两个问题整个工程能否顺利进行？哪些活动

40、是影响工程按期完工的关键？ 拓扑排序 关键路径6.5 有向图的应用拓扑排序AOV 网用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网（Activity On Vertices）若是图中的有向边，则表示活动 vi 必须先于活动 vj 进行AOV 网中不允许有回路，这意味着某项活动不能以自己为先决条件6.5 有向图的应用拓扑排序例学生课程学习工程图6.5 有向图的应用拓扑排序由给定的 AOV 网所描述的工程是否可行？检测方法：拓扑排序对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在回路，工程可行。相反，如果得不到满足要求的拓扑

41、有序序列，则说明AOV 网中存在有向回路，此 AOV 网所代表的工程是不可行的。6.5 有向图的应用拓扑排序概念拓扑（有序）序列在 AOV 网中若将各个顶点（代表各个活动）排列成一个线性有序的序列 v1, v2, , vn，使得若从顶点 vi 到 vj 有一条有向路径，则在序列中顶点 vi 必须排在顶点 vj 之前。拓扑排序在 AOV 网中找一个拓扑序列的过程。6.5 有向图的应用拓扑排序例，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4

42、 , C7 , C6拓扑序列并不唯一6.5 有向图的应用拓扑排序例，对下列有向图不能求得它的拓扑有序序列BDAC因为图中存在一个有向回路 B, C, D6.5 有向图的应用拓扑排序拓扑排序的思想输入一个 AOV 网，令 n 为顶点个数。(1) 在 AOV 网中选一个没有前驱的顶点，并输出之。(2) 从图中删去该顶点，同时删去与该顶点关联的弧。(3) 重复以上 (1)、(2) 步，直到全部顶点均已输出，拓扑序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV 网中一定存在有向回路。6.5 有向图的应

43、用拓扑排序例eabcghdfabhcdgfe在算法中需要用定量的描述替代定性的概念 入度为零的顶点 弧头顶点的入度减 1输出没有前驱的顶点删除顶点及以它为尾的弧6.5 有向图的应用拓扑排序拓扑排序的算法思想图的存储：邻接表增设一个数组 indegree ，记录各个顶点的入度在输入数据时，每输入一条弧，就需要建立一个弧结点，将它链入相应弧链表中，并统计入度信息 EArcNode *p = new EArcNode (k); plink = gheadj.firstout; gheadj.firstout = p; indegreek+;/顶点 k 入度加1 6.5 有向图的应用拓扑排序使用一个链

44、式栈，存放入度为零的顶点只要出现入度为零的顶点，就将它加入栈中由于表头结点的“入度计数域”在变成0之后，已经无用，故用它作为链式栈使用顶点栈的拓扑排序算法可以描述如下(1) 建立入度为零的顶点栈；(2) 当入度为零的顶点栈不空时，重复执行 从顶点栈中退出一个顶点，并输出之；该顶点发出的所有弧的终点的入度减1；如果弧的终点入度减为至0，则该顶点压入顶点栈；(3) 如果输出顶点个数少于 AOV 网的顶点个数，则说明网中存在有向回路；否则拓扑排序完成。6.5 有向图的应用拓扑排序拓扑排序的算法bool TopologicalSort () FindInDegree (indegree)； top=-

45、1; for (i=0；i-1) i=top; top=indegreetop; coutlink) k=p-adjvex； if (!(-indegreek) indegreek=top； top=k; /for /while if (countn) return false； return true； /TopologicalSort6.5 有向图的应用拓扑排序例6.5 有向图的应用拓扑排序拓扑排序的算法分析设AOV网中有 n 个顶点，e 条弧在拓扑排序的过程中，建立顶点栈所需要的时间是O(n)一般情况下，每个顶点进一次栈，出一次栈，共输出 n 次顶点入度减 1 的运算共执行了 e 次总的

46、时间复杂度为 O(n+e)6.5 有向图的应用关健路径AOE网在没有回路的有向网中，如果用顶点表示事件（Event） 用弧表示一个工程中的各项活动（Activity）用弧上的权值表示活动的持续时间（Duration）则称这样的有向图为用弧表示活动的网（Activity on Edge）6.5 有向图的应用关健路径例在 AOE 网中，有些活动（弧）顺序进行，有些活动并行进行。从始点到终点的有向路径可能不止一条，完成不同路径的活动所需的时间也可能不同，但只有各条路径上所有活动都完成了，整个工程才算完成。6.5 有向图的应用关健路径AOE 网在某些工程预算方面非常有用，它可以使人们了解到完成整个工程

47、最短需要多少时间（假设网中没有有向回路）？为缩短完成工程所需的时间，应当加快哪些活动？6.5 有向图的应用关健路径问题1完成工程的最短时间？完成整个工程所需的最短时间定义为从开始顶点到结束顶点的最长路径的长度，即在这条路径上所有活动的持续时间之和最大。从开始顶点到结束顶点的这条最长的路径称为关键路径（Critical Path）关键路径上的所有活动称为关键活动说明：关键路径可能不止一条6.5 有向图的应用关健路径问题2为缩短工期，应当加快哪些活动？要找出关键路径，必须找出关键活动，只有提高关键活动的功效，才可能缩短整个工期。关键路径为： (v0, v1, v4, v6, v8 ) 或 (v0,

48、 v1, v4, v7, v8 )关键路径的长度为：18关键活动为：a1, a4, a7, a10, a8, a116.5 有向图的应用关健路径定义几个与计算关键活动有关的量e(i)活动 ai 的最早开始时间l(i) 活动 ai 的最迟开始时间活动 ai 用弧 表示dut() 表示活动 ai 持续的时间关键活动：e(i)=l(i) 的活动 ai 6.5 有向图的应用关健路径ee(i)事件 vi 的最早发生时间从始点 v0 到顶点 vi 的最长路径长度le(i)事件 vi 的最晚发生时间在保证终点 vn-1 在 le(n-1) 时刻完成的前提下，事件 vi 的最晚发生时间P(j) 表示以顶点 v

49、j 为弧头的所有弧的尾顶点集合S(j) 表示以顶点 vj 为弧尾的所有弧的头顶点集合6.5 有向图的应用关健路径例ee(1)=6ee(2)=4le(4)=7a4= a5=e(4)=ee(1)=6e(5)=ee(2)=4l(4)=le(4)-dut()=6l(5)=le(4)-dut()=6是关键活动， 不是关键活动6.5 有向图的应用关健路径求关键路径的算法思想1）建立AOE网；2）从始点 v0 出发，令 ee(0)=0，边进行拓扑排序，边计算其余各顶点的 ee(i)。若图中有回路则结束。3）从终点 vn-1 出发，le(n-1)=ee(n-1)，按逆拓扑有序的顺序求 le(i)，i=n-2,

50、 , 0。4）根据各点的 ee 和 le 的值，求每个活动（弧）的最早开始时间 e(i) 和最迟开始时间 l(i)。若某弧满足条件 e(i) = l(i)，则对应活动是关键活动。6.5 有向图的应用关健路径算法bool TopologicalSort(Stack &T) /求以邻接表存储的有向图中各顶点事件的最早发生时间ee。/S是入度为零顶点栈，T为拓扑序列顶点栈。若该有向图无回路，则该算法返回true且栈T返回该有向图的一个拓扑序列，否则返回false。 Stack S; FindInGegree(indegree) /求各顶点的入度indegree count=0; ee0.n-1=0;

51、 /初始化 for (k=0; klink) /对顶点j的每个后继顶点入度减1 k=p-adjvex; if (-indegreek=0) S.Push(k); /若入度为0，则入栈S if (eej+dut()eek) eek=eej+dut(); /对j的各后继点k修改eek if(countlink) k=p-adjvex; if (lek-dut()lej) lej=lek-dut(); for (j=0; jlink) k=p-adjvex; tag=(eej=lek-dut()?*: ; coutjkdut()eejlek-dut()tag; /CriticalPath6.5 有向

52、图的应用关健路径例顶点eeileiv0v1v2v3v4v5v6v7v80645771614180668710161418活动eklkl-ea1a2a3a4a5a6a7a8a9a10a11000022033660462583770770710316160141406.5 有向图的应用关健路径算法分析拓扑排序求 eei 和逆拓扑有序求 lei 时，所需时间为 O(n+e)求各个活动的 ek 和 lk 时所需时间为O(e)总共花费时间仍然是 O(n+e)6.6 最短路径（Shortest Path）6.6 最短路径（Shortest Path）求从某个源点到其余各点的最短路径 Dijkstra 算法

53、每一对顶点之间的最短路径 Floyd 算法6.6 最短路径求单源最短路径单源最短路径问题如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法Dijkstra 算法给定一个网 G = V, E,W 与源点 v0，求从 v0 到 G中其它顶点的最短路径。规定各边（或弧）上的权值大于或等于0。6.6 最短路径求单源最短路径Dijkstra 算法思想按路径长度的递增次序，逐步产生各条最短路径。第一条最短路径长度的求法这条路径必定只含一条弧 ，并且这条弧的权值最小。w1w2wkwn-16.6 最短路径求单源最短路径第二

54、条最短路径长度的求法 它只可能有两种情况直接从源点到某顶点 v2 （只含一条弧）从源点经过顶点 v1，再到达该顶点 v2（由两条弧组成）6.6 最短路径求单源最短路径其余最短路径的求法或者是直接从源点到某顶点vk（只含一条弧）或者是从源点经过已求得最短路径的顶点，再到达该顶点6.6 最短路径求单源最短路径例602010305010003421103421源点终点最短路径路径长度v0v110v2-v330v4100605090606.6 最短路径求单源最短路径Dijkstra 算法实现引入一个辅助数组dist它的每一个分量 disti 表示当前找到的从源点 v0 到终点 vi 的最短路径的长度初

55、始状态若从源点 v0 到顶点 vi 有边，则disti为该边上的权值若从源点 v0 到顶点 vi 没有边，则disti为+ 每次求得一条最短路径之后，其终点 vk 加入集合 S，然后对所有的 viV-S，修改其 disti 值6.6 最短路径求单源最短路径Dijkstra 算法描述如下初始化置S v0 ;disti cost0i, i= 1, ,n-1; / n为图中顶点个数(1) 求出最短路径的长度distk min disti , iV-S ; S S k ;(2) 修改对于每一个 iV-S， disti min disti, distk + costki ；(3) 重复 (1) 和 (2

56、) n-1次。6.6 最短路径求单源最短路径计算最短路径的图邻接矩阵类的定义const int Vexnum =20； /图中最大顶点个数#define max /定义无穷大 class Graph /图的类定义 float costVernumVernum； float dist Vexnum； /最短路径长度数组 int pathVexnum； /最短路径顶点序列数组 int findVexnum； /最短路径顶点集public: void ShortestPath (int，int)； int choose ( int )；/ Graph6.6 最短路径求单源最短路径Dijkstra 描述的单源最短路径算法void ShortestPath_DIJ (int v0; int path; int *dist) for (v=0; vVexnum; v+) findv=0; pathv=0; distv=costv0v; findv0=1; for (i=1; i Vexnum; i+) k=mini