数据结构中的图

第7章图（Graph）主讲：李耀国数据结构（DataStructure）第七章图图是一种比线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素最多只有一个直接前驱和一个直接后继。在树型结构中，数据元素之间存在明显的层次关系，并且每层的元素可能和下一层的多个元素相邻，但只能和上一层的一个元素相邻。而在图形结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相邻。图是计算机应用过程中对实际问题进行数学抽象和描述的强有力的工具，数据结构中对图的讨论侧重于在计算机中如何表示图以及如何实现图的操作和应用等。第七章图和广义表7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.5.1拓扑排序7.5.2关键路径7.6最短路径7.1图的定义和术语图由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V,E)。图中的顶点即为数据结构中的数据元素，弧的集合E实际上是定义在顶点集合上的一个关系。用有序对v,w表示从v到w的一条弧。弧具有方向性，以带箭头的线段表示，通常称v为弧尾或始点，称w为弧头或终点，此时的图称为有向图。若图中从v到w有一条弧，同时从w到v也有一条弧，则以无序对(v,w)代替这两个有序对v,w和w,v,表示v和w之间的一条边。此时的图在顶点之间不再强调方向性的特征，称为无向图。7.1图的定义和术语图G1是一个有向图，G1=(V1,{A1})。其中:V1={A,C,B,F,D,E,G}A1={A,B,B,C,B,F,B,E,C,E,E,D,D,C,E,B,F,G}ACBFDGE有向图G17.1图的定义和术语图G2是一个无向图，G2=(V2,{E2})。其中：V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,E)}ABCDEF无向图G27.1图的定义和术语在实际应用中，图的弧或边往往与具有一定意义的数相关，称这些数为权(weight)。分别称带权的有向图和无向图为有向网和无向网。123456712345671918212756103311706475806018069584331324430无向网有向网7.1图的定义和术语稀疏图和稠密图假设用n表示图中顶点数目，用e表示边或弧的数目。若不考虑顶点到其自身的弧或边，则对于无向图，边数e的取值范围是0到n(n-1)/2。称具有n(n-1)/2条边的无向图为完全图。对于有向图，弧的数目e的取值范围是0到n(n-1)。称具有n(n-1)条弧的有向图为有向完全图。若enlogn，则称为稀疏图，反之称为稠密图。子图假设有两个图G=(V,{E})和G’=(V’,{E’})，若V’V且E’E，则称G’为G的子图。7.1图的定义和术语度、入度和出度若u-v是图中的一条弧，则称u邻接到v，或v邻接自u。图中所邻接到某顶点v的弧的数目，称为该顶点的入度，记作:ID(v)；反之，从某顶点u出发的弧的数目，称为该顶点的出度，记作:OD(u)。顶点v的入度和出度之和称为该顶点的总度，简称为度，记作:TD(v)。例如图G1中顶点B的入度ID(B)=2，出度OD(B)=3，度TD(B)=5。无向图中顶点的度定义为与该顶点相连的边的数目。一般情况下，如果顶点vi的度记作TD(vi)，则一个含有n个顶点，e条边或弧的图，满足如下关系：niivTDe1)(21ACBFDGE7.1图的定义和术语路径和回路若有向图G中k+1个顶点之间都有弧存在，则这个顶点的序列{v0,v1,…vk}为从顶点v0到顶点vk的一条有向路径，路径中弧的数目定义为路径长度。若序列中的顶点都不相同，则为简单路径。对无向图，相邻顶点之间存在边的k+1个顶点序列构成一条长度为k的无向路径。如若v0和vk是同一个顶点，则是一条由某个顶点出发又回到自身的路径，称这种路径为回路或环。7.1图的定义和术语连通图和连通分量若无向图中任意两个顶点之间都存在一条无向路径，则称该无向图为连通图。对有向图而言，若图中任意两个顶点之间都存在一条有向路径，则称该有向图为强连通图。非连通图中的各个极大连通子图称为该图的连通分量。ABCDEFACBFDGE非强连通图和强连通分量非连通图和连通分量7.1图的定义和术语图的抽象数据类型ADTGraph{数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系R:R={VR}VR={v,w|v,w∈P(v,w),v,w表示从到的弧,谓词P(v,w)定义了弧v,w的意义或信息}基本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestoryGraph(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。more7.1图的定义和术语GetVex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G存在，v是G中的某个顶点。操作结果：对v赋值value。FirstAdjVex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的第一个邻接点，若该顶点在G中无邻接点，则返回空。NextAdjVex(G,v,w)初始条件：图G存在，v是G中的某个顶点，w是v的邻接顶点。操作结果：返回v的(相对于w的)下一个邻接点。若w是v的最后一个邻接点，则返回空。more7.1图的定义和术语InsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w)初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中增添弧v,w，若G是无向的，则还增添对称弧w,v。DeleteArc(&G,v,w)初始条件：图G存在，v和w是G中的两个顶点。操作结果：在图G中删除弧v,w，若G是无向的，则还删除对称弧w,v。more7.1图的定义和术语DFSTraverse(G,v,visit())初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,v,visit())初始条件：图G存在，v是G中的某个顶点，visit是针对顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraph7.2图的存储结构图是一种典型的复杂结构，图中顶点可能同任意一个其他顶点之间存在关系。因此，图没有顺序映象的存储结构。图有两种常用的存储结构。7.2.1图的数组(邻接矩阵)存储表示邻接矩阵是用于描述图中顶点之间的关系(及弧或边的权)的矩阵，假设图中顶点数为n，则邻接矩阵A=(ai,j)m*n定义为：A[i][j]=1若Vi和Vj之间有弧或边存在0Vi和Vj之间没有弧或边存在7.2.1图的数组(邻接矩阵)存储表示0000000100000000010100000100001000001101000000010ACBFDGEABCDEF010110100110000100111011110101000110有向图G1无向图G2G1的邻接矩阵G2的邻接矩阵7.2.1图的数组(邻接矩阵)存储表示一般情况下，图中没有邻接到自身的弧，因此矩阵中主对角线全为零。由于无向图中一条边视为一对弧，则无向图的邻接矩阵必然是对称矩阵。网的邻接矩阵定义中，当vi到vj有弧相邻接时，ai,j的值为该弧上的权值，否则为∞。12345677064758060180695843313244306943755818070443230603164807.2.1图的数组(邻接矩阵)存储表示有向图的邻接矩阵大多为稀疏矩阵，可以采用压缩存储表示。用二维数组表示更为方便，它和顶点信息等其他图的信息一起构成图的一种存储表示constINFINITY_INT_MAX=MAX;//最大值∞设为MAXconstMAX_VERTEX_NUM=20;//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//图类型(有向图、有向网、无向图、无向网)typedefstructArcCell{VRTypeadj;//VRType为顶点的关系类型。对无权图，用1或0表示是否相邻；对带权图则为权值类型InfoType*info;//指向该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//描述顶点的数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧(边)数GraphKindkind;//图的种类标志}MGraph;vexs[0][0].adjvexs[0][0].info……vexs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]arcsvexnumarcnumkind7.2.2图的邻接表存储表示邻接表是图的一种链式存储表示方法，它类似于树的孩子链表。在有向图的邻接表中，从同一个顶点出发的弧链接在同一链表中，邻接表中结点的个数恰好为图中弧的个数。在无向图的邻接表中，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此无向图的邻接表中结点个数是边的两倍。7.2.2图的邻接表存储表示ACBFDGE有向图G1MAX_VERTEX_NUMABCEDFG^……--01234561^3^6^12^4^245^7.2.2图的邻接表存储表示MAX_VERTEX_NUMABCEDF……--012345ABCDEF无向图G22^1024015^345^2^125^124^7.2.2图的邻接表存储表示邻接表定义如下：constMAX_VERTEX_NUM=20;typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//指向该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;算法7.1voidCreateUDG(ALGraph&G){//采用邻接表存储表示，构造无向图G(G.kind=UDG)cinG.vexnumG.arcnumIncinfo;for(i=0;iG.vexnum;++i){//构造表头向量cinG.vertices[i].data;//输入顶点值G.vert