第七章 图 数据结构

￡7.1图的定义和术语（1）形式化定义Graph=(V,R)V={x|x∈dataobject}//顶点的有穷非空集合R={VR}VR={v,w|P(v,w)∩(v,w∈V)}//两个顶点之间的关系集合（2）图形表示图7.1图的示例(b)无向图G2G1V1V2V3V4(a)有向图G1图由结点及边(弧)组成,与树的主要区别在于图可以有回路V3V4V5V1V2G2(a)有向图G1G1＝(V1,{A1})其中：V1={v1,v2,v3,v4}A1={v1,v2,v1,v3,v3,v4,v4,v1}(b)无向图G2G2＝(V2,{E2})其中：V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}（3）相关术语顶点（Vertex）：图中的数据元素。弧（Arc）：若v,w∈VR，则v,w表示从v到w的一条弧。弧尾（Tail）或初始点（Initialnode）：弧v,w的一个顶点v。弧头（Head）或终端点（Terminalnode）：弧v,w的一个顶点w。有向图（Digraph）：由弧和顶点组成。边（Edge）：若v,w∈VR必有w,v∈VR，即VR是对称的，则以无序对(v,w)代替这两个有序对，表示v和w之间的一条边。无向图（Undigraph）：由边和顶点组成。若，用n表示图中顶点数目，用e表示边或弧的数目。且不考虑顶点到其自身的边或弧，即若vi,vj∈VR，则vi≠vj。那么，)1(21nn；对于有向图，e的对于无向图，e的取值范围是0到取值范围是0到n(n－1)。无向完全图（Completedgraph）：有条边的无向图。)1(21nn有向完全图：有n(n－1)条弧的有向图。稀疏图（Sparsegraph）：有很少条边或弧（如enlogn）的图。反之称为稠密图（Densegraph）。子图（Subgraph）：有两个图G=(V,{E})和G’=(V’,{E’})，如果V’V且E’则称G’为G的子图。E,(a)图7.1中G1的子图V1V4V1V1V1V2V4V3V3V3(b)图7.1中G2的子图图7.2子图示例V1V4V1V2V4V5V3V3V1V2V1V2V4V5对于无向图G=(V,{E})，如果边(v,v’)∈E，则称顶点v和v’互为邻接点（Adjacent）。边(v,v’)依附（Incident）于顶点v和v’，或者说(v,v’)和顶点v和v’相关联。度：指和顶点v相关联的边的数目，记为TD(v)。对于有向图G=(V,{A})，如果弧v,v’∈A，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。弧v,v’和顶点v、v’相关联。入度（InDegree）：以顶点v为头的弧的数目，记为ID(v)。出度（OutDegree）：以顶点v为尾的弧的数目，记为OD(v)。有向图中，顶点v的度为TD(v)＝ID(v)＋OD(v)。一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条niivTDe1)(21边或弧的图，满足如下关系：路径（Path）：在无向图G=(V,{E})中从顶点v到顶点v’的一个顶点序列(v=vi,0,vi,1,…,vi,m=v’)，其中(vi,j-1,vi,j)∈E，1≤j≤m。若G是有向图，则路径也是有向的，顶点序列满足vi,j-1,vi,j∈E，1≤j≤m。路径的长度：路径上的边或弧的数目。简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。回路或环（Cycle）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。连通：在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。连通图（ConnectedGraph）：对于图中任意两个顶点vi,vj∈V，vi和vj都是连通的图。连通分量（ConnectedComponent）：指无向图中的极大连通子图。(a)无向图G3(b)G3的3个连通分量图7.3无向图及其连通分量DEG3ABCDEFGHIKLMJGHIKABCFJLM强连通图：在有向图G中，如果对于每一对vi,vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。强连通分量：有向图中的极大强连通子图。生成树：一个连通图的生成树是一个极小连通子图。它含有图中全部顶点，但只有足以构成一棵树的n－1条边。图7.4G3的最大连通分量的一棵生成树ABCFJLM由生成树的定义易知：①一棵有n个顶点的生成树有且仅有n－1条边。②如果一个图有n个顶点和小于n－1条边，则是非连通图。③如果一个图有n个顶点和大于n－1条边，则一定有环。④有n－1条边的图不一定是生成树。生成森林：一个有向图的生成森林由若干棵有向树组成，含有图中全部的结点，但只有足以构成若干棵不相交的有向树的弧。图7.5一个有向图及其生成森林ADFBCEABCFED边的权、网图有时图的边或弧附带有数值信息，这种数值称为权（Weight）在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。每条边或弧都带权的图称为带权图或网络（Network）如果边是无方向的带权图，则是一个无向网图。否则就是一个有向网图。如下图所示是一个有向网图。（4）图的抽象数据类型定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,w∈V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作：CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。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的最后一个邻接点，则返回“空”。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。BFSTraverse(G,visit());初始条件：图G存在，visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraphDFSTraverse(G,visit());初始条件：图G存在，visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。￡7.2图的存储结构￡7.2.1数组表示法（邻接矩阵）（1）定义数组表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。（2）C语言描述#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}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;思考…设计一个算法判断一个图是否是连通图（3）邻接矩阵中顶点度的求法对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和，即：10)__](][[)(njiNUMVERTEXMAXnjiAvTD对于有向图，顶点vi的出度OD(vi)为第i行的元素之和，顶点vi的入度ID(vi)为第i列的元素之和。（4）网的邻接矩阵网的邻接矩阵可定义为：wi,j若vi,vj或(vi,vj)∈VRA[i][j]=∞反之例如，下图列出了一个有向网和它的邻接矩阵。1356598475(b)邻接矩阵(a)网N4538791655V1V2V6V3V5V4练习1:画出下列图的邻接矩阵,并求出各顶点的度.V1V2V3V4（a）G1V1V2V3V4（b）G200001000100011102A01001001000101101A练习2:绘出如下有向网络的邻接矩阵V2V4V1V3V63527948V56179618727453A（5）图的构造算法7.1如下：StatusCreateGraph(MGraph&G){//采用数组（邻接矩阵）表示法，构造图G。scanf(&G.kind);switch(G.kind){caseDG:returnCreateDG;//构造有向图GcaseDN:returnCreateDN;//构造有向网GcaseUDG:returnCreateUDG;//构造无向图GcaseUDN:returnCreateUDN;//构造无向网Gdefault:returnERROR;}}//CreateGraph算法7.1是在邻接矩阵存储结构MGraph上对图的构造操作的实现框架，它根据图G的种类调用具体构造算法。StatusCreateUDN(MGraph&G){//采用数组（邻接矩阵）表示法，构造无向网G。scanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其他信息for(i=0;iG.vexnum;++i)scanf(&G.vexs[i]);//构造顶点向量for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}for(k=0;kG.arcnum;++k){//构造邻接矩阵scanf(&v1,&v2,&w);//输入一条边依附的顶点及权值i=LocateVex(G,v1);