图图的定义存储结构

《图图的定义存储结构》由会员分享，可在线阅读，更多相关《图图的定义存储结构（43页珍藏版）》请在金锄头文库上搜索。

1、数据结构7.1 图的定义和术语第七章 图7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图的应用数学家欧拉曾经解决过著名的七 桥问题：城市中有一条河，河中有A、D 两个岛，河上有七座桥来连接两个岛及 河的B、C两岸，问：能否刚好经过每座 桥一次，既无重复也无遗漏？在线性结构中，数据元素之间仅具有线性关系； 在树结构中，结点之间具有层次关系； 在图结构中，任意两个顶点之间都可能有关系。 FECBAD线性结构 ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比在线性结构中，元素之间的关系为前驱和后继； 在树结构中，结点之间的关系为双亲和孩子； 在图结构中

2、，顶点之间的关系为邻接。 FECBAD线性结构 ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比7.1 图的定义和术语图是由顶点的非空有限集合与顶点之间关系 (边或弧)的有限集合构成的结构, 通常表示为G = ( V, E) 其中, V 为顶点集合, E 为关系(边或弧)的集合.一.图的定义例1 G1= V1=v1,v2,v3,v4 ,v5 E1=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)G1图示无序对(vi,vj)： 用连接顶点vi、vj的线段 表示，称为无向边；V5V1 V2V4V3无向图：在图G中，若所有边是无向边，

3、则称G为无向图；例2 G2= V2=v1,v2,v3,v4 E2=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)G2图示完全图：若具有n个结点的无向图,其边数达到最大值 n(n-1)/2,则称图为完全图；V3V1 V2V4例3 G3= V3=v1,v2,v3,v4 E3=, , , G3图示有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；V1 V2V3 V4有向图：在图G中，若所有边是有向边，则称G为有向图； 有向完全图:具有n(n-1)条弧的有向图。二.图的应用例1 交通图（公路、铁路）顶点：地点边：连接地点的公路交

4、通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图顶点：元件边：连接元件之间的线路 例3 通讯线路图顶点：地点边：地点间的连线 例4 各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系V5V1 V2V4V31.顶点的度对于有向图而言, 有:顶点的出度:以顶点v为出发点的边的数目,记为OD(v)。顶点的入度:以顶点v 为终止点的边的数目,记为ID(v)。顶点的度： TD(v) = OD(v) + ID(v)对于无向图而言，有：顶点的入度=顶点的出度图的度为图中结点度的最大值。三.名词术语依附于顶点v的边的数目,记为TD(v)。V1 V2V3 V42. 路径和回路无向图

5、D=(V,E)中的顶点序列v1,v2, ,vk,若(vi,vi+1)E(i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；有向图D=(V,E)中的顶点序列v1,v2, ,vk, 若E ( i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；V5V1 V2V4V3V1 V2V3 V43.子图 对于图G=(V,E) 与 G=(V,E), 若有VV, EE, 则称G为G的一个子图.V5V1 V2V4V3V5V1 V2V3V5V1 V2V4V3图1图2图34. 连通图和连通

6、分量在无向图G=（V, E）中，若对任何两个顶点v、u都 存在从v到u的路径，则称G是连通图。非连通图的极大连通子图称为连通分量。 连通图V5V1 V2V4V3V5V6V3V1 V2V4非连通图u是子图； u子图是连通的； u连通子图含有极 大顶点数； u具有极大顶点数 的连通子图包含依 附于这些顶点的所 有边。5. 强连通图和强连通分量在有向图G=( V, E )中，若对任何两个顶点v、u都 存在从v到u的路径，则称G是强连通图。 强连通图V4V1 V2V3非强连通图的极大强连通子图称为强连通分量。 非强连通图V4V1 V2V3强连通分量V4V1 V2V3观察：强连通分量中一般存在回路；划分

7、后可能会丢掉一些 弧，但顶点不能丢。6.生成树包含无向图G所有顶点的极小连通子图称为G的生成树。极小连通子图：该子图是G的连通子图，在该子图 中删除任何一条边，子图不再连通。若T是G的生成树当且仅当T满足如下条件：T是G的连通子图T包含G的所有顶点T中无回路说明说明V5V1 V2V4V3V5V1 V2V4V36.生成树包含无向图G所有顶点的极小连通子图称为G的生成树。一棵有n个顶点的生成树有且仅有n-1条边，但有n- 1条边和n个顶点的图不一定是生成树。如果一个图有n个顶点和少于n-1条边，则该图一定 不是连通图。说明说明V5V1 V2V4V3V5V1 V2V4V3如果一个图有n个顶点和多于n

8、-1条边，则该图一定 有环。v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v46.生成树画出下图的生成树：规律：一棵有n个顶点的生成树有且仅有n-1条边。7.2 图的存储结构例G12413例15324G2V1V2 V4 V3 V1 V2V4 V5 V3一.数组表示法（邻接矩阵）7.2 图的存储结构V5V1 V2V4V3顶点的存储：用一维数组存储（按编号顺序）G的邻接矩阵是满足如下条件的n阶矩阵： Aij=1 若(vi,vj)E 或 E0 否则顶点关系的存储：邻接矩阵一.数组表示法（邻接矩阵）7.2 图的存储结构V5V1 V2V4V30 1 0 1

9、0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 00 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0V1 V2V3 V4无向图数组表示法特点无向图邻接矩阵是对称矩阵，同一条边表示了两次；顶点v的度：等于二维数组对应行（或列）中1的个数；一.数组表示法（邻接矩阵）7.2 图的存储结构V5V1 V2V4V30 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 00 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0V1 V2V3 V4无向图数组表示法特点判断两顶点v、u是否为邻接点：只需判断二维数组对应分

10、量是否为1；顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；一.数组表示法（邻接矩阵）7.2 图的存储结构V5V1 V2V4V30 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 00 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0V1 V2V3 V4无向图数组表示法特点设存储顶点的一维 数组大小为m, G占用存储空间:m+m2,G占用存储空间只与它的顶点数有关，与边数无关，适用于边稠密图。一.数组表示法（邻接矩阵）7.2 图的存储结构V5V1 V2V4V30 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1

11、0 1 0 0 0 1 1 0 00 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0V1 V2V3 V4有向图数组表示法特点有向图的邻接矩 阵的第i行元素1的个 数为第i个顶点的出 度;第i列元素1的个 数为第i个顶点的入 度。一.数组表示法（邻接矩阵）7.2 图的存储结构网的邻接矩阵是满足如下条件的n阶矩阵： Aij=wij 若(vi,vj)E 或 E 否则V1 V2V5 V4V6 V335 45 518 9 76 5 7 4 8 9 5 6 5 3 1 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /最大顶点个数

12、 typedef enum DG,DN,UDG,UDN GraphKind; /图种类有向图，有向网，无向图，无向网 typedef struct ArcCell /边(弧)信息 VRType adj; /图取值0或1，网取值InfoType *info; /弧相关信息指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; /存储顶点的一维数组AdjMatrix arcs; /存储邻接矩阵的二维数组int vexnum, arcnum; /图的当前顶点数和弧数

13、GraphKind kind; /图的种类标志 Mgraph;一.数组表示法（邻接矩阵）161页设G是Mgraph 类型的变量，用于存储无向图，该图有n个顶 点，e条边G的图示如下：G.vexs G.arcsG.vexnu mG.arcnu m G.kind V105 6 UDGV5V1 V2V4V30 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0一.数组表示法（邻接矩阵）status CreateUDN(MGraph for(i=0;iG.vexnum;+i) scanf(/输入顶点for(i=0;iG.vexnum;+i) for(j=0;

14、jG.vexnum;+j) G.arcsij=INFINITY,NULL；/初始化邻接矩阵for(k=0;kG.arcnum;+k) ;/构造邻接矩阵 scanf(/输入一条边依附的两个顶点及权i=LocateVex(G,v1); /确定v1和v2在G中的位置j=LocateVex(G,v2);G.arcsij.adj=w; if(IncInfo) Input(*G.arcsij.Info); /输入弧相关信息G.arcsji=G.arcsij;/无向网有对称弧return OK; 162页优点：容易实现图的操作，如：求某顶点的度、 判断顶点之间是否有边（弧）、找顶点的邻接 点等等。缺点：n个顶点需要n*n个单元存储边(弧);空间效 率为O(n2)。对稀疏图而言尤其浪费空间。一.数组表示法（邻接矩阵）二.邻接表1 . 无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用线性链表存储V5V1 V2V4V3例01234m-1V1 V2 V3 V4 V5134 2211002 3该结点表示边(V1,V2)4二.邻接表1 . 无向图的邻接表表头结点datafirstarcadjvexnextarc边(弧)结点data