最新图的定义和术语及存储结构ppt课件.ppt

《最新图的定义和术语及存储结构ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新图的定义和术语及存储结构ppt课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的定义和术语及存储结构图的定义和术语及存储结构27.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章章 图图9路径路径: :设图设图G=(V,VR)G=(V,VR)中的一个顶点序列中的一个顶点序列: :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

2、v 到顶到顶点点w w 之间存在一条路径。之间存在一条路径。路径长度：路径长度：路径上边路径上边（或弧）（或弧）的数目。的数目。ABECF如如: :从从A A到到F F长度为长度为 3 3 的路径的路径A,B,C,FA,B,C,F或或AA，E E，C C，FF简单路径简单路径: :指序列中顶点不重复出现的路径。指序列中顶点不重复出现的路径。简单回路简单回路: :指序列中第一个顶点和最后一个顶点相同，指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。其余顶点不重复出现的回路。10连通图：连通图：无向无向图图G G中任意中任意两个顶点之间都有路径相两个顶点之间都有路径相连通。连通。连

3、通分量：连通分量：非连通图中非连通图中的极大连通子图。的极大连通子图。BACDFEBACDFE强连通图：强连通图：在有向图中在有向图中, , 每一对顶点每一对顶点v vi i和和v vj j, , 都存都存在一条从在一条从v vi i到到v vj j和从和从v vj j到到v vi i的路径的路径强连通分量：强连通分量：非强连通非强连通图中的极大强连通子图。图中的极大强连通子图。ABECFABECF11生成树：生成树：v1v2v3v4生成森林：生成森林： 假设一个连通图有假设一个连通图有 n n 个顶点和个顶点和 e e 条边，其中条边，其中 n-1 n-1 条边和条边和 n n 个个顶点构成

4、一个极小连通子图，称顶点构成一个极小连通子图，称该极小连通子图为此连通图的生该极小连通子图为此连通图的生成树。成树。由若干棵由若干棵生成树生成树组成，含全部顶点，但构成组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均这些树的边是最少的。（对有向或无向图均适用）适用）12CreatGraph(&G, V, VR)/按定义按定义(V,VR)(V,VR)构造图构造图DestroyGraph(&G) / / 销毁图销毁图结构的建立和销毁结构的建立和销毁对顶点的访问操作对顶点的访问操作LocateVex(G, u) / / 若若G G中存在顶点中存在顶点u u，则返回该顶点，则返回该顶点在

5、图中在图中“位置位置”，否则返回其它信息。，否则返回其它信息。GetVex(G, v) / / 返回返回 v v 的值。的值。PutVex(&G, v, value) / / 对对 v v 赋值赋值valuevalue。结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作遍历遍历插入或删除弧插入或删除弧基本操作基本操作对顶点的访问操作对顶点的访问操作13对邻接点的操作对邻接点的操作FirstAdjVex(G, v); /返回返回v v的的“第一个邻接点第一个邻接点” ” 若该若该顶点在顶点在G G中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAd

6、jVex(G, v, w); /返回返回v v的（相对于的（相对于w w的）的） “ “下下一个邻接点一个邻接点”。若。若w w是是v v的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。插入或删除顶点插入或删除顶点InsertVex(&G, v); /在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G, v)；/删除删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。14插入和删除弧插入和删除弧InsertArc(&G, v, w); / / 在在G G中增添弧中增添弧，若，若G G是是无向的，则还增添对称弧无向的，则还增添对称弧。DeleteArc(&G,

7、v, w); /在在G G中删除弧中删除弧，若，若G G是是无向的，则还删除对称弧无向的，则还删除对称弧。DFSTraverse(G, v, Visit(); /从顶点从顶点v v起深度优先遍历起深度优先遍历图图G G，并对每个顶点调用函数，并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点从顶点v起广度优先遍历图起广度优先遍历图G，并对每个顶点调用函数，并对每个顶点调用函数Visit一次且仅一次。一次且仅一次。遍遍 历历157.2 7.2 图的存储结构图的存储结构图的特点：图的特点：链式存储结构：链式存储结构：顺

8、序存储结构：顺序存储结构： 难！难！ （多个顶点，无序可言，无法仅以（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）顶点坐标表达相互关系）可用可用多重链表多重链表但可但可用用数组数组描述元素间关系。描述元素间关系。非线性结构非线性结构（m :nm :n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原各种表示法成立的原则：存入电脑后能唯则：存入电脑后能唯一复原一复原16 建立一个建立一个顶点表顶点表和一个和一个邻接矩阵邻接矩阵。 , ),( , ,.否否则则或或者者如如果果01AEjiEjijiarcs记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表

9、示各个顶点之间关系 设图设图 A = (A = (V V, , E E ) ) 有有 n n 个顶点，则图的邻接个顶点，则图的邻接矩阵是一个二维数组矩阵是一个二维数组 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顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v418例例2 2 ：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？有向图的邻接矩阵可能

10、是不对称的。有向图的邻接矩阵可能是不对称的。顶点顶点v vi i的出度的出度= =第第i i行元素之和行元素之和; ; 顶点顶点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为头的弧为头的弧(

11、(即入度边）。即入度边）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 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 v1v2v3v4v5v620 容易实现图的操作，如：求某顶点的容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶度、判断顶点之

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

13、顶点数typedef enum DG, DN, UDG,UDN GraphKind; /有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网 21typedef struct ArcCell / / 弧的定义弧的定义 VRType adj; / VRType/ VRType是顶点关系类型。是顶点关系类型。/对无权图对无权图, ,用用1 1或或0 0表示相邻否；对带权图，则为权值类型表示相邻否；对带权图，则为权值类型。 InfoType *info; / / 该弧相关该弧相关信息的指针信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM

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

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

16、V2V12301邻接表邻接表( (出边出边) )V4V3V2V13020逆邻接表逆邻接表( (入边入边) )01230123在有向图的邻接表中不易找到指向该顶点的弧。在有向图的邻接表中不易找到指向该顶点的弧。OD(Vi)=邻接表中邻接表中Vi链接的结点数链接的结点数ID(Vi)=逆邻接表中逆邻接表中Vi i链接的结点数链接的结点数TD(Vi) = OD( Vi ) + ID( Vi )25例例3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存储结构形成后，图便成后，图便唯一确定！唯一确定！26分析分析1：对于

17、对于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+e)O(n+e)。若是稀疏图，则比。若是稀疏图，则比邻接矩阵表示法合适。邻接矩阵

18、表示法合适。它其实是对邻接矩阵法的一种它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧改进，两个结点表示一条边或弧邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点： 空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵两结点对应的单链表，没有邻接矩阵方便。方便。27讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元

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

20、用于稀疏图的存储（enen2 2) )28图的邻接表在机内如何表示？图的邻接表在机内如何表示？ （参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct ArcNode /弧结构弧结构 int adjvex; /该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针该弧相关信息的指针 ArcNode；29Typedef struct /图结构图结构 AdjList ver

21、tics ; /应包含邻接表应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph; Typedef struct VNode /顶点结构顶点结构 VertexType data; /顶点信息顶点信息 ArcNode * firstarc; /指向第一条依附该顶点指向第一条依附该顶点的弧的指针的弧的指针VNode, AdjList MAX_VERTEX_NUM ; /邻接表邻接表 30 它是它是有向图有向图的另一种链式存储结构。的另一种链式存储结构。 思路：思

22、路：将邻接矩阵用链表存储，是邻接表、逆邻接表将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。的结合。(1)(1)开设弧结点，设开设弧结点，设5 5个域（每段弧是一个数据元素）个域（每段弧是一个数据元素）(2)(2)开设顶点结点，设开设顶点结点，设3 3个域（每个顶点也是一个数据个域（每个顶点也是一个数据元素）元素）tailvex headvex hlinktlinkinfo弧结点弧结点tailvex: 弧尾顶点位置弧尾顶点位置 headvex: 弧头顶点位置弧头顶点位置hlink: 弧头相同的下一弧位置弧头相同的下一弧位置tlink: 弧尾相同的下一弧位置弧尾相同的下一弧位置info: 弧信息

23、弧信息31 data : 顶点信息顶点信息firstin : 以顶点为弧头的第以顶点为弧头的第一条弧结点一条弧结点firstout: 以顶点为弧尾的第以顶点为弧尾的第一条弧结点一条弧结点问：问：n n个顶点的集合怎样储存？个顶点的集合怎样储存？顺序存储结构顺序存储结构data firstinfirstout顶点结点顶点结点十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。32ABCABC0 1 20 2 0 12 1 2 0 例：画出有向图的十字链表。例：画出有

24、向图的十字链表。tailvex headvex hlinktlink弧结点弧结点data firstinfirstout顶点结点顶点结点33这是这是无向图无向图的另一种链式存储结构，当对边操作时建的另一种链式存储结构，当对边操作时建议采用此种结构存储。议采用此种结构存储。（1 1）设立边结点，）设立边结点， 6 6个域（每条边是一个数据元素）个域（每条边是一个数据元素）（2 2）设立顶点结点，）设立顶点结点， 2 2个域（每个顶点也是一个数据个域（每个顶点也是一个数据元素）元素）mark ivex ilink jvexjlink info边结点边结点4. 4. 邻接多重表表示法邻接多重表表示法

25、mark：标志域，标记该边是否被搜索过。标志域，标记该边是否被搜索过。ivex， jvex : 边依附的两个顶点位置边依附的两个顶点位置 ilink: 指向下一条依附顶点指向下一条依附顶点 i i 的边位置的边位置Jlink： 指向下一条依附顶点指向下一条依附顶点 j j 的边位置的边位置info: 边信息边信息34 data : 存储顶点信息存储顶点信息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)