数据结构中的图

1、 第第7 7章章 图（图（GraphGraph） 主讲：李耀国主讲：李耀国第七章第七章 图图 图是一种比线性表和树更为复杂的数据结构。在线性图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有表中，数据元素之间仅有线性关系线性关系，每个元素最多只有一，每个元素最多只有一个直接前驱和一个直接后继。在树型结构中，数据元素之个直接前驱和一个直接后继。在树型结构中，数据元素之间存在明显的间存在明显的层次关系层次关系，并且每层的元素可能和下一层的，并且每层的元素可能和下一层的多个元素相邻，但只能和上一层的一个元素相邻。而多个元素相邻，但只能和上一层的一个元素相邻。而在图在图形结构中，结点

2、之间的关系可以是形结构中，结点之间的关系可以是任意任意的，图中的任意两的，图中的任意两个元素之间都可能相邻个元素之间都可能相邻。图是计算机应用过程中对实际问。图是计算机应用过程中对实际问题进行数学抽象和描述的强有力的工具，数据结构中对图题进行数学抽象和描述的强有力的工具，数据结构中对图的讨论侧重于在计算机中的讨论侧重于在计算机中如何表示图如何表示图以及如何实现图的操以及如何实现图的操作和作和应用应用等。等。第七章第七章 图和广义表图和广义表 7.1 7.1 图的定义和术语图的定义和术语 7.2 7.2 图的存储结构图的存储结构 7.3 7.3 图的遍历图的遍历 7.4 7.4 图的连通性问题图

3、的连通性问题 7.5 7.5 有向无环图及其应用有向无环图及其应用 7.5.1 7.5.1 拓扑排序拓扑排序 7.5.2 7.5.2 关键路径关键路径 7.6 7.6 最短路径最短路径7.1 图的定义和术语图的定义和术语图图由一个由一个顶点顶点的有穷非空集合的有穷非空集合V(G)V(G)和一个和一个弧弧的集的集合合E(G)E(G)组成，通常记做组成，通常记做G=(V,E)G=(V,E)。图中的。图中的顶点顶点即为即为数据结构中的数据结构中的数据元素数据元素，弧弧的集合的集合E E实际上是定义实际上是定义在顶点集合上的一个在顶点集合上的一个关系关系。用有序对。用有序对表示从表示从v v到到w w

4、的一条的一条弧弧。弧具有方向性，以带箭头的线段表。弧具有方向性，以带箭头的线段表示，通常称示，通常称v v为为弧尾弧尾或或始点始点，称，称w w为为弧头弧头或或终点终点，此，此时的图称为时的图称为有向图有向图。若图中从。若图中从v v到到w w有一条弧，同时有一条弧，同时从从w w到到v v也有一条弧，则以无序对也有一条弧，则以无序对(v,w)(v,w)代替这两个代替这两个有序对有序对和和,表示表示v v和和w w之间的一条之间的一条边边。此。此时的图在顶点之间不再强调方向性的特征，称为时的图在顶点之间不再强调方向性的特征，称为无无向图向图。7.1 图的定义和术语图的定义和术语图图G1G1是一

5、个有向图，是一个有向图，G1=(V1,A1)G1=(V1,A1)。其中。其中: : V1=A,C,B,F,D,E,G V1=A,C,B,F,D,E,G A1=, A1=, ,ACBFDGE有向图有向图G17.1 图的定义和术语图的定义和术语 图图G2G2是一个无向图，是一个无向图，G2=(V2,E2)G2=(V2,E2)。其中：。其中： V2=A,B,C,D,E,FV2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), E2=(A,B),(A,C),(B,C),(B,E),(B,F),(C,F), (C,D),(E,F),(C,E)(C,D

6、),(E,F),(C,E)ABCDEF无向图无向图G27.1 图的定义和术语图的定义和术语 在实际应用中，图的弧或边往往与具有一定意义在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为的数相关，称这些数为权权(weight)(weight)。分别称带权的有。分别称带权的有向图和无向图为向图和无向图为有向网有向网和和无向网无向网。123456712345671918212756103311706475806018069584331324430无向网无向网有向网有向网7.1 图的定义和术语图的定义和术语 稀疏图和稠密图稀疏图和稠密图 假设用假设用n n表示图中顶点数目，用表示图中顶点数

7、目，用e e表示表示边或弧的数目。若不考虑顶点到其自身的弧或边，则对于边或弧的数目。若不考虑顶点到其自身的弧或边，则对于无向图，边数无向图，边数e e的取值范围是的取值范围是0 0到到n(n-1)/2n(n-1)/2。称具有。称具有n(n-n(n-1)/21)/2条边的无向图为条边的无向图为完全图完全图。对于有向图，弧的数目。对于有向图，弧的数目e e的的取值范围是取值范围是0 0到到n(n-1)n(n-1)。称具有。称具有n(n-1)n(n-1)条弧的有向图为条弧的有向图为有有向完全图向完全图。若。若enlognev是图中的一条弧，则称是图中的一条弧，则称u邻接邻接到到v，或，或v邻接自邻接

8、自u。图中所。图中所邻接到邻接到某顶点某顶点v的弧的数目，的弧的数目，称为该顶点的称为该顶点的入度入度，记作，记作:ID(v)；反之，从某顶点；反之，从某顶点u出出发发的弧的数目，称为该顶点的的弧的数目，称为该顶点的出度出度，记作，记作:OD(u)。顶。顶点点v的入度和出度之的入度和出度之和和称为该顶点的称为该顶点的总度总度，简称为，简称为度度，记作记作: TD(v)。例如图。例如图G1中顶点中顶点B的入度的入度ID(B)=2，出，出度度OD(B)=3，度，度TD(B)=5。 无向图中顶点的度定义为与该顶点相连的边的数目。无向图中顶点的度定义为与该顶点相连的边的数目。 一般情况下，如果顶点一般

9、情况下，如果顶点vi的度记作的度记作TD(vi)，则一个含有，则一个含有n个顶点，个顶点，e条边或弧的图，满足如下关系：条边或弧的图，满足如下关系：niivTDe1)(21ACBFDGE7.1 图的定义和术语图的定义和术语 路径和回路路径和回路 若有向图若有向图G中中k+1个顶点之间都个顶点之间都有弧存在，则这个顶点的序列有弧存在，则这个顶点的序列v0,v1,vk为为从顶点从顶点v0到顶点到顶点vk的一条的一条有向路径有向路径，路径中，路径中弧的数目定义为弧的数目定义为路径长度路径长度。若序列中的顶点。若序列中的顶点都不相同，则为都不相同，则为简单路径简单路径。对无向图，相邻。对无向图，相邻顶

10、点之间存在边的顶点之间存在边的k+1个顶点序列构成一条个顶点序列构成一条长度为长度为k的的无向路径无向路径。如若。如若v0和和vk是同一个顶是同一个顶点，则是一条由某个顶点出发又回到自身的点，则是一条由某个顶点出发又回到自身的路径，称这种路径为路径，称这种路径为回路回路或或环环。7.1 图的定义和术语图的定义和术语 连通图和连通分量连通图和连通分量 若无向图中任意两个若无向图中任意两个顶点之间都存在一条无向路径，则称该无顶点之间都存在一条无向路径，则称该无向图为向图为连通图连通图。对有向图而言，若图中任。对有向图而言，若图中任意两个顶点之间都存在一条有向路径，则意两个顶点之间都存在一条有向路径

11、，则称该有向图为称该有向图为强连通图强连通图。非连通图中的各。非连通图中的各个极大连通子图称为该图的个极大连通子图称为该图的连通分量连通分量。ABCDEFACBFDGE非强连通图和强连通分量非强连通图和强连通分量非连通图和连通分量非连通图和连通分量7.1 图的定义和术语图的定义和术语 图的抽象数据类型图的抽象数据类型ADT Graph ADT Graph 数据对象数据对象V:VV:V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。 数据关系数据关系R:R=VRR:R=VR VR=|v,wP(v,w), VR=|v,wP(v,w), 表示从到的弧表示从到的

12、弧, , 谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作：基本操作： CreateGraph (&G,V,VR)CreateGraph (&G,V,VR)n初始条件：初始条件：V V是图的顶点集，是图的顶点集，VRVR是图中弧的集合。是图中弧的集合。n操作结果：按操作结果：按V V和和VRVR的定义构造图的定义构造图G G。 DestoryGraph (&G)DestoryGraph (&G)n初始条件：图初始条件：图G G存在。存在。n操作结果：销毁图操作结果：销毁图G G。 LocateVex (G,u)LocateVex

13、 (G,u)n初始条件：图初始条件：图G G存在，存在，u u和和G G中顶点有相同特征。中顶点有相同特征。n操作结果：若操作结果：若G G中存在顶点中存在顶点u u，则返回该顶点在图中的位置；否则返回其他信息。，则返回该顶点在图中的位置；否则返回其他信息。more7.1 图的定义和术语图的定义和术语 GetVex (G,v)GetVex (G,v)n初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点。中的某个顶点。n操作结果：返回操作结果：返回v v的值。的值。 PutVex (&G,v,value)PutVex (&G,v,value)n初始条件：图初始

14、条件：图G G存在，存在，v v是是G G中的某个顶点。中的某个顶点。n操作结果：对操作结果：对v v赋值赋值valuevalue。 FirstAdjVex (G,v)FirstAdjVex (G,v)n初始条件：图初始条件：图G G存在，存在， v v是是G G中的某个顶点。中的某个顶点。n操作结果：返回操作结果：返回v v的第一个邻接点，若该顶点在的第一个邻接点，若该顶点在G G中无邻接点，则返中无邻接点，则返回空。回空。 NextAdjVex (G,v,w)NextAdjVex (G,v,w)n初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点，中的某个顶点，w w是

15、是v v的邻接顶点。的邻接顶点。n操作结果：返回操作结果：返回v v的的( (相对于相对于w w的的) )下一个邻接点。若下一个邻接点。若w w是是v v的最后一个的最后一个邻接点，则返回空。邻接点，则返回空。more7.1 图的定义和术语图的定义和术语 InsertVex (&G,v) InsertVex (&G,v)n 初始条件：图初始条件：图G G存在，存在，v v和图中顶点有相同特征。和图中顶点有相同特征。n 操作结果：在图操作结果：在图G G中增添新顶点中增添新顶点v v。 DeleteVex (&G,v)DeleteVex (&G,v)n 初始条件：

16、图初始条件：图G G存在，存在，v v是是G G中的某个顶点。中的某个顶点。n 操作结果：删除操作结果：删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。 InsertArc (&G,v,w)InsertArc (&G,v,w)n 初始条件：图初始条件：图G G存在，存在， v v和和w w是是G G中的两个顶点。中的两个顶点。n 操作结果：在图操作结果：在图G G中增添弧中增添弧，若，若G G是无向的，则还是无向的，则还增添对称弧增添对称弧。 DeleteArc (&G,v,w)DeleteArc (&G,v,w)n 初始条件：图初始条件：图G G存在，

17、存在， v v和和w w是是G G中的两个顶点。中的两个顶点。n 操作结果：在图操作结果：在图G G中删除弧中删除弧，若，若G G是无向的，则还是无向的，则还删除对称弧删除对称弧。more7.1 图的定义和术语图的定义和术语 DFSTraverse (G,v,visit() DFSTraverse (G,v,visit()n 初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点，中的某个顶点，visitvisit是是针对顶点的应用函数。针对顶点的应用函数。n 操作结果：从顶点操作结果：从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个，并对每个顶点调用函数顶点调用函

18、数visitvisit一次且仅一次。一旦一次且仅一次。一旦visit()visit()失失败，则操作失败。败，则操作失败。 BFSTraverse (G,v,visit() BFSTraverse (G,v,visit() n 初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点，中的某个顶点，visitvisit是是针对顶点的应用函数。针对顶点的应用函数。n 操作结果：从顶点操作结果：从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个，并对每个顶点调用函数顶点调用函数visitvisit一次且仅一次。一旦一次且仅一次。一旦visit()visit()失失败，则操作

19、失败。败，则操作失败。ADT GraphADT Graph7.2 图的存储结构图的存储结构图是一种典型的复杂结构，图中顶点可能同任意一图是一种典型的复杂结构，图中顶点可能同任意一个其他顶点之间存在关系。因此，图没有顺序映象个其他顶点之间存在关系。因此，图没有顺序映象的存储结构。图有两种常用的存储结构。的存储结构。图有两种常用的存储结构。7.2.1 7.2.1 图的数组图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示 邻接矩阵是用于描述图中顶点之间的关系邻接矩阵是用于描述图中顶点之间的关系( (及弧或边的权及弧或边的权) )的矩阵，假设图中顶点数为的矩阵，假设图中顶点数为n n，则邻接矩阵，

20、则邻接矩阵A=(aA=(ai,ji,j) )m m* *n n定义定义为：为：nAij=1 若若Vi和和Vj之间有弧或边存在之间有弧或边存在0 Vi和和Vj之间没有弧或边存在之间没有弧或边存在7.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 0000000100000000010100000100001000001101000000010ACBFDGEABCDEF 010110100110000100111011110101000110有向图有向图G1无向图无向图G2G1的邻接矩阵的邻接矩阵G2的邻接矩阵的邻接矩阵7.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示

21、一般情况下，图中没有邻接到自身的弧，因此矩阵中主对角一般情况下，图中没有邻接到自身的弧，因此矩阵中主对角线全为零。由于无向图中一条边视为一对弧，则无向图的邻线全为零。由于无向图中一条边视为一对弧，则无向图的邻接矩阵必然是对称矩阵。接矩阵必然是对称矩阵。网的邻接矩阵定义中，当网的邻接矩阵定义中，当v vi i到到v vj j有弧相邻接时，有弧相邻接时，a ai,ji,j的值为该的值为该弧上的权值，否则为弧上的权值，否则为。1234567706475806018069584331324430 6943755818070443230603164807.2.1 图的数组图的数组(邻接矩阵邻接矩阵)存储

22、表示存储表示有向图的邻接矩阵大多为有向图的邻接矩阵大多为稀疏矩阵稀疏矩阵，可以采用，可以采用压缩压缩存储表示。用存储表示。用二维数组二维数组表示更为方便，它和顶点信息等其他图的信息一起构成图的一种存储表示表示更为方便，它和顶点信息等其他图的信息一起构成图的一种存储表示const INFINITY_INT_MAX=MAX; /最大值最大值设为设为MAXconst MAX_VERTEX_NUM=20; /最大顶点个数最大顶点个数typedef enum DG,DN,AG,ANGraphKind; /图类型图类型(有向图、有向网、无向图、有向图、有向网、无向图、无向网无向网)typedef stru

23、ct ArcCellVRType adj; / VRType为顶点的关系类型。对无权图，用为顶点的关系类型。对无权图，用1或或0表示是否相邻；表示是否相邻；对带权图则为权值类型对带权图则为权值类型InfoType *info; /指向该弧相关信息的指针指向该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; / 描述顶点的数组描述顶点的数组AdjMatrix arcs; / 邻接矩阵邻接矩阵int vexnum,arcnum; / 图的当前顶点数和

24、弧图的当前顶点数和弧(边边)数数GraphKind kind; / 图的种类标志图的种类标志MGraph;vexsvexsMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_MAX_VERTEX_NUMVERTEX_NUM arcsarcsvexnumvexnumarcnumarcnumkindkind7.2.2图的邻接表存储表示图的邻接表存储表示 邻接表邻接表是图的一种链式存储表示方法，是图的一种链式存储表示方法，它类似于树的孩子链表。在有向图的它类似于树的孩子链表。在有向图的邻接表中，从同一个顶

25、点出发的弧链邻接表中，从同一个顶点出发的弧链接在同一链表中，接在同一链表中，邻接表中结点的个邻接表中结点的个数恰好为图中弧的个数数恰好为图中弧的个数。在无向图的。在无向图的邻接表中，同一条边有两个结点，分邻接表中，同一条边有两个结点，分别出现在和它相关的两个顶点的链表别出现在和它相关的两个顶点的链表中，因此中，因此无向图的邻接表中结点个数无向图的邻接表中结点个数是边的是边的两两倍倍。7.2.2图的邻接表存储表示图的邻接表存储表示ACBFDGE有向图有向图G1MAX_VERTEX_NUMABCEDFG - -01234561361242457.2.2图的邻接表存储表示图的邻接表存储表示MAX_V

26、ERTEX_NUMABCEDF - -012345ABCDEF无向图无向图G22 1024015 345 2 125 124 7.2.2图的邻接表存储表示图的邻接表存储表示 邻接表定义如下：邻接表定义如下：const MAX_VERTEX_NUM=20;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针指向下一条弧的指针InfoType *info;/指向该弧相关信息的指针指向该弧相关信息的指针ArcNode;typedef struct VNodeVertex

27、Type data;/顶点信息顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /图的当前顶点数和弧数图的当前顶点数和弧数int kind; /图的种类标志图的种类标志ALGraph;算法算法7.1void CreateUDG (ALGraph &G) /采用邻接表存储表示，构造无向图采用邻接表存储表示，构造无向图G(G.kind=UDG) cinG.vexnumG.arcnumInc

28、info; for(i=0; iG.verticesi.data;/输入顶点值输入顶点值 G.verticesi.firstarc=NULL; /初始化链表头指针为空初始化链表头指针为空 /for for(k=0; kv1v2;/输入一条弧的始点和终点输入一条弧的始点和终点 i=LocateVex(G,v1); j=LocateVex(G,v2); /确定确定v1和和v2在在G中的位置，即顶点在中的位置，即顶点在G.Vertices中的序号中的序号 pi=new ArcNode; pi-adjvex=j; /对弧结点赋邻接点对弧结点赋邻接点“位置位置”信息信息 pi-nextarc=G.ver

29、ticesi.firstarc; G.verticesi.firstarc=pi; /插入链表插入链表G.verticesi pj=new ArcNode; pj-adjvex=i; /对弧结点赋邻接点对弧结点赋邻接点“位置位置”信信息息 pj-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=pj; /插入链表插入链表G.verticesj if (IncInfo)/若弧含有相关信息，则输入若弧含有相关信息，则输入cinpj-info; pi-info=pj-info; /for /CreateUDG7.3 图的遍历图的遍历 与二叉树和树的

30、遍历类似，图结构也有遍历操作，即从某个与二叉树和树的遍历类似，图结构也有遍历操作，即从某个顶点出发，沿着某条路径对图中其余顶点进行访问，且使每顶点出发，沿着某条路径对图中其余顶点进行访问，且使每一个顶点只被访问一次。但图的遍历要比树的遍历更复杂，一个顶点只被访问一次。但图的遍历要比树的遍历更复杂，因为图中和同一顶点有弧或边相通的顶点之间可能也有弧或因为图中和同一顶点有弧或边相通的顶点之间可能也有弧或边，那么在访问了某个顶点之后，可能沿着某条回路又回到边，那么在访问了某个顶点之后，可能沿着某条回路又回到了该顶点。为了避免同一顶点被重复访问，则在遍历过程中，了该顶点。为了避免同一顶点被重复访问，则

31、在遍历过程中，必须为已经访问过的顶点加上标识，以便再次途径这样的顶必须为已经访问过的顶点加上标识，以便再次途径这样的顶点时不再重复访问。为此，需附设一维数组点时不再重复访问。为此，需附设一维数组visited0.n-visited0.n-11，令其每个分量对应图中一个顶点，各分量的初值均设为，令其每个分量对应图中一个顶点，各分量的初值均设为FALSEFALSE或或0 0，一旦访问了某个顶点，便将，一旦访问了某个顶点，便将visitedvisited中相应分量中相应分量的值置为的值置为TRUETRUE或被访问时的序号。或被访问时的序号。 通常，对图进行遍历可有两种搜索路径：通常，对图进行遍历可有

32、两种搜索路径：深度优先搜索深度优先搜索和和广广度优先搜索度优先搜索。7.3.1 深度优先搜索遍历图深度优先搜索遍历图 深度优先搜索遍历深度优先搜索遍历类似于树的类似于树的先根先根遍历，可遍历，可以看成是先根遍历的推广。以看成是先根遍历的推广。 假设初始状态是图中所有顶点均未被访问，假设初始状态是图中所有顶点均未被访问，则从某个顶点则从某个顶点v v出发，首先访问该顶点，然出发，首先访问该顶点，然后依次从它的各个后依次从它的各个未被访问未被访问的邻接点出发的邻接点出发深深度优先搜索度优先搜索遍历图，直至图中所有和遍历图，直至图中所有和v v有路有路径相通的顶点都被访问到，若此时尚有其他径相通的顶

33、点都被访问到，若此时尚有其他顶点未被访问到，则另选一个未被访问的顶顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。是一个递归的过程。7.3.1 深度优先搜索遍历图深度优先搜索遍历图 例如，从例如，从v v3 3出发对下图进行深度优先搜索，首先访问顶点出发对下图进行深度优先搜索，首先访问顶点v v3 3，然后从，然后从v v3 3的邻接顶点的邻接顶点v v2 2出发进行深度优先搜索，先后出发进行深度优先搜索，先后访问访问v v4 4、v

34、v9 9和和v v1 1，由于，由于v v3 3的第二个邻接顶点的第二个邻接顶点v v1 1已经被访问已经被访问过，则不再从过，则不再从v v1 1出发进行搜索，而出发进行搜索，而v v3 3的下一个邻接点的下一个邻接点v v6 6未未被访问，则再从被访问，则再从v v6 6出发进行搜索。出发进行搜索。124987563搜索过程中访问顶点的次序为：搜索过程中访问顶点的次序为：v3- v2- v4- v9- v1- v6- v5- v8- v7 7.3.1 深度优先搜索遍历图深度优先搜索遍历图算法算法7.27.2 Boolean visitMAX;Boolean visitMAX;void DF

35、STraverse(Graph G,Status (void DFSTraverse(Graph G,Status (* *Visit)(int v) Visit)(int v) VisitFunc=Visit; VisitFunc=Visit; for(v=0;vG.vexnum;v+) visitv=False; for(v=0;vG.vexnum;v+) visitv=False; for(v=0;vG.vexnum;v+) if(!visitv) DFS (G, v); for(v=0;vnextarc;) for(p=G.verticesv.firstarc;p;p=p-nextar

36、c;) w=p-adjvex; w=p-adjvex; if(!visitedw) if(!visitedw) DFS(G,W); DFS(G,W); /对对v v未访问过的邻接顶点未访问过的邻接顶点w w递归调用递归调用DFSDFS /for/for /DFS/DFS7.3.1深度优先搜索遍历图深度优先搜索遍历图查找的顺序为：查找的顺序为：1 1、2 2、4 4、8 8、5 5、6 6、3 3、7 72 21 13 34 45 56 67 78 8121 1241248124851248612483612480 00 00 00 00 00 00 00 01 12 23 34 45 56 6

37、7 78 81 11 11 11 11 11 11 11 11 12 24 48 85 56 63 37 761248371243861248612481241217.3.2 广度优先搜索遍历图广度优先搜索遍历图 广度优先搜索广度优先搜索的基本思想是：从图中某顶点的基本思想是：从图中某顶点v v出发，出发，在访问了在访问了v v之后依次访问之后依次访问v v的各个未曾访问过的邻接点，然的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点先被访问的顶点的邻接点先于后被访问

38、的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以遍历图的过程是以v v为起点，由近至远，依次访问和为起点，由近至远，依次访问和v v有路有路径相通且路径长度为径相通且路径长度为1,2.1,2.的顶点。的顶点。7.3.2

39、 广度优先搜索遍历图广度优先搜索遍历图例如，从例如，从v3v3开始对下图进行广度优先搜索遍历的过程为：首先访问开始对下图进行广度优先搜索遍历的过程为：首先访问v3v3和和v3v3的邻接点的邻接点v2v2、v1v1和和v6v6，然后依次访问，然后依次访问v2v2的邻接点的邻接点v4v4和和v6v6的邻的邻接点接点v5v5，接着访问，接着访问v4v4的邻接点的邻接点v9v9，最后访问，最后访问v5v5的邻接点的邻接点v8v8和和v7v7。由。由于这些顶点的邻接点都已经被访问，并且图中所有顶点都已被访问于这些顶点的邻接点都已经被访问，并且图中所有顶点都已被访问到，广度优先遍历至此结束。到，广度优先遍

40、历至此结束。124987563一层一层二层二层三层三层访问序列为：访问序列为： v3- v2- v1- v6- v4- v5- v9- v8- v7 3216459877.3.2 广度优先搜索遍历图广度优先搜索遍历图 可见，图的广度优先搜索过程类可见，图的广度优先搜索过程类似于树的层次遍历。和深度优先搜索类似于树的层次遍历。和深度优先搜索类似，在遍历的过程中也需要借助于访问似，在遍历的过程中也需要借助于访问标志数组标志数组visitedvisited。并且为了实现按照顶。并且为了实现按照顶点被访问的先后次序查询它们的邻接点，点被访问的先后次序查询它们的邻接点，需附设一个队列依访问次序存储已被访

41、需附设一个队列依访问次序存储已被访问的顶点。对以邻接矩阵表示方法存储问的顶点。对以邻接矩阵表示方法存储的图进行广度优先遍历的算法如的图进行广度优先遍历的算法如7.57.5所示。所示。7.3.2 广度优先搜索遍历图广度优先搜索遍历图算法算法7.57.5void BFSTraverse(MGraph G)void BFSTraverse(MGraph G) bool visitedG.vexnum; bool visitedG.vexnum; /附设访问标志数组附设访问标志数组 SqQueue Q; SqQueue Q; /附设循环队列附设循环队列Q Q for(v=0;vG.vexnum;+v)

42、 visitedv=FALSE; for(v=0;vG.vexnum;+v) visitedv=FALSE; InitQueve(Q,G.vexnum); InitQueve(Q,G.vexnum); for(v=0;vG.vexnum;+v) for(v=0;vG.vexnum;+v) if(!visitedv) if(!visitedv) visitedv=TRUE;VisitFunc(G.vexv); visitedv=TRUE;VisitFunc(G.vexv); /访问第访问第v v个顶点个顶点 EnQueue_Sq(Q,v); EnQueue_Sq(Q,v); /v/v入队列入队列

43、 while(!QueueEmpty_Sq(Q)while(!QueueEmpty_Sq(Q) DeQueue_Sq(Q,u); DeQueue_Sq(Q,u); /队头元素出队并置为队头元素出队并置为u u for(w=0;wG.vexnum;w+) for(w=0;wG.vexnum;w+) if(G.arcsu,w.adj & !visitedw) if(G.arcsu,w.adj & !visitedw) visitedw=TRUE; VisitFunc(w); visitedw=TRUE; VisitFunc(w); /访问图中第访问图中第w w个顶点个顶点 EnQu

44、eue_Sq(Q,w); EnQueue_Sq(Q,w); /当前访问的顶点当前访问的顶点w w入队列入队列Q Q /if/if /while/while /if/if /BFSTraverse/BFSTraverse7.3.2 广度优先搜索遍历图广度优先搜索遍历图 从以上几个算法中可以看出，遍历图的过程从以上几个算法中可以看出，遍历图的过程实质上是通过边或弧找邻接点的过程，其消实质上是通过边或弧找邻接点的过程，其消耗时间取决于所采用的存储结构。因此若采耗时间取决于所采用的存储结构。因此若采用同样的存储结构，广度优先遍历的时间复用同样的存储结构，广度优先遍历的时间复杂度和深度优先搜索相同。由于

45、算法杂度和深度优先搜索相同。由于算法7.57.5中中的存储结构为邻接矩阵，因此算法的存储结构为邻接矩阵，因此算法7.57.5的时的时间复杂度为间复杂度为O(nO(n2 2) )。 图遍历是图的基本操作，也是一些图的应用图遍历是图的基本操作，也是一些图的应用问题求解算法的基础，以此为框架可以派生问题求解算法的基础，以此为框架可以派生出许多应用算法。出许多应用算法。7.4 图的连通性问题图的连通性问题 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树 7.4.2 有向图的强连通分量有向图的强连通分量 7.4.3 连通网的最小生成树连通网的最小生成树 7.4.1 无向图的连通分量和生成树

46、无向图的连通分量和生成树 对于连通图从任一顶点出发进行深度（广度）对于连通图从任一顶点出发进行深度（广度）优先遍历，即可访问到图的所有顶点；对于非连通优先遍历，即可访问到图的所有顶点；对于非连通图需要从多个顶点出发进行遍历。图需要从多个顶点出发进行遍历。(a) 非连通图非连通图(b) 非连通图的两个极大连通分量非连通图的两个极大连通分量ABCDEFACDBEF 7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树 设连通图设连通图G边的集合为边的集合为E(G)，将，将E(G)分为两个集合分为两个集合T(G)和和B(G)，T(G)为遍历图过程中经历的边的集合，为遍历图过程中经历的边的集合

47、， B(G)为为剩余的边。剩余的边。T(G)和和G中所有顶点一起构成连通图中所有顶点一起构成连通图G的极大连的极大连通子图，是连通图的生成树。如果遍历采用深度优先搜索，通子图，是连通图的生成树。如果遍历采用深度优先搜索，则得到的则得到的深度优先生成树深度优先生成树；如果遍历采用广度优先搜索，则；如果遍历采用广度优先搜索，则得到的得到的广度优先生成树广度优先生成树。而非连通图只有生成树林。而非连通图只有生成树林。(a) 连通图连通图1 12 23 34 45 56 67 78 8（b）深度优先生成树）深度优先生成树1 12 24 48 85 56 67 73 3(c)广度优先生成树广度优先生成树

48、7 76 65 54 48 82 23 31 1 7.4.2 有向图的强连通分量有向图的强连通分量(a) 非强连通图非强连通图(b) 非强连通图两个强连通分量非强连通图两个强连通分量 在有向图在有向图G中，如果对于每一对中，如果对于每一对vi,vjV，vi,vj ，从从vi到到vj和从和从vj到到vi都存在路径，则都存在路径，则G是强连通图。是强连通图。有向图中的最大连通子图称作有向图的强连通分量。有向图中的最大连通子图称作有向图的强连通分量。ACBFDGECBDEAF7.4.3 连通网的最小生成树连通网的最小生成树 在一个含有在一个含有n n个顶点的连通图中，必能从中选出个顶点的连通图中，必

49、能从中选出n-1n-1条边条边构成一个极小连通子图，它含有图中全部构成一个极小连通子图，它含有图中全部n n个顶点，但只有足个顶点，但只有足以构成一棵树的以构成一棵树的n-1n-1条边，称这棵树为连通图的条边，称这棵树为连通图的生成树生成树。例如，。例如，对下图对下图(a)(a)进行深度优先搜索遍历过程中经过的边和全部顶点进行深度优先搜索遍历过程中经过的边和全部顶点构成的极小连通子图构成的极小连通子图(b)(b)即为即为(a)(a)的一棵生成树。的一棵生成树。124987563124987563(a)(b)7.4 连通网的最小生成树连通网的最小生成树 在含有在含有n n个顶点的连通网中选择个顶

50、点的连通网中选择n-1n-1条边，构成一棵极小连通子图，条边，构成一棵极小连通子图，并使该连通子图中并使该连通子图中n-1n-1条边上权值之条边上权值之和达到最小，则称其为和达到最小，则称其为连通网的最连通网的最小生成树小生成树。例如，对于如右图所示。例如，对于如右图所示的连通网可以有多棵权值总和不相的连通网可以有多棵权值总和不相同的生成树。同的生成树。abcdefg1216431489106527abcdefg1639627abcdefg1243827abcdefg1216414810(a)权值总和为权值总和为43(b)权值总和为权值总和为36(a)权值总和为权值总和为64权值序列：权值序列

51、：2 3 4 5 6 7 8 9 10 12 14 167.4 连通网的最小生成树连通网的最小生成树构造连通网的最小生成树的算法主要有两种。构造连通网的最小生成树的算法主要有两种。1.1.克鲁斯卡尔克鲁斯卡尔(Kruskal)(Kruskal)算法算法基本思想：按照权值从小到大的顺序选择基本思想：按照权值从小到大的顺序选择n-1n-1条边，并保证这条边，并保证这n-1n-1条边不构条边不构成回路。成回路。具体做法：首先构造一个只含具体做法：首先构造一个只含n n个顶点的森林，然后依权值从小到大从连通个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成

52、一棵树网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。为止。abcdefg1216431489106527abcdefg1243827(c,e)产生回路产生回路(c,f)产生回路产生回路(f,g)产生回路产生回路(b,c)产生回路产生回路已选出已选出n-1条边条边7.4 连通网的最小生成树连通网的最小生成树2.2.普里姆普里姆(Prim)(Prim)算法算法 假设假设G=(V,E)G=(V,E)为一网，其中为一网，其中V V为网中所有顶为网中所有顶点的集合，点的集合，E E为网中所有带权边的集合。设置两为网中所有带权边的集合。设置两个新的集合个新的集合U U和和T T，其

53、中，其中U U用于存放用于存放G G的最小生成树的最小生成树中的顶点，中的顶点，T T存放存放G G的最小生成树中的边。令的最小生成树中的边。令U U的的初值为初值为U=uU=u0 0 ( (假设从顶点假设从顶点u u0 0出发构造最小生成出发构造最小生成树树) )，令，令T T的初值为空，的初值为空，T=T=。 普里姆算法的思想是：从所有普里姆算法的思想是：从所有u?Uu?U，v?V-Uv?V-U的边中选取权值最小的边的边中选取权值最小的边(u, v)(u, v)，将顶点，将顶点v v加入加入集合集合U U中，将边中，将边(u, v)(u, v)加入集合加入集合T T中，如此不断重中，如此不

54、断重复，直到复，直到U=VU=V为止，最小生成树构造完毕，这时为止，最小生成树构造完毕，这时集合集合T T中包含了最小生成树中的所有边。中包含了最小生成树中的所有边。7.4 连通网的最小生成树连通网的最小生成树例如，利用例如，利用PrimPrim算法对下图从顶点算法对下图从顶点a a开始构造最小生开始构造最小生成树。成树。abcdefg1216431489106527abcdefgU:aT:(a,b):12(a,f):16(a,g):1412U: a, b T: (a,b) (a,f):16(a,g):14(b,c):10(b,f):77U: a, b, f T: (a,b) , (b,f)

55、(a,g):14(b,c):10(f,c):6(f,e):2(f,g):92U: a, b, e, f T: (a,b) , (b,f) , (f,e) (a,g):14(b,c):10(e,c):5(e,d):4(e,g):8(f,c):6(f,g):94U: a, b, d, e, f T: (a,b) , (b,f) , (f,e) , (e,d) (a,g):14(e,g):8(f,g):9(b,c):10(d,c):3(e,c):5(f,c):63U: a, b, c, d, e, f T: (a,b) , (b,f) , (f,e) , (e,d) , (d,c) (a,g):14

56、(e,g):8(f,g):98U: a, b, c, d, e, f, g T: (a,b) , (b,f) , (f,e) , (e,d) , (d,c) , (e,g)此时，所有顶点都已加入集合此时，所有顶点都已加入集合U，即，即UV，最小生成树构造完毕。，最小生成树构造完毕。7.4 连通网的最小生成树连通网的最小生成树比较以上两种算法可见：比较以上两种算法可见： KurskalKurskal算法主要对边进行操作，又称为算法主要对边进行操作，又称为“加加边法边法”，其时间复杂度为，其时间复杂度为O(e)O(e)。这种方法比。这种方法比较适用于稀疏图。较适用于稀疏图。 PrimPrim算法主

57、要对顶点进行操作，又称为算法主要对顶点进行操作，又称为“加加点法点法”，其时间复杂度为，其时间复杂度为O(nO(n2 2) )。比较适用于。比较适用于稠密图。稠密图。7.5 有向无环图及其应用有向无环图及其应用 一个无环的有向图称为一个无环的有向图称为有向无环图有向无环图（directed acycline graphdirected acycline graph），简），简称称DAGDAG。abced 有向无环图是描述一项系统或工程的有向无环图是描述一项系统或工程的进行过程进行过程的有效工具，常用来判断工的有效工具，常用来判断工程能否顺利进行及估算完成时间。程能否顺利进行及估算完成时间。7.

58、5.1 拓扑排序拓扑排序 有向无环图有向无环图在工程计划和管理方面有在工程计划和管理方面有着广泛的应用。一项工程往往可以分解为着广泛的应用。一项工程往往可以分解为一些具有相对独立性的子工程，称这些子一些具有相对独立性的子工程，称这些子工程为工程为活动活动。子工程之间在进行的时间上。子工程之间在进行的时间上有着一定的相互制约关系。可以用有向图有着一定的相互制约关系。可以用有向图表示子工程及其相互制约关系，其中以表示子工程及其相互制约关系，其中以顶顶点点表示活动表示活动，弧弧表示活动之间的表示活动之间的优先制约优先制约关系关系，称这种有向图为，称这种有向图为活动在顶点上活动在顶点上的网的网络，简称

59、络，简称活动顶点网络活动顶点网络(Activity On (Activity On Vertex Network)Vertex Network)，或，或AOVAOV网网。7.5.1 拓扑排序拓扑排序什么是拓扑排序？什么是拓扑排序？若集合若集合X X上的关系上的关系R R是自反的、反对称的和传递的，是自反的、反对称的和传递的，则称则称R R是集合是集合X X上的偏序关系。上的偏序关系。设设R R是集合是集合X X上的偏序，如果对每个上的偏序，如果对每个x,yXx,yX必有必有xRyxRy或或yRxyRx，则称，则称R R是集合是集合X X上的全序关系。上的全序关系。由某个集合上的一个偏序得到该集

60、合上的一个全序，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。这个操作称为拓扑排序。v2v1v4v3v2v1v4v37.5.1 拓扑排序拓扑排序例如，在课程计划中，每门课程的学习就是一项活动，一门课程可能以例如，在课程计划中，每门课程的学习就是一项活动，一门课程可能以其他某几门课程为先修基础，而它本身又可能是另一些课程的先修基础，其他某几门课程为先修基础，而它本身又可能是另一些课程的先修基础，各课程之间的先修关系可用活动顶点网络表示。各课程之间的先修关系可用活动顶点网络表示。C2C1C9C3C11C4C6C12C8C7C5C13C10课程号课程号课程名课程名先修课先修课C C1 1C C语言程序设计语言程序设计无无C C2 2计算机导论计算机导论无无C C3 3数据结构数据结构C C1 1 ，