武汉理工大学-信息工程学院-数据结构-ppt-课件ch07-1-图1-图的定义和存储

第7章图数据结构讲义-图的定义和存储信息工程学院魏洪涛Email:[e-mail]图的定义：图G是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。例如，对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：G1=(V1,E1),其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2)，其中V2={1,2,3},E2={1,2,1,3,2,3,3,1}。dAAcAba213(a)无向图G1(b)有向图G2图7-1无向图和有向图7.1图的基本概念7.2图的存贮结构图无法以数据元素在存储区中的物理位置来表示元素之间关系，即图没有顺序映象的存储结构。用多重链表表示图，即以一个数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针。常用的有邻接矩阵、邻接表和十字链表等。不管哪一种方式，它除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。–多重链表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V31．图的邻接矩阵表示在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）∈E(G)或〈i,j〉∈E(G),则矩阵中第i行第j列元素值为1，否则为0。图的邻接矩阵定义为：1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形7.2.1邻接矩阵例如,对图7-8所示的无向图和有向图的邻接矩阵。312(a)无向图G3(b)有向图G4图7-8无向图G3及有向图G412430111101011011010001100110(a)G3的邻接矩阵(b)G4的邻接矩阵邻接矩阵表示2．从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的，可压缩存储（上（下）三角）;（2）第i行或第i列中1的个数为顶点i的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。3．从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的;（2）第i行中1的个数为顶点i的出度;（3）第i列中1的个数为顶点i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i和顶点j是否有弧相连.4．网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形网及网的邻接矩阵见下图。7493728421986316(a)网G5(b)网G5的邻接矩阵示意图网及邻接矩阵示意图5312436124897邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。邻接矩阵法缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。1．图的邻接表表示图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。vertexlinknextadjvexweightnext边结点顶点结点7.2.2邻接表123424^134^24^123^(a)无向图G3的邻接表12323^3^1^1233^1^13^(b)有向图G4的邻接表(c)有向图G4的逆邻接表邻接表示例左图所示的无向图G3和有向图G4的邻接表见右图所示:312(a)无向图G3(b)有向图G4无向图G3及有向图G412432．从无向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。3．从有向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。例：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储结构形成后，图便唯一确定！如果是无向图，只要搜索任意一个结点的边表。有向图要搜索两个结点的边表。邻接表的优点：–空间效率高；容易寻找顶点的邻接点；邻接表的缺点：–判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。4．图的邻接表数据类型描述图的邻接表数据类型描述如下：#defineMAXN50/*MAXN表示图中最大顶点数*/typedefstructe_node//定义边结点的结构{intadjvex;intweight;//边的信息structe_node*next;}E_NODE;//指向邻接点的指针typedefstructv_node//定义邻接表的表头类型{intvertex;//顶点信息E_NODE*link;//指向“边表”的指针}V_NODE;V_NODEhead[MAXN];讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2)有向图的十字链表表示法弧结点：typedefstructarcnode{inttailvex,headvex;//弧尾、弧头在表头数组中位置structarcnode*hlink；//指向弧头相同的下一条弧structarcnode*tlink;//指向弧尾相同的下一条弧}AD;tailvexheadvexhlinktlink顶点结点：typedefstructdnode{intdata;//存与顶点有关信息structarcnode*firstin；//指向以该顶点为弧头的第一个弧结点structarcnode*firstout;//指向以该顶点为弧尾的第一个弧结点}DD;DDg[M];//g[0]不用datafirstinfirstout例bdacabcd123413123431434241^^^^^^^^无向图的邻接多重表表示法顶点结点：typedefstructdnode{intdata;//存与顶点有关的信息structnode*firstedge;//指向第一条依附于该顶点的边}DD;DDga[M];//ga[0]不用datafirstedge边结点：typedefstructnode{intmark;//标志域intivex,jvex;//该边依附的两个顶点在表头数组中位置structnode*ilink,*jlink;//分别指向依附于ivex和jvex的下一条边}JD;markivexilinkjvexjlink例aecbd1234acdb5e121434323552^^^^^作业已知如图所示的有向图，请给出该图的:–（1）每个顶点的入/出度；–（2）邻接矩阵；–（3）邻接表；–（4）逆邻接表；–（5）十字链表.