图数据结构

图数据结构图的定义和基本术语一、图的定义本章介绍另一种非线性数据结构—图,主要学习图的存储结构以及图的若干操作的实现。图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图G由两个集合构成，记作G=(V,{A})其中V是顶点的非空有限集合，A是边的有限集合，其中边是顶点的无序对或有序对(此时的图称为无向图或有向图)。无向图G1=(V1,{A1})，V1={v0,v1,v2,v3,v4}，A1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；G1图示V0V4V3V1V2有序对vi,vj：用以为vi起点(弧尾)、以vj为终点(弧头)的有向线段表示，称为有向边或弧；G2图示V0V1V2V3有向图G2=(V2,{A2})，V2={v0v1,v2,v3}，A2={v0,v1,v0,v2,v2,v3,v3,v0}例1交通图（公路、铁路）顶点：地点边：连接地点的路交通图中的有单行道、双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图(如生产流程图)顶点：工序边：各道工序之间的顺序关系V0V4V3V1V2V0V1V2V3图的实例ADTGraph{数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。ADT图的定义基本操作:CreateGraph(&G,V,VR)//按定义构造图初始条件:V是图的顶点集,VR是图中弧的集合。操作结果:按V和VR的定义构造图G。数据关系R:R={VR}VR={v,w︱v,wV，且p(v,w),v,w表示从v到w的弧，谓词p(v,w)定义了弧v,w的意义或信息。}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的第一个邻接点。若顶点v在G中没有邻接顶点，则返回“空”。NextAdjVex(G,v,w)//求下一个邻接点初始条件:图G存在，v是G中某个顶点，w是v的邻接点。操作结果:返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G,v);//插入顶点初始条件:图G存在，v和G中顶点有相同特性。操作结果:在图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。DFSTraverse(G,v,Visit())//深度优先遍历初始条件:图G存在，v是G中某个顶点，Visit()是顶点的应用函数。操作结果:从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败。BFSTraverse(G,v,Visit())//广度优先遍历初始条件:图G存在，v是G中某个顶点，Visit()是顶点的应用函数。操作结果:从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败。2顶点的度、入度、出度顶点v的度TD(v)=与v相关联的边的数目。在有向图中：顶点v的出度OD(v)=以v为起点有向边数；顶点v的入度ID(v)=以v为终点有向边数；TD(v)=OD(v)+ID(v)V0V4V3V1V2V0V1V2V3二、图的基本术语1邻接点及关联边邻接点：边的两个顶点；关联边：若边e=(v,u),则称边e与顶点v和u相关联；设图G的顶点数为n，边数为e则图的所有顶点的度数之和=2*e（每条边对图的所有顶点的度数之和“贡献”2度）无向图G1有向图G2V0V4V3V1V2V0V1V2V33路径、回路(环)无向图G1=（V1，E1）中的顶点序列v1,v2,…,vk,若(vi,vi+1)E1(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在G1中，v0,v1,v2,v3是v0到v3的路径；v0,v1,v2,v3,v0是回路；有向图G2=（V2，E2）中的顶点序列v1,v2,…,vk,vi,vi+1E2(i=1,2,…k-1),若v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在G2中，v0,v2,v3是v0到v3的路径v0,v2,v3,v0是回路；简单路径和简单回路在一条路径中,若所有顶点各不相同,则称该路径为简单路径；若除起点和终点外,其余顶点各不相同的回路称为简单回路。例有向图G2无向图G1V0V4V3V1V2V0V1V2V3在图G1中，V0,V1,V2,V3是简单路径；V0,V1,V2,V4,V1不是简单路径；在图G2中，V0,V2,V3,V0是简单回路；4连通图（强连通图）在无（有）向图G=(V,E)中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）非连通图连通图强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4非强连通图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V25子图例下列(b)、(c)是(a)的子图6(强)连通分量无向图G的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；连通分量非连通图V0V2V3V1V5V4V0V2V1非连通分量有向图D的极大强连通子图称为D的强连通分量。极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V1非强连通图7生成树包含无向图G所有顶点的极小连通子图称为G的生成树。极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。G的生成树V0V4V3V1V2连通图GV0V4V3V1V2V0V4V3V1V2若T是G的生成树当且仅当T满足如下条件：T是G的连通子图；T包含G的所有顶点；T中无回路。一棵n个顶点的生成树有且仅有足以构成树的n-1条边。说明：G的生成树V0V4V3V1V2连通图GV0V4V3V1V2V0V4V3V1V2若在一棵生成树上删除一条边，就不再连通。若在一棵生成树上添加一条边，必定构成一个环。不再连通构成环图的存储结构由于图中任意两个顶点之间都可能存在联系，因此难以以数据元素在存储区中物理位置表示它们间的关系，但可以借助数组表示之。另一方面，也可以用多重链表表示图。但由于图中顶点的度可能相差悬殊，会因此造成空间的浪费；反之，若按每个顶点的度设计不同的结点结构，又会造成操作上的不便。应根据具体的图和需要，设计恰当的结点结构和表结构。图的存储结构至少要保存两类信息：1)顶点的数据；2)顶点间的关系。如何表示顶点间的关系？V0V4V3V1V2V0V1V2V3常用图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：A[i][j]=1若(vi,vj)E或vi,vjE0否则0101010101201011301004011000110000000011000V0V4V3V1V2V0V1V2V3一、数组表示法(邻接矩阵表示)typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。对无权图，//用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//－－图的数组(邻接矩阵)存储表示－－#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind；//{有向图，有向网，无向图，无向网}typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点向量—保存顶点数据AdjMatrixarcs;//邻接矩阵—保存顶点间关系intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；010101010120101130100401100对有向图的数组表示法可做类似的讨论V0V4V3V1V22）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否非零；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋非零值或清零；5）用二维数组存储顶点数为n的图,占用存储空间只与它的顶点数n有关，与边数e无关。适用于边稠密的图。图的基本操作的实现(采用数组表示法)：1）求无向图某顶点vi的度：(或有向图vi的出度)A[i][0]到A[i][n-1]中的非零个数，即数组A第i行的非零元素的个数；010101010120101130100401100V0V4V3V1V2V0V1V2V301100000000110002）求有向图某顶点vi的入度：A[0][i]到A[n-1][i]中的非零个数，即数组A中第i列的非零元素的个数；3）求图中的总边数：扫描整个数组A，统计出数组中非零元素的个数。无向图的总边数为非零元素个数的一半，而有向图的总弧数为非零元素个数。图的构造操作的实现(采用数组表示法)StatusCreateGraph(MGraph&G){//采用数组表示法,构造图Gscanf(&G.kind);switch(G.kind){caseDG:returnCreateDG(G);//构造有向图GcaseDN:returnCreateDN(G);//构造有向网GcaseUDG:returnCreateUDG(G);//构造无向图GcaseUDN:returnCreateUDN(G);//构造无向网Gdefault:returnERROR;}}//CreateGraph无向网的构造算法StatusCreateUDN(MGraph&G){//采用数组表示法,构造无向网Gscanf(&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};for(k=0;kG.arcnum;++