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

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

1、图的定义和术语及存储结构1数据结构课程的内容：数据结构课程的内容：多对多多对多（m:n)图的定义和术语及存储结构27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章章 图图图的定义和术语及存储结构37.1 7.1 图的基本术语图的基本术语其中：其中：V V 是是G G 的顶点集合，是有穷非空集；的顶点集合，是有穷非空集； VRVR| v,wV | v,wV 且且 P(v,w),P(v,w),是有穷集是有穷集. . 问：问：当当VR VR 为空时，图为空时，图G G存在否

2、？存在否？V=vertex 图：图：记为记为 Graph( V, VR )E EA AC CB BD D表示从表示从 v v 到到 w w 的一条弧，的一条弧，并称并称 w w 为为弧头弧头，v v 为为弧尾弧尾。 P(v,w) P(v,w) 定义了弧定义了弧 的意义的意义或信息。或信息。答：还存在！但此时图答：还存在！但此时图G G只有顶点。只有顶点。图的定义和术语及存储结构4E EA AC CB BD D例如例如: : G = (V, VR)G = (V, VR)其中其中V=A, B, C, D, EV=A, B, C, D, EVR=, ,VR=, , , , , , , , , , 无

3、向图：无向图：由顶点集和边集构成的图由顶点集和边集构成的图(“(“边边”无方向）无方向）若若 VR VR 必有必有 VR, VR, 则称则称 (v,w)(v,w) 为顶点为顶点 v v 和顶点和顶点 w w 之间存在一条边。之间存在一条边。有向图：有向图：由顶点集和弧集构成的图由顶点集和弧集构成的图（“弧弧”是有方向的）是有方向的）图的定义和术语及存储结构5BCAFED例如例如: : G=(V,VR)G=(V,VR)其中：其中：V=A, B, C, D, E, FV=A, B, C, D, E, FVR=(A, B), (A, E),VR=(A, B), (A, E), (B, E), (B,

4、 E), (C, D), (D, F), (B, F), (C, F) (C, D), (D, F), (B, F), (C, F) v若若 n n 个顶点的无向图有个顶点的无向图有 n n( (n n-1)/2 -1)/2 条边条边, , 称为称为无向完全无向完全图图v若若 n n 个顶点的有向图有个顶点的有向图有n n( (n-n-1) 1) 条边条边, , 称为称为有向完全图有向完全图证明：证明：证明：证明：若是有向完全图，则若是有向完全图，则n个顶点中个顶点中的每个顶点都有一条弧指向其它的每个顶点都有一条弧指向其它n-1个个顶点顶点, 因此总边数因此总边数=n(n-1)1234图的定义

5、和术语及存储结构6证明：证明：从从可以直接推论出无向完全图的可以直接推论出无向完全图的边数边数因为无方向，两弧合并为一边，因为无方向，两弧合并为一边，所以边数减半，总边数为所以边数减半，总边数为n(n-1)/2。1234例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？图的定义和术语及存储结构7稀疏图：稀疏图：稠密图：稠密图： 设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。子子 图：图：边较少的图。通常边数远少于边较少的图。通常边数远少于边很多的图。边很多的图。无向图中，边数接近无向图

6、中，边数接近有向图中，边数接近有向图中，边数接近BBCABECFABECF例如：例如：图的定义和术语及存储结构8ABECF1597211132有向网有向网或或无向网无向网是弧或边带权的图是弧或边带权的图。邻接点：邻接点：若边若边(v,w) VR，则，则顶点顶点v v 和顶点和顶点w w 互为邻接点。互为邻接点。 边边(v,w) (v,w) 依附依附于顶点于顶点v v 和和w w，或者，或者与顶点与顶点v,wv,w相关联相关联 。顶点顶点v v的度：的度：是和是和v v 相关联的边的数目相关联的边的数目, ,记为记为TD(v)TD(v). .顶点顶点v v的出度的出度: : 以顶点以顶点v v

7、为尾的弧的数目为尾的弧的数目; ;记为记为OD(v)OD(v). .顶点顶点v v的入度的入度: : 以顶点以顶点v v 为头的弧的数目为头的弧的数目, ,记为记为ID(v)ID(v). .顶点的度顶点的度(TD)=(TD)=出度出度(OD)+(OD)+入度入度(ID)(ID)问：当有向图中仅问：当有向图中仅1 1个顶点的入个顶点的入度为度为0,0,其余顶点的入度均其余顶点的入度均为为1 1，此时是何形状？，此时是何形状？答：是树！答：是树！而且是一棵而且是一棵有向树！有向树！图的定义和术语及存储结构9路径路径: :设图设图G=(V,VR)G=(V,VR)中的一个顶点序列中的一个顶点序列: :

8、v=vv=vi,0 i,0 ,v,vi,1 i,1 , , v, , vi,mi,m=w =w 中，中，(v(vi,j-1 i,j-1 ,v,vi,ji,j) )（或（或 v vi,j-1i,j-1,v,vi,ji,j） VRVR 1jm,1jm,则称从顶点则称从顶点v v 到顶到顶点点w w 之间存在一条路径。之间存在一条路径。路径长度：路径长度：路径上边路径上边（或弧）（或弧）的数目。的数目。ABECF如如: :从从A A到到F F长度为长度为 3 3 的路径的路径A,B,C,FA,B,C,F或或AA，E E，C C，FF简单路径简单路径: :指序列中顶点不重复出现的路径。指序列中顶点不重

9、复出现的路径。简单回路简单回路: :指序列中第一个顶点和最后一个顶点相同，指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。其余顶点不重复出现的回路。图的定义和术语及存储结构10连通图：连通图：无向无向图图G G中任意中任意两个顶点之间都有路径相两个顶点之间都有路径相连通。连通。连通分量：连通分量：非连通图中非连通图中的极大连通子图。的极大连通子图。BACDFEBACDFE强连通图：强连通图：在有向图中在有向图中, , 每一对顶点每一对顶点v vi i和和v vj j, , 都存都存在一条从在一条从v vi i到到v vj j和从和从v vj j到到v vi i的路径的路径强连通

10、分量：强连通分量：非强连通非强连通图中的极大强连通子图。图中的极大强连通子图。ABECFABECF图的定义和术语及存储结构11生成树：生成树：v1v2v3v4生成森林：生成森林： 假设一个连通图有假设一个连通图有 n n 个顶点和个顶点和 e e 条边，其中条边，其中 n-1 n-1 条边和条边和 n n 个个顶点构成一个极小连通子图，称顶点构成一个极小连通子图，称该极小连通子图为此连通图的生该极小连通子图为此连通图的生成树。成树。由若干棵由若干棵生成树生成树组成，含全部顶点，但构成组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均这些树的边是最少的。（对有向或无向图均适用）适用）

11、图的定义和术语及存储结构12CreatGraph(&G, V, VR)/按定义按定义(V,VR)(V,VR)构造图构造图DestroyGraph(&G) / / 销毁图销毁图结构的建立和销毁结构的建立和销毁对顶点的访问操作对顶点的访问操作LocateVex(G, u) / / 若若G G中存在顶点中存在顶点u u，则返回该顶点，则返回该顶点在图中在图中“位置位置”，否则返回其它信息。，否则返回其它信息。GetVex(G, v) / / 返回返回 v v 的值。的值。PutVex(&G, v, value) / / 对对 v v 赋值赋值valuevalue。结构的建立和销毁结构的建立和销毁插入

12、或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作遍历遍历插入或删除弧插入或删除弧基本操作基本操作对顶点的访问操作对顶点的访问操作图的定义和术语及存储结构13对邻接点的操作对邻接点的操作FirstAdjVex(G, v); /返回返回v v的的“第一个邻接点第一个邻接点” ” 若该若该顶点在顶点在G G中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVex(G, v, w); /返回返回v v的（相对于的（相对于w w的）的） “ “下下一个邻接点一个邻接点”。若。若w w是是v v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。插入或删除顶点插入或删除顶点Inse

13、rtVex(&G, v); /在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G, v)；/删除删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。图的定义和术语及存储结构14插入和删除弧插入和删除弧InsertArc(&G, v, w); / / 在在G G中增添弧中增添弧，若，若G G是是无向的，则还增添对称弧无向的，则还增添对称弧。DeleteArc(&G, v, w); /在在G G中删除弧中删除弧，若，若G G是是无向的，则还删除对称弧无向的，则还删除对称弧。DFSTraverse(G, v, Visit(); /从顶点从顶点v v起深度优先遍历起深度优先遍历

14、图图G G，并对每个顶点调用函数，并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点从顶点v起广度优先遍历图起广度优先遍历图G，并对每个顶点调用函数，并对每个顶点调用函数Visit一次且仅一次。一次且仅一次。遍遍 历历图的定义和术语及存储结构157.2 7.2 图的存储结构图的存储结构图的特点：图的特点：链式存储结构：链式存储结构：顺序存储结构：顺序存储结构： 难！难！ （多个顶点，无序可言，无法仅以（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）顶点坐标表达相互关系）可用可用多重链表多重链表但可但可用用数组数

15、组描述元素间关系。描述元素间关系。非线性结构非线性结构（m :nm :n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原各种表示法成立的原则：存入电脑后能唯则：存入电脑后能唯一复原一复原图的定义和术语及存储结构16 建立一个建立一个顶点表顶点表和一个和一个邻接矩阵邻接矩阵。 , ),( , ,.否否则则或或者者如如果果01AEjiEjijiarcs记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表示各个顶点之间关系 设图设图 A = (A = (V V, , E E ) ) 有有 n n 个顶点，则图的邻接个顶点，则图的邻接矩阵是一个二维数组矩阵是一个二

16、维数组 A A.arcs.arcs n nn n ，定义为：，定义为：图的定义和术语及存储结构17邻接矩阵：邻接矩阵：A.arcs =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v4图的定义和术语及存储结构18例例2 2 ：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。顶点顶点v vi i的出度的出度= =第第i i行元素之和行元素之和

17、; ; 顶点顶点v vi i的入度的入度= =第第i i列元素之和列元素之和; ; 顶点的度顶点的度= =第第i i行元素之和行元素之和+ +第第i i列元素之和。列元素之和。v1v2v3v4邻接矩阵：邻接矩阵：A.arcs =( v1 v2 v3 v4 )v1v2v3v4在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第j j列含义：以结点列含义：以结点v vj j为头的弧为头的弧( (即入度边）。即入度边）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 图的定义

18、和术语及存储结构19例例3 3 ： 有权图（即网络）的邻接矩阵如何表示？有权图（即网络）的邻接矩阵如何表示？定义：定义：A.arcs i j =Wij 或（或（vi, vj）VR 反之反之v1v2v3v4Nv5v65489755613邻接矩阵：邻接矩阵： N.arcs =(v1 v2 v3 v4 v5 v6)顶点表：顶点表： 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6图的定义和术语及存储结构20 容易实现图的操作，如：求某顶点的容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。点的邻接点等等。 n n个

19、顶点需要个顶点需要个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O(O(n n ) )。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：对稀疏图而言尤对稀疏图而言尤其浪费空间。其浪费空间。图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？ （参见教材（参见教材P161P161）注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数typedef enum DG, DN, UDG,UDN

20、GraphKind; /有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网 图的定义和术语及存储结构21typedef struct ArcCell / / 弧的定义弧的定义 VRType adj; / VRType/ VRType是顶点关系类型。是顶点关系类型。/对无权图对无权图, ,用用1 1或或0 0表示相邻否；对带权图，则为权值类型表示相邻否；对带权图，则为权值类型。 InfoType *info; / / 该弧相关该弧相关信息的指针信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / /

21、 图的定义图的定义 VertexType vexsMAX_VERTEX_NUM; / / 顶点向量顶点向量 AdjMatrix arcs; / / 邻接矩阵邻接矩阵 int vexnum, arcnum; / / 顶点数，弧数顶点数，弧数 GraphKind kind; / / 图的种类标志图的种类标志 MGraph;图的定义和术语及存储结构22adjvexnextarcinfodatafirstarc邻接点域，邻接点域，表示表示v vi i 邻接邻接点的位置点的位置链域，链域，指向指向下一条边或下一条边或弧的结点弧的结点数据域，数据域，存储顶点存储顶点v vi i 信息信息链域，链域，指向指

22、向单链表的第单链表的第一个结点一个结点边或弧的信息边或弧的信息图的定义和术语及存储结构23例例1 1：无向图的邻接表如何表示？：无向图的邻接表如何表示？v1v2v3v5v4v4邻接表：邻接表：0123413341420请注意：邻接表不唯一！请注意：邻接表不唯一！因各个边结点的链入顺序因各个边结点的链入顺序是任意的。是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4的位置的位置此无权图未开此无权图未开第第3 3分量分量TD(Vi)=单链表中单链表中V Vi i链接的结点个数链接的结点个数图的定义和术语及存储结构24例例2 2：有向图的邻接表如何表示？：有向图的邻接表如

23、何表示？v1v2v3v4V4V3V2V12301邻接表邻接表( (出边出边) )V4V3V2V13020逆邻接表逆邻接表( (入边入边) )01230123在有向图的邻接表中不易找到指向该顶点的弧。在有向图的邻接表中不易找到指向该顶点的弧。OD(Vi)=邻接表中邻接表中Vi链接的结点数链接的结点数ID(Vi)=逆邻接表中逆邻接表中Vi i链接的结点数链接的结点数TD(Vi) = OD( Vi ) + ID( Vi )图的定义和术语及存储结构25例例3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存储结构形成后

24、，图便成后，图便唯一确定！唯一确定！图的定义和术语及存储结构26分析分析1：对于对于n n个顶点个顶点e e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n n个头结点外，只有个头结点外，只有2e2e个表结点个表结点, ,空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2) )，则比邻接矩阵表示法，则比邻接矩阵表示法O(nO(n2 2) )省空省空间。间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:2:在有向图中，邻接表中除了在有向图中，邻接表中除了n n个头结点外，只个头结点外，只有有e e个表结点个表结点, ,空间效率为空间效率为O(n+

25、e)O(n+e)。若是稀疏图，则比。若是稀疏图，则比邻接矩阵表示法合适。邻接矩阵表示法合适。它其实是对邻接矩阵法的一种它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧改进，两个结点表示一条边或弧邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点： 空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵两结点对应的单链表，没有邻接矩阵方便。方便。图的定义和术语及存储结构27讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联系：联系：邻接表

26、中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但号与顶点编号一致），但邻接表不唯一邻接表不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于

27、稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2) )图的定义和术语及存储结构28图的邻接表在机内如何表示？图的邻接表在机内如何表示？ （参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct ArcNode /弧结构弧结构 int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info;

28、/该弧相关信息的指针该弧相关信息的指针 ArcNode；图的定义和术语及存储结构29Typedef struct /图结构图结构 AdjList vertics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向第一条依附该顶点指向第一条依附该顶点的弧的指针的弧的指针VNod

29、e, AdjList MAX_VERTEX_NUM ; /邻接表邻接表 图的定义和术语及存储结构30 它是它是有向图有向图的另一种链式存储结构。的另一种链式存储结构。 思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。的结合。(1)(1)开设弧结点，设开设弧结点，设5 5个域（每段弧是一个数据元素）个域（每段弧是一个数据元素）(2)(2)开设顶点结点，设开设顶点结点，设3 3个域（每个顶点也是一个数据个域（每个顶点也是一个数据元素）元素）tailvex headvex hlinktlinkinfo弧结点弧结点tailvex: 弧尾顶点位置弧尾顶

30、点位置 headvex: 弧头顶点位置弧头顶点位置hlink: 弧头相同的下一弧位置弧头相同的下一弧位置tlink: 弧尾相同的下一弧位置弧尾相同的下一弧位置info: 弧信息弧信息图的定义和术语及存储结构31 data : 顶点信息顶点信息firstin : 以顶点为弧头的第以顶点为弧头的第一条弧结点一条弧结点firstout: 以顶点为弧尾的第以顶点为弧尾的第一条弧结点一条弧结点问：问：n n个顶点的集合怎样储存？个顶点的集合怎样储存？顺序存储结构顺序存储结构data firstinfirstout顶点结点顶点结点十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求

31、顶点的入度、出度等。空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。图的定义和术语及存储结构32ABCABC0 1 20 2 0 12 1 2 0 例：画出有向图的十字链表。例：画出有向图的十字链表。tailvex headvex hlinktlink弧结点弧结点data firstinfirstout顶点结点顶点结点图的定义和术语及存储结构33这是这是无向图无向图的另一种链式存储结构，当对边操作时建的另一种链式存储结构，当对边操作时建议采用此种结构存储。议采用此种结构存储。（1 1）设立边结点，）设立边结点， 6 6个域（每条边是一个数据元素）个域（每

32、条边是一个数据元素）（2 2）设立顶点结点，）设立顶点结点， 2 2个域（每个顶点也是一个数据个域（每个顶点也是一个数据元素）元素）mark ivex ilink jvexjlink info边结点边结点4. 4. 邻接多重表表示法邻接多重表表示法mark：标志域，标记该边是否被搜索过。标志域，标记该边是否被搜索过。ivex， jvex : 边依附的两个顶点位置边依附的两个顶点位置 ilink: 指向下一条依附顶点指向下一条依附顶点 i i 的边位置的边位置Jlink： 指向下一条依附顶点指向下一条依附顶点 j j 的边位置的边位置info: 边信息边信息图的定义和术语及存储结构34 data

33、 : 存储顶点信息存储顶点信息firstedge : 依附顶点的第一依附顶点的第一条边结点条边结点data firstedge顶点结点顶点结点问问: :n n个顶点的集合怎样储存？个顶点的集合怎样储存？ 仍用顺序存储结构仍用顺序存储结构邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度容易操作，如求顶点的度, ,对边对边操作等。操作等。空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。图的定义和术语及存储结构35v1v2v3v5v4v4例：画出无向图的邻接多重表。例：画出无向图的邻接多重表。mark ivex ilink jvex jlink边结点边结点data firstedge顶点结点顶点结点121 4232 43 4 0v11v22v33v44v5012340103(v1,v2)(v1,v4)(v2,v5)(v2,v3)(v3,v4)(v3,v5)(v4,v5)