05-1 第5章 图1.pptx

第1页：第五章图封面

第五章图

第2页：图

图（Graph）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图状结构可以描述各种复杂的数据对象。图的应用极为广泛，特别是近年来的迅速发展，已经渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。

第3页：图的出现最早可以追溯到1736年

图的出现最早可以追溯到1736年，著名的数学家欧拉使用它解决了经典的柯尼斯堡七桥难题。从此，有关图的理论形成了一个专门的数学分支——图论。

第4页：柯尼斯堡是18世纪初普鲁士的一个小镇

柯尼斯堡是18世纪初普鲁士的一个小镇，普雷格尔河流经此镇，共有7座桥横跨河上，把全镇连接起来。当时当地居民热衷于一项非常有趣的消遣活动：在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点，这就是柯尼斯堡七桥问题。为了解决七桥问题，欧拉第一次提出了“图”的概念。欧拉用点表示岛和陆地，两点之间的连线（边）表示连接它们的桥，将河流、小岛和桥简化为一幅图。

定义与顶点相连的边的数目为顶点的度，欧拉证明了如果这个问题有答案的话只有在每个顶点的度都是偶数的情况下才成立，而在七桥所形成的图中没有一个点具有偶数条边，因此七桥问题不存在解。

第5页：图状结构的实际背景在城市之间建立通讯网络

图状结构的实际背景在城市之间建立通讯网络，使得其中的任意两个城市之间有直接或间接的通讯线路，假设已知每对城市之间通讯线路的造价，要求找出一个造价最低的通讯网络。

第6页：城市航线网天津北京上海广州深圳

城市航线网天津北京上海广州深圳

第7页：计算机网络

计算机网络computerconnection

第8页：很多问题都可以抽象成一个图结构

很多问题都可以抽象成一个图结构，考虑如下三个例子：将电影界的所有演员构成顶点集V，其中两位演员u和v如果共同出演过至少一部影片，那么在u和v之间连接一条边。演员之间的这种合作关系看作对等关系。按照这种方式建立的图是无向图。将C++程序中所有的类构成顶点集V，且如果类a是类b的子类，则定义一条从b指向a的有向边。

按照这种方式建立的图是有向图。将多个城市构成顶点集V，如果城市a和城市b之间有一条高速公路，则在a和b之间连接一条边。允许在两个城市之间修建多条高速公路。按照这种方式建立的图是多重图。

第9页：不一定具有一个根结点没有明显

不一定具有一个根结点没有明显的父子关系从一个顶点到另一个顶点可能有多个（或0个）路径图VS.树

第10页：第五章图目录

第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用

第11页：定义的定义

定义5.1：图G由两个集合V和E组成，记为G=(V,E)；其中V是顶点的有限集合，E是连接V中两个不同顶点的边的有限集合。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G为有向图。如果顶点对是无序对，则称G是无向图。5.1图的基本概念

第12页：定义的定义（续2）

定义5.2若G=(V,E)是有向图，则它的一条有向边是由V中两个顶点构成的有序对，亦称为弧，记为<w,v>，其中w是边的始点，又称弧尾；v是边的终点，又称弧头。

第13页：有向图

有向图G=（V，E）V={ v1，v2，v3，v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}v1v3v2v

第14页：无向图

无向图G=(V,E)V={V1, V2, V3, V4 ,V5}E={(V1, V4 ), (V1, V2), (V2, V3 ), (V2, V5 ),(V3, V4 ), (V3, V5 ) }V1V4V3V2V

第15页：定义的定义（续2）

定义5.3 在无向图中

若两个顶点w和v之间存在一条边(w, v)，则称w, v是相邻的，二者互为邻接顶点。在有向图中，若存在一条边<w, v>，则称顶点w邻接到顶点v，顶点v邻接自顶点w.v3v4v1v2oooov1v2v3v

第16页：定义5.4由于E是边的集合

定义5.4由于E是边的集合，故一个图中不会多次出现一条边。若去掉此限制，则由此产生的结构称为多重图。图(c)就是一个多重图。(a) (b) (c)

第17页：定义的定义（续3）

定义5.5设G是无向图，v∈V(G)，E(G)中以v为端点的边的个数，称为顶点的度。若G是有向图，则v的出度是以v为始点的边的个数，v的入度是以v为终点的边的个数。–有向图中，以某顶点为弧头的弧的数目称为该顶点的入度。以某顶点为弧尾的弧的数目称为该顶点的出度。顶点的度=入度+出度。

第18页：入度

度: D(v)入度: ID(v)出度: OD(v)D(v)=ID(v)+OD(v)Graph2V5V1V2V3V4V4V3V2V1Graph

第19页：设图G(可以为有向或无向图)共有n个顶点

设图G(可以为有向或无向图)共有n个顶点，e条边，若顶点vi的度数为D(vi)，则因为一条边关联两个顶点，而且使得这两个顶点的度数分别增加1。因此顶点的度数之和就是边的两倍。

第20页：定义5.6设G是图

定义5.6设G是图，若存在一个顶点序列使得或属于E(G)，则称vp到vq存在一条路径，其中vp称为起点，vq称为终点。路径的长度是该路径上边的个数。如果一条路径上除了起点和终点可以相同外，再不能有相同的顶点，则称此路径为简单路径。如果一条简单路径的起点和终点相同，且路径长度大于等于2，则称之为简单回路。

第21页：之间存在一条路径

图(a)中，v1到v3之间存在一条路径v1,v2,v5,v4,v3，同时这也是一条简单路径；v1,v2,v5,v4,v3,v1是一条简单回路。(a) (b) (c)

第22页：路径

V5V4V2V1V3V1V2V3V4路径：v1 v3 v4 v3 v5简单路径：v1 v3 v5简单回路：v1 v2 v3 v1路径：v1 v3 v2 v4 v3 v2简单路径：v1 v3 v2简单回路：v1 v3 v2 v

第23页：定义的定义（续4）

定义5.7设G，H是图，如果V(H)V(G)，E(H)E(G)，则称H是G的子图，G是H的母图。如果H是G的子图，并且V(H)=V(G)，则称H为G的支撑子图。

第24页：定义的定义（图）

24……V5V1V2V3V4V1V1V2V5V2V3V5V1V2V3V

第25页：定义的定义（续2）

V4V3V2V1V1V2V1V4V3V2V1V4V3V1……

第26页：定义5.8设G是图

定义5.8设G是图，若存在一条从顶点vi到顶点vj的路径，则称vi与vj可及(连通)。若G为无向图，且V(G)中任意两顶点都可及，则称G为连通图。若G为有向图，且对于V(G)中任意两个不同的顶点vi和vj，vi与vj可及，vj与vi也可及，则称G为强连通图。也可以定义“弱连通图”的概念，即在任何顶点u和v之间，至少存在一条从u到v的路径或者存在一条从v到u的路径。

第27页：定义5.8设G是图（图）

V5V4V2V1V3V1V2V3V

第28页：定义的定义（续5）

定义5.9设图G=(V，E)是无向（或有向）图，若G的子图GK是一个（强）连通图，则称GK为G的（强）连通子图。

第29页：定义的定义（续2）

定义5.10对于G的一个连通子图GK，如果不存在G的另一个连通子图G′，使得V(GK)⊂V(G′)，则称GK为G的连通分量。

第30页：图的连通子图

30(a) (b) (c)(d) (e)一个图的连通子图e是a的连通分量

第31页：连通分量

连通分量V4V3V1V2V4V3V2V

第32页：连通分量（续2）

连通分量BAEJKGLMDIFCHALJCFBMDEKIHG

第33页：有时候，图不仅要表示出元素之间

有时候，图不仅要表示出元素之间是否存在某种关系，同时还需要表示与这一关系相关的某些信息。例如，在计算机网络对应的图中，顶点表示计算机，顶点之间的边表示计算机之间的通讯链路。实际中，为了管理计算机网络，我们需要这个图包含更多的信息，例如每条通讯链路的物理长度、成本和带宽等信息。为此，我们为传统图中的每条边添加相应的数据域以记录所需要的信息。

第34页：定义的定义（续6）

定义5.11设G=(V,E)是图，若对图中的任意一条边l，都有实数w(l)与其对应，则称G为权图，记为G=(V,E,w)。记w(u,v)表示w((u,v))或w(<u,v>)，规定：∀u∈V,有w((u,u))=0或w(<u,u>)=0∀u,v∈V,若(u,v)∉E(G)或<u,v>∉E(G)则w((u,v))=＋∞或w(<u,v>)=＋∞

第35页：定义5.12若是权图G中的一条路径

定义5.12若是权图G中的一条路径，则称为加权路径的长度或权重。权通常用来表示从一个顶点到另一个顶点的距离或费用。

第36页：定义5.12若是权图G中的一条路径（图）

V1V2V3V42357

第37页：无向图与有向图常用术语对照表

无向图与有向图常用术语对照表：无向图与有向图在基本术语上的对应关系如下表。

第38页：第五章图目录

第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用

第39页：邻接矩阵邻接表(逆邻接表)1

邻接矩阵邻接表(逆邻接表)1、图的存储结构

第40页：用顺序方式或链接方式存储图

用顺序方式或链接方式存储图的顶点表v0,v1,…vn-1,图的边用n×n阶矩阵A =(aij)表示，A的定义如下：（a）若图为权图，aij对应边<vi,vj>的权值；（b）若图为非权图，则（1）aii=0；（2）aij=1，当i≠j且<vi,vj>或(vi,vj)存在时；（3）aij=0，当i≠j且<vi,vj>或(vi,vj)不存在时。

称矩阵A为图的邻接矩阵。1、邻接矩阵

第41页：无向图的邻接矩阵无向图

41[例1]无向图的邻接矩阵无向图的邻接矩阵是对称阵。012301111001100111100123V0V3V2V

第42页：有向图的邻接矩阵

42[例2]有向图的邻接矩阵V0V3V4V1V2012340 1 0 0 01000101010100000001001234

第43页：权图的邻接矩阵

43[例3]权图的邻接矩阵0123035830∞45∞028 4 200123V0V3V2V135284

第44页：特点：无向图的邻接矩阵对称

特点：无向图的邻接矩阵对称，可压缩存储，有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称，有n个顶点的有向图需存储空间为n²

第45页：借助邻接矩阵

借助邻接矩阵，可以很容易地求出图中顶点的度。–无向图邻接矩阵的第i行（或第i列）的非零元素的个数是顶点Vi的度。–有向图邻接矩阵第i行的非零元素的个数为顶点Vi的出度；第i列的非零元素的个数为顶点Vi的入度。

第46页：借助邻接矩阵（图）

Graph1V4V3V2V1Graph2V5V1V2V3V401100000000110000 1 0 1 010101010111010001100

第47页：邻接表是图的一种链式存储结构

472、邻接表邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。V0V3V2V1V0V1V2V30231123∧012∧03∧03∧

第48页：顶点的结构非权图中边结点结构

顶点的结构非权图中边结点结构为（VerAdj,link）权图中边结点结构为（VerAdj,cost,link）VerName adjacentVerAdj cost linkVerAdj link

第49页：无向图的邻接表

49[例1]无向图的邻接表V0V3V2V1V0V1V2V30231123∧012∧03∧03∧

第50页：有向图的邻接表

50[例2]有向图的邻接表V0V1V2V3V4024311∧3∧0∧0∧4∧1∧3∧V0V3V4V1V

第51页：对于用邻接表存储的有向图

对于用邻接表存储的有向图，每条边只对应一个边结点；而对于用邻接表存储的无向图，每条边则对应两个边结点。根据邻接表，可以统计出有向图中每个顶点的出度。但是，如果要统计顶点的入度，每统计一个顶点，就要遍历所有的边结点，其时间复杂度为O(e)(e为图中边的个数)，从而统计所有顶点入度的时间复杂度为O(ne)(n为图的顶点个数)。

建立逆邻接表(顶点的指向关系与邻接表恰好相反)，根据逆邻接表，很容易统计出图中每个顶点的入度。

第52页：有向图的逆邻接表

52[例3]有向图的逆邻接表V0V3V4V1V2V0V1V2V3V4024311∧0∧2∧2∧4∧1∧3∧∧

第53页：权图的邻接表

53[例4]权图的邻接表V0V3V2V135284V0V1V2V30231133∧825082∧214053∧2033∧4

第54页：采用邻接矩阵还是用邻接表来存储图

采用邻接矩阵还是用邻接表来存储图，要视对给定图实施的具体操作而定。对于边很多的图(也称稠密图)，适于用邻接矩阵存储，因为占用的空间少。而对于顶点多而边少的图(也称稀疏图)，若用邻接矩阵存储，对应的邻接矩阵将是一个稀疏矩阵，存储利用率很低。因此，顶点多而边少的图适于用邻接表存储。

第55页：邻接矩阵存储的图类

邻接矩阵存储的图类Graph_Matrix邻接表存储的图类Graph_List2、图的实现

第56页：用邻接矩阵存储的图类

561.用邻接矩阵存储的图类●Graph_Matrix类声明const int MaxGraphSize = 256 ;

第57页：构造函数与析构函数

public://I.构造函数与析构函数Graph_Matrix();~Graph_Matrix();//II.图的维护函数intGraphEmpty(void)const//检测图是否为空intGraphFull(void) const ;//检测图是否已满，即顶点个数是否越界intNumberOfVertices( void ) const ;//返回图的顶点个数intNumberOfEdges( void ) const ;

第58页：向图中插入一个顶点

voidInsertVertex(constint&v);//向图中插入一个顶点voidInsertEdge( const int & v1, const int & v2, int weight );

第59页：构造函数

59//构造函数,创建一个图Graph_Matrix :: Graph_Matrix (){ cin >> graphsize;for( int i = 0 ; i < graphsize ; i ++ )for( int j = 0 ; j < graphsize ; j ++ )cin >> edge[i][j];}0123035830∞45∞028 4 200123ADCB35284

第60页：取得序号

60//取得序号为v的顶点的第一个邻接顶点的序号int Graph_Matrix ::GetFirstNeighbor( const int v ){if (v = =-1) return-1;for( int i = 0 ; i < graphsize ; i ++ )if( edge[v][i] > 0 && edge[v][i] < MaxWeight)return i ;return-1 ;

第61页：取得顶点

61//取得顶点v1相对于v2的下一个邻接顶点的序号int Graph_Matrix ::GetNextNeighbor( const int v1 , const int v2 ){if (v1 = =-1 || v2= =-1) return-1;for( int i = v2 + 1 ; i < graphsize ; i ++ )if( edge[v1][i] > 0 && edge[v1][i] < MaxWeight)return i ;return-1 ;

第62页：删除顶点Vertex算法思想

删除顶点Vertex算法思想：不仅要从顶点表中删除该顶点，还需要删除该顶点所发出的边以及所有的入边，即在邻接矩阵中删除相应的行和列。

第63页：用邻接表存储的图类

632.用邻接表存储的图类Graph_ListV0V3V2V1V0V1V2V30231123∧012∧03∧03∧

第64页：用邻接表存储的图类（续2）

642.用邻接表存储的图类Graph_List//边结点的结构体struct Edge{friend class Graph_List ;int VerAdj ;

第65页：顶点表中结点的结构体

65//顶点表中结点的结构体struct Vertex{friend class Graph_List;int VerName;//顶点的名称Edge *adjacent;//边链表的头指针}

第66页：采用邻接表存储

66//采用邻接表存储的Graph_List类定义class Graph_List{private:Vertex *Head;

第67页：求序号

67//求序号为v的顶点的第一个邻接顶点的序号int Graph_List:: GetFirstNeighbor( const int v ){if ( v = =-1 ) return-1;Edge *p = Head[v].adjacent ;if (p != NULL)return p→VerAdj ;elsereturn-1;}ADCBABCD0231123∧012∧03∧03∧

第68页：求序号（续2）

68//求序号为v1的顶点相对于序号为v2的顶点的下一个邻接顶点的序号int Graph_List :: GetNextNeighbor( const int v1 , const int v2 ){if ( v1 !=-1 && v2 !=-1 ){ Edge *p = Head[v1].adjacent ;while( p→VerAdj != v2 && p!=NULL )//令p指向v2所在的边结点p = p→link ;if (p = = NULL) return-1;p = p→link ;

第69页：第五章图目录

第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用

第70页：从已给的连通图中某一顶点出发

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让visited[i]为1，防止它被多次访问。

第71页：5.3.1 深度优先遍历

715.3.1深度优先遍历●深度优先遍历又被称为深度优先搜索DFS( Depth FirstSearch )●基本思想:DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

第72页：深度优先搜索

深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例

第73页：递归算法

731.递归算法算法DepthFirstSearch(v,visited)DFSearch1[初始化]PRINT(v).visited[v]←1.p←adjacent(Head[v]).DFSearch2[深度优先遍历图]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THENDepthFirstSearch(VerAdj(p),visited).p←link(p).)▐

第74页：算法DFS_Main

算法DFS_Main(){visited=newint[graphsize];//为辅助数组申请空间for(intk=0;k<graphsize;k++)visited[k]=0;//数组初始化//从序号为0的顶点出发，深度优先遍历图DepthFirstSearch(0,visited[]);delete[]visited;//释放辅助数组空间}

第75页：初始化

DFSearch1[初始化]PRINT(v).visited[v]←1.p←adjacent(Head[v]) .DFSearch2[深度优先遍历图]WHILE p ≠∧DO( IFvisited[VerAdj(p)]≠1 THENDepthFirstSearch (VerAdj(p),visited) .p←link(p) . )▐V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567

第76页：初始化（图）

V1V2V4V3V8V7V6V5V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567

第77页：可以利用堆栈实现深度优先遍历的非递归算法

可以利用堆栈实现深度优先遍历的非递归算法。堆栈中存放已访问结点的未被访问的邻接顶点，每次弹出栈顶元素时，如其未被访问，则访问该顶点，并检查当前顶点的边链表，将其未被访问的邻接顶点入栈，循环进行。2.迭代算法

第78页：首先将所有顶点

首先将所有顶点的visited[]值置为0,初始顶点压入堆栈；①检测堆栈是否为空。若堆栈为空，则迭代结束；否则，从栈顶弹出一个顶点v；②如果v未被访问过，则访问v，将visited[v]值更新为1，然后根据v的邻接顶点表，将v的未被访问的邻接顶点压入栈，执行步骤①。

第79页：首先将所有顶点（图）

A0243156BCDEFG16∧2∧34∧5∧0∧5∧4∧ACGBFED

第80页：算法DFS

算法DFS(Head,v,visited.visited)DFS1[初始化]CREATS(S).FORi=1TOnDOvisited[i]←0.S←v.DFS2[利用堆栈S深度优先遍历图]WHILENOT(ISEMTS(S))DO(v←S.IFvisited[v]=0THEN(PRINT(v).visited[v]←1.p←adjacent(Head[v]).WHILEp≠ DO(IFvisited[VerAdj(p)]=0THENS←VerAdj(p).p←link(p).)))▐

第81页：算法分析图中有n个顶点

算法分析图中有n个顶点，e条边。如果用邻接表表示图，沿顶点的adjacent可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。

第82页：非连通图

非连通图需要多次调用深度优先遍历算法Fori=0ton-1DOvisited[i]←0.Forj=0ton-1DOIFvisited[j]=0THENDepthFirstSearch(v[j],visited)V1V2V

第83页：5.3.2 广度优先遍历

835.3.2广度优先遍历●基本思想：首先访问初始点顶点v0，之后依次访问与v0邻接的全部顶点w1，w2，...，wk。然后，再顺次访问与w1，w2，...，wk邻接的尚未访问的全部顶点，再从这些被访问过的顶点出发，逐个访问与它们邻接的尚未访问过的全部顶点。依此类推，直到连通图中的所有顶点全部访问完为止。

第84页：广度优先搜索BFS

广度优先搜索BFS(BreadthFirstSearch)广度优先搜索的示例广度优先搜索过程广度优先生成树

第85页：广度优先搜索类似于树的层次遍历

广度优先搜索类似于树的层次遍历，是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用一个队列，以便于向下一层访问。与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组visited[]。

第86页：算法BFS

算法BFS(Head,v,visited.visited)BFS1[初始化]CREATQ(Q).FORi=1TOnDOvisited[i]←0.PRINT(v).visited[v]←1.Q←v.BFS2[广度优先遍历]WHILENOT(ISEMTQ(Q))DO(v←Q.p←adjacent(Head[v]).WHILEp≠ DO(IFvisited[VerAdj(p)]=0THEN(Q←VerAdj(p).PRINT(VerAdj(p)).visited[VerAdj(p)]←1.).p←link(p).))▐

第87页：当队列不空时

WHILENOT(ISEMTQ(Q))DO(v←Q.p←adjacent(Head[v]).WHILEp≠ DO(IFvisited[VerAdj(p)]=0THEN(Q←VerAdj(p).PRINT(VerAdj(p)).visited[VerAdj(p)]←1.)p←link(p).))01234567024315670123457612∧04∧306∧517∧27∧27∧36∧4517∧

第88页：算法分析如果使用邻接表

算法分析如果使用邻接表表示图，则循环的总时间代价为d0+d1+…+dn-1=O(e)，其中的di是顶点i的度。总的时间复杂度为O(n+e)。如果使用邻接矩阵，则对于每一个被访问的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。

第89页：第五章图目录

第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用

第90页：5.4 拓扑排序计划

905.4拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。AOV网:在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系，称这样的有向图为AOV网(ActivityOnVertexNetwork)。

第91页：例如，计算机专业学生的学习就是一个工程

例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。

第92页：[例]按拓扑次序

92[例]按拓扑次序安排计算机专业必修课程计算机专业必修课程课程代号课程名称先修课程C0高等数学无C1程序设计基础无C2离散数学C0,C1C3数据结构C2,C4C4程序设计语言C1C5编译技术C3,C4C6操作系统C3,C8C7普通物理C0C8计算机原理C7C0C2C3C5C4C1C7C6C

第93页：AOV网络中

在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边<Vi,Vj>，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。

第94页：拓扑序列

拓扑序列：把AOV网中的所有顶点排成一个线性序列，使每个活动的所有前驱活动都排在该活动的前边。拓扑排序：构造AOV网的拓扑序列的过程被称为拓扑排序。拓扑序列：C0, C1, C2, C4,C3, C5, C7, C8, C6C0C2C3C5C4C1C7C6C

第95页：拓扑排序基本步骤

95●拓扑排序基本步骤：①从网中选择一个入度为0的顶点且输出之。②从网中删除该顶点及其所有出边。③执行①②，直至所有顶点已输出，或网中剩余顶点入度均不为0(说明网中存在回路，无法继续拓扑排序)C0C2C3C5C4C1C7C6C

第96页：回路与拓扑排序任何无回路的AOV网

回路与拓扑排序任何无回路的AOV网，其顶点均可排成拓扑序列(其拓扑序列不一定唯一)；如果能将AOV网的所有顶点都排入一个拓扑序列，则该AOV网中必定无有向环；如果得不到所有顶点的拓扑序列，则说明AOV网中存在有向环(AOV网所代表的工程是不可行的)。存在回路的AOV网，找不到所有顶点的拓扑序列。因此，可以用拓扑排序判断有向图中是否有回路

第97页：假定AOV网用邻接表的形式存储

假定AOV网用邻接表的形式存储。为实现拓扑排序算法，事先需好两项准备工作：建立一个数组count[ ]，count[i]的元素值取对应顶点i的入度；建立一个堆栈，栈中存放入度为0的顶点，每当一个顶点的入度为0，就将其压入栈。拓扑排序算法

第98页：假定AOV网用邻接表的形式存储（图）

98325140002123013425count0243152∧42∧3∧53∧5∧5∧

第99页：用一个堆栈存放入度

用一个堆栈存放入度为0的顶点。虚拟的堆栈－－利用变量top和count数组元素的值来模拟堆栈的压入和弹出。top:“栈顶”位置，初始为-1count[top]：次栈顶元素入栈：count[i] = top; top = i;出栈：j = top; top = count[top];

第100页：算法TopoOrder

算法TopoOrder(n) TOrder1[初始化]FORi=0TOn-1DOcount[i]←0.FORi=0TOn-1DO(p←adjacent(Head[i] ) .WHILEp≠ DO(count[VerAdj(p)]←count[VerAdj(p)]+1.p←link (p). ) )325140002123013425count

第101页：拓扑排序算法

拓扑排序算法：top←-1.//栈顶指针topFORi=0TOn-1DO//将入度为0的顶点入栈IFcount[i] = 0 THEN(count[i]←top.top←i. )top－102123013425count325140

第102页：拓扑排序算法（续2）

102－102123013425counttop1拓扑排序算法：top←-1.//栈顶指针topFORi=0TOn-1DO//将入度为0的顶点入栈IFcount[i] = 0 THEN(count[i]←top.top←i. )325140

第103页：拓扑排序

TOrder2[拓扑排序]FORi=1TOnDOIFtop=-1THEN//若循环体尚未被执行n次，栈顶指针已为-1(PRINT“有回路!”.RETURN.)//说明有回路，终止程序ELSE(j←top.top←count[top].PRINT(j).p←adjacent(Head[j] ) .//扫描j的边链表WHILEp≠ DO(k←VerAdj(p) .count[k]←count[k]-1.//顶点k的入度减1IFcount[k]=0THEN//若入度为0，则k入栈(count[k]←top.top←k.)p←link(p).))▐

第104页：弹出堆栈顶点

j←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)top－12123013425count－102123013425counttop325140

第105页：扫描

1050243152∧42∧3∧53∧5∧5∧－11013013425counttop32540pppj←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)

第106页：弹出堆栈顶点（续2）

1063250－1112013425counttopj←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)

第107页：弹出堆栈顶点（续2）

107－112013425counttop325j←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)

第108页：弹出堆栈顶点（续3）

108－11013425counttop35j←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)

第109页：弹出堆栈顶点（续2）

109－1013425counttop5j←top.top←count[top].PRINT(j).p←adjacent(Head[j]).WHILEp≠ DO(k←VerAdj(p).count[k]←count[k]-1.IFcount[k]=0THEN(count[k]←top.top←k.)//入栈p←link(p).)

第110页：引理5.1

引理5.1设图G=(V,E)是非循环图,V(G)≠Φ,则G中一定存在入度为零的顶点定理5.2设G=(V,E)是非循环图，V(G)={1,2,…,n},e=|E(G)|.则算法TopoOrder是正确的且算法的时间复杂性为O(n+e).

第111页：课后作业

课后作业173：5-1、5-7、5-12、5-13、5-14、5-15、5-16