数据结构中的图.ppt

《数据结构中的图.ppt》由会员分享，可在线阅读，更多相关《数据结构中的图.ppt（67页珍藏版）》请在优知文库上搜索。

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

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

3、.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),(E,F),(C,E

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

7、弧的数目。若不考虑顶点到其自身的弧或边，则对于边或弧的数目。若不考虑顶点到其自身的弧或边，则对于无向图，边数无向图，边数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邻接自邻接自u。图中所。图中所邻接

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

9、记作的度记作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), 表示从到的弧表示从到的弧, , 谓词谓词P(v

12、,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 (G,u)n初始条件：图初始条件：图G G存在，存在，

13、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初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点。中的某个顶点。n

14、操作结果：对操作结果：对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是是v v的邻接顶点。的邻接顶点。n操作结果：返回操作结果：返回v v的的

15、( (相对于相对于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 初始条件：图初始条件：图G G存在，存在，v v是是G G中的某个顶点。中的某个顶点。n 操作结果：删除操作结果：

16、删除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存在，存在， 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起深度优先遍历图