图的定义和术语及存储结构.ppt

《图的定义和术语及存储结构.ppt》由会员分享，可在线阅读，更多相关《图的定义和术语及存储结构.ppt（35页珍藏版）》请在三一办公上搜索。

1、1,数据结构课程的内容：,多对多（m:n),2,7.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的连通性7.5 图的应用,第7章 图,3,7.1 图的基本术语,其中：V 是G 的顶点集合，是有穷非空集；VR|v,wV 且 P(v,w),是有穷集.,问：当VR 为空时，图G存在否？,V=vertex,图：记为 Graph(V,VR),表示从 v 到 w 的一条弧，并称 w 为弧头，v 为弧尾。P(v,w)定义了弧 的意义或信息。,答：还存在！但此时图G只有顶点。,4,例如:,G=(V,VR),其中V=A,B,C,D,EVR=,无向图：由顶点集和边集构成的图(“边”无方向）,若VR 必有

2、VR,则称(v,w)为顶点 v 和顶点 w 之间存在一条边。,有向图：由顶点集和弧集构成的图（“弧”是有方向的）,5,例如:G=(V,VR)其中：V=A,B,C,D,E,FVR=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),若 n 个顶点的无向图有 n(n-1)/2 条边,称为无向完全图若 n 个顶点的有向图有n(n-1)条边,称为有向完全图,证明：,有向完全图有n(n-1)条边。,证明：若是有向完全图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1),6,证明：从可以直接推论出无向完全图的边数因为无方向，两弧合并为一边，所以

3、边数减半，总边数为n(n-1)/2。,无向完全图有n(n-1)/2 条边。,例：判断下列4种图形各属什么类型？,7,稀疏图：稠密图：,设有两个图 G(V,E)和 G(V,E)。若 V V 且 E E,则称 图G 是 图G 的子图。,子 图：,边较少的图。通常边数远少于nlogn边很多的图。,无向图中，边数接近n(n-1)/2 有向图中，边数接近n(n-1),B,例如：,8,15,9,7,21,11,3,2,有向网或无向网是弧或边带权的图。,邻接点：若边(v,w)VR，则顶点v 和顶点w 互为邻接点。,边(v,w)依附于顶点v 和w，或者与顶点v,w相关联。,顶点v的度：是和v 相关联的边的数目

4、,记为TD(v).,顶点v的出度:以顶点v 为尾的弧的数目;记为OD(v).,顶点v的入度:以顶点v 为头的弧的数目,记为ID(v).,顶点的度(TD)=出度(OD)+入度(ID),问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,答：是树！而且是一棵有向树！,9,路径:设图G=(V,VR)中的一个顶点序列:v=vi,0,vi,1,vi,m=w 中，(vi,j-1,vi,j)（或 vi,j-1,vi,j）VR 1jm,则称从顶点v 到顶点w 之间存在一条路径。路径长度：路径上边（或弧）的数目。,如:从A到F长度为 3 的路径A,B,C,F或A，E，C，F,简单路径:指序

5、列中顶点不重复出现的路径。,简单回路:指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。,10,连通图：无向图G中任意两个顶点之间都有路径相连通。,连通分量：非连通图中的极大连通子图。,强连通图：在有向图中,每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,强连通分量：非强连通图中的极大强连通子图。,11,生成树：,生成森林：,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）,12,CreatGra

6、ph(&G,V,VR)/按定义(V,VR)构造图,DestroyGraph(&G)/销毁图,结构的建立和销毁,对顶点的访问操作,LocateVex(G,u)/若G中存在顶点u，则返回该顶点在图中“位置”，否则返回其它信息。,GetVex(G,v)/返回 v 的值。,PutVex(&G,v,value)/对 v 赋值value。,结构的建立和销毁,插入或删除顶点,对邻接点的操作,遍历,插入或删除弧,基本操作,对顶点的访问操作,13,对邻接点的操作,FirstAdjVex(G,v);/返回v的“第一个邻接点”若该顶点在G中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回v的（

7、相对于w的）“下一个邻接点”。若w是v的最后一个邻接点，则返回“空”。,插入或删除顶点,InsertVex(/在图G中增添新顶点v。,DeleteVex(&G,v)；/删除G中顶点v及其相关的弧。,14,插入和删除弧,InsertArc(/在G中增添弧，若G是无向的，则还增添对称弧。,DeleteArc(/在G中删除弧，若G是无向的，则还删除对称弧。,DFSTraverse(G,v,Visit();/从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。

8、,遍 历,15,7.2 图的存储结构,图的特点：,链式存储结构：,顺序存储结构：,难！,（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）,可用多重链表,邻接矩阵(数组)表示法邻接表(链式)表示法十字链表表示法邻接多重表表示法,但可用数组描述元素间关系。,非线性结构（m:n）,邻接矩阵,邻接表十字链表邻接多重表,各种表示法成立的原则：存入电脑后能唯一复原,16,建立一个顶点表和一个邻接矩阵。,1.邻接矩阵（数组）表示法,记录各个顶点信息,表示各个顶点之间关系,设图 A=(V,E)有 n 个顶点，则图的邻接矩阵是一个二维数组 A.arcsnn，定义为：,17,分析1：无向图的邻接矩阵是对称的；

9、分析2：顶点i 的度第 i 行(列)中1 的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,例1：,邻接矩阵：,A.arcs=,（v1 v2 v3 v4 v5）,v1v2v3v4v5,0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,顶点表：,无向图的邻接矩阵如何表示？,18,例2：有向图的邻接矩阵如何表示？,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行元素之和;顶点vi的入度=第i列元素之和;顶点的度=第i行元素之和+第i列元素之和。,邻接矩阵：,A.arcs=,(v1 v2 v3 v4),v1v2v3v4,注：在

10、有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第j列含义：以结点vj为头的弧(即入度边）。,顶点表：,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,19,例3：有权图（即网络）的邻接矩阵如何表示？,定义：,邻接矩阵：,N.arcs=,(v1 v2 v3 v4 v5 v6),顶点表：,5 7 4 8 9 5 6 5 3 1,v1v2v3v4v5v6,20,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。,邻接矩阵法优点：,邻接矩阵法缺点：,对稀疏图而言尤其浪费空间。,

11、图的邻接矩阵在机内如何表示？（参见教材P161）,注：用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX/最大值#define MAX_VERTEX_NUM 20/假设的最大顶点数typedef enum DG,DN,UDG,UDN GraphKind;/有向图，有向网，无向图，无向网,21,typedef struct ArcCell/弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图,用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NU

12、MMAX_VERTEX_NUM;,typedef struct/图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;,22,2.邻接表（链式）表示法,对每个顶点vi 建立一个单链表，把与vi有关联的边（或以vi为尾的弧)的信息链接起来，表中每个结点都设为3个域。,每个单链表还应当附设一个表头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi 邻接点的位置,链域，指向下一条边或弧的结点,数据域，存

13、储顶点vi 信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,边或弧的信息,23,例1：无向图的邻接表如何表示？,邻接表：,请注意：邻接表不唯一！因各个边结点的链入顺序是任意的。,v1邻接点v4的位置,此无权图未开第3分量,TD(Vi)=单链表中Vi链接的结点个数,24,例2：有向图的邻接表如何表示？,邻接表(出边),逆邻接表(入边),0123,0123,在有向图的邻接表中不易找到指向该顶点的弧。,OD(Vi)=邻接表中Vi链接的结点数ID(Vi)=逆邻接表中Vi链接的结点数,TD(Vi)=OD(Vi)+ID(Vi),25,例3：已知某网的邻接（出边）表，请画出该

14、网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,26,分析1：对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,27,讨论：

15、邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),28,图的邻接表在机内如何表示？（参见教材P163）,#define MAX_VERTEX_NUM 20/假设的最大顶点数,Typedef struct ArcNode/弧结构 int a

16、djvex;/该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针 InfoArc*info;/该弧相关信息的指针 ArcNode；,29,Typedef struct/图结构 AdjList vertics;/应包含邻接表 int vexnum,arcnum;/应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）ALGraph;,Typedef struct VNode/顶点结构 VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjList MAX_VERTEX

17、_NUM;/邻接表,30,它是有向图的另一种链式存储结构。思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。(1)开设弧结点，设5个域（每段弧是一个数据元素）(2)开设顶点结点，设3个域（每个顶点也是一个数据元素）,弧结点,3.十字链表表示法,tailvex:弧尾顶点位置 headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息,31,data:顶点信息firstin:以顶点为弧头的第一条弧结点firstout:以顶点为弧尾的第一条弧结点,问：n个顶点的集合怎样储存？,顺序存储结构,顶点结点,十字链表优点：容易操作，如求顶点的入度、出度等

18、。,空间复杂度和建表的时间复杂度都与邻接表相同。,32,0 1 2,例：画出有向图的十字链表。,弧结点,顶点结点,33,这是无向图的另一种链式存储结构，当对边操作时建议采用此种结构存储。（1）设立边结点，6个域（每条边是一个数据元素）（2）设立顶点结点，2个域（每个顶点也是一个数据元素）,边结点,4.邻接多重表表示法,mark：标志域，标记该边是否被搜索过。ivex，jvex:边依附的两个顶点位置 ilink:指向下一条依附顶点 i 的边位置Jlink：指向下一条依附顶点 j 的边位置info:边信息,34,data:存储顶点信息firstedge:依附顶点的第一条边结点,顶点结点,问:n个顶点的集合怎样储存？,仍用顺序存储结构,邻接多重表优点：容易操作，如求顶点的度,对边操作等。,空间复杂度和建表的时间复杂度都与邻接表相同。,35,例：画出无向图的邻接多重表。,边结点,顶点结点,(v1,v2),(v1,v4),(v2,v5),(v2,v3),(v3,v4),(v3,v5),(v4,v5),