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

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

1、会计学1图的定义和术语及存储结构图的定义和术语及存储结构27.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的连通性7.5 图的应用第第第第7 7 7 7章章章章 图图图图第1页/共35页37.1 7.1 7.1 7.1 图的基本术语图的基本术语图的基本术语图的基本术语其中：V 是G 的顶点集合，是有穷非空集；VR|v,wV 且 P(v,w),是有穷集.问：当VR 为空时，图G存在否？V=vertex 图：记为 Graph(V,VR)EACBD表示从 v 到 w 的一条弧，并称 w 为弧头，v 为弧尾。P(v,w)定义了弧 的意义或信息。答：还存在！但此时图G只有顶点。第2页/共35页

2、4EACBD例如:G=(V,VR)其中V=A,B,C,D,EVR=,无向图：由顶点集和边集构成的图(“边”无方向）若VR 必有VR,则称(v,w)为顶点 v 和顶点 w 之间存在一条边。有向图：由顶点集和弧集构成的图（“弧”是有方向的）第3页/共35页5BCAFED例如:G=(V,VR)其中：V=A,B,C,D,E,FVR=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)v若 n 个顶点的无向图有 n(n-1)/2 条边,称为无向完全图v若 n 个顶点的有向图有n(n-1)条边,称为有向完全图证明：有向完全图有有向完全图有n n(n n-1)-1)条边条边。证

3、明：若是有向完全图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数=n(n-1)1234第4页/共35页6证明：从可以直接推论出无向完全图的边数因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。无向完全图有无向完全图有n n(n n-1)/2-1)/2 条边条边。1234例：判断下列4种图形各属什么类型？第5页/共35页7稀疏图：稀疏图：稀疏图：稀疏图：稠密图：稠密图：稠密图：稠密图：设有两个图 G(V,E)和 G(V,E)。若 V V 且 E E,则称 图G 是 图G 的子图。子 图：边较少的图。通常边数远少于nlognnlogn边很多的图。无向图中，边数

4、接近n n(n n-1)/2-1)/2 有向图中，边数接近n n(n n-1)-1)BBCABECFABECF例如：第6页/共35页8ABECF1597211132有向网或无向网是弧或边带权的图。邻接点：若边(v,w)VR，则顶点v 和顶点w 互为邻接点。边(v,w)依附于顶点v 和w，或者与顶点v,w相关联。顶点v的度：是和v 相关联的边的数目,记为TD(v).顶点v的出度:以顶点v 为尾的弧的数目;记为OD(v).顶点v的入度:以顶点v 为头的弧的数目,记为ID(v).顶点的度(TD)=出度(OD)+入度(ID)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是

5、树！而且是一棵有向树！第7页/共35页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 之间存在一条路径。路径长度：路径上边（或弧）的数目。ABECF如:从A到F长度为 3 的路径A,B,C,F或A，E，C，F简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。第8页/共35页10连通图：无向图G中任意两个顶点之间都有路径相连通。连通分量：非连通图中的极大连通子图。BACDFEBACDFE强连通图：在有

6、向图中,每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径强连通分量：非强连通图中的极大强连通子图。ABECFABECF第9页/共35页11生成树：v1v2v3v4生成森林：假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）第10页/共35页12CreatGraph(&G,V,VR)/按定义(V,VR)构造图DestroyGraph(&G)/销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u)/若G中存在

7、顶点u，则返回该顶点在图中“位置”，否则返回其它信息。GetVex(G,v)/返回 v 的值。PutVex(&G,v,value)/对 v 赋值value。结构的建立和销毁插入或删除顶点对邻接点的操作遍历插入或删除弧基本操作对顶点的访问操作第11页/共35页13对邻接点的操作FirstAdjVex(G,v);/返回v的“第一个邻接点”若该顶点在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);/返回v的（相对于w的）“下一个邻接点”。若w是v的最后一个邻接点，则返回“空”。插入或删除顶点InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v)；/删

8、除G中顶点v及其相关的弧。第12页/共35页14插入和删除弧InsertArc(&G,v,w);/在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse(G,v,Visit();/从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。遍 历第13页/共35页157.2 7.2 7.2 7.2 图的存储结构图的存储结构图的存储结构图的存储结构图的特点：图的特点：图的

9、特点：图的特点：链式存储结构：顺序存储结构：难！（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）可用多重链表1.1.邻接矩阵邻接矩阵(数组数组)表示法表示法2.2.邻接表邻接表(链式链式)表示法表示法3.3.十字链表十字链表表示法表示法4.4.邻接多重表邻接多重表表示法表示法但可用数组描述元素间关系。非线性结构（m:n）邻接矩阵邻接表十字链表邻接多重表各种表示法成立的原则：存入电脑后能唯一复原第14页/共35页16 建立一个顶点表和一个邻接矩阵。1.1.1.1.邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法记录各个顶点信息表示各个顶点之间关系 设图

10、 A=(V,E)有 n 个顶点，则图的邻接矩阵是一个二维数组 A.arcsnn，定义为：第15页/共35页17分析分析1 1：无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；分析分析2 2：顶点顶点i i 的度的度第第 i i 行行(列列)中中1 1 的个数的个数；特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为0 0，其余全，其余全1 1。例例1 1：邻接矩阵：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顶点表：无向图的邻接矩阵如何表示？v1v2v3v

11、5v4v4A A第16页/共35页18例例例例2 2 2 2：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？分析分析1 1：有向图的邻接矩阵可能是不对称的。分析分析2 2：顶点vi的出度=第i行元素之和;顶点vi的入度=第i列元素之和;顶点的度=第i行元素之和+第i列元素之和。v1v2v3v4A A邻接矩阵：A.arcs=(v1 v2 v3 v4)v1v2v3v4注：注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第j列含义：以结点vj为头的弧(即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1

12、 1 0 0 0 第17页/共35页19例例例例3 3 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第18页/共35页20 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*nn*n个单元存储边(弧)

13、;空间效率为O(n2 2)。邻接矩阵法优点：邻接矩阵法缺点：对稀疏图而言尤其浪费空间。图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？（参见教材（参见教材（参见教材（参见教材P161P161P161P161）注：用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数typedef enum DG,DN,UDG,UDN GraphKind;/有向图，有向网，无向图，无向网第19页/共35页21typedef struct Ar

14、cCell /弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图,用1或0表示相邻否；对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;第20页/共35页222.2.2.2.邻接表（链式）表示

15、法邻接表（链式）表示法邻接表（链式）表示法邻接表（链式）表示法 对每个顶点对每个顶点v vi i 建立一个建立一个单链表单链表，把与，把与v vi i有关联的有关联的边边（或以（或以v vi i为尾的弧为尾的弧)的信息链接的信息链接起来，表中每个结点起来，表中每个结点都设为都设为3 3个域。个域。每个单链表还应当附设一个每个单链表还应当附设一个表头结点表头结点（设为（设为2 2个域），个域），存存v vi i信息；信息；adjvexnextarcinfodatafirstarc表结点表结点头结点头结点邻接点域，表示vi 邻接点的位置链域，指向下一条边或弧的结点数据域，存储顶点vi 信息链域，指

16、向单链表的第一个结点 每个单链表的每个单链表的头结点另外用顺序存储结构头结点另外用顺序存储结构存储。存储。边或弧的信息第21页/共35页23例例例例1 1 1 1：无向图的邻接表如何表示？：无向图的邻接表如何表示？：无向图的邻接表如何表示？：无向图的邻接表如何表示？v1v2v3v5v4v4邻接表：0123413341420请注意：邻接表不唯一！因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v1邻接点v4的位置此无权图未开第3分量TD(Vi)=单链表中Vi链接的结点个数第22页/共35页24例2：有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301邻接表(出边)V4

17、V3V2V13020逆邻接表(入边)01230123在有向图的邻接表中不易找到指向该顶点的弧。OD(Vi)=邻接表中Vi链接的结点数ID(Vi)=逆邻接表中Vi链接的结点数TD(Vi)=OD(Vi)+ID(Vi)第23页/共35页25例例例例3 3 3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储结构形成后，图便唯一确定！第24页/共35页26分析1：对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2

18、e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点：邻接表存储法的特点：邻接表存储法的特点：邻接表存储法的特点：分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。第25页/共35页27讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表

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

20、）#define MAX_VERTEX_NUM 20 /假设的最大顶点数Typedef struct ArcNode /弧结构 int adjvex;/该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针 InfoArc *info;/该弧相关信息的指针 ArcNode；第27页/共35页29Typedef struct /图结构 AdjList vertics;/应包含邻接表 int vexnum,arcnum;/应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）ALGraph;Typedef struct VNode /顶点结构 V

21、ertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjList MAX_VERTEX_NUM;/邻接表 第28页/共35页30 它是有向图的另一种链式存储结构。思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。(1)开设弧结点，设5个域（每段弧是一个数据元素）(2)开设顶点结点，设3个域（每个顶点也是一个数据元素）tailvex headvex hlinktlinkinfo弧结点3.3.3.3.十字链表表示法十字链表表示法十字链表表示法十字链表表示法tailvex:弧尾顶点位置 headvex:弧头顶点位置hlink

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

23、ktlink弧结点data firstinfirstout顶点结点第31页/共35页33这是无向图的另一种链式存储结构，当对边操作时建议采用此种结构存储。（1）设立边结点，6个域（每条边是一个数据元素）（2）设立顶点结点，2个域（每个顶点也是一个数据元素）mark ivex ilink jvex jlink info边结点4.4.4.4.邻接多重表表示法邻接多重表表示法邻接多重表表示法邻接多重表表示法mark：标志域，标记该边是否被搜索过。ivex，jvex:边依附的两个顶点位置 ilink:指向下一条依附顶点 i 的边位置Jlink：指向下一条依附顶点 j 的边位置info:边信息第32页/

24、共35页34 data :存储顶点信息firstedge:依附顶点的第一条边结点data firstedge顶点结点问:n个顶点的集合怎样储存？仍用顺序存储结构邻接多重表优点：容易操作，如求顶点的度,对边操作等。空间复杂度和建表的时间复杂度都与邻接表相同。第33页/共35页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)第34页/共35页