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

图的定义和术语及存储结构第1页，共35页，编辑于2022年，星期五17.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 图的应用图的应用第第7 7章章 图图第2页，共35页，编辑于2022年，星期五27.1 7.1 图的基本术语图的基本术语其中：其中：V V 是是G G 的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；VRVR|v,wV|v,wV 且且 P(v,w),P(v,w),是有穷集是有穷集.问：问：当当VR VR 为空时，图为空时，图G G存在否？存在否？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只有顶点。只有顶点。第3页，共35页，编辑于2022年，星期五3E EA AC CB BD D例如例如:G=(V,VR)G=(V,VR)其中其中V=A,B,C,D,EV=A,B,C,D,EVR=,VR=,无向图：无向图：由顶点集和边集构成的图由顶点集和边集构成的图(“(“边边”无方向）无方向）若若 VR VR 必有必有 VR,VR,则称则称 (v,w)(v,w)为顶点为顶点 v v 和顶点和顶点 w w 之间存在一条边。之间存在一条边。有向图：有向图：由顶点集和弧集构成的图由顶点集和弧集构成的图（“弧弧”是有方向的）是有方向的）第4页，共35页，编辑于2022年，星期五4BCAFED例如例如: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,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 n n(n n n n-1)-1)-1)-1)条边条边条边条边。证明：证明：若是有向完全图，则若是有向完全图，则n个顶点中的每个顶点中的每个顶点都有一条弧指向其它个顶点都有一条弧指向其它n-1个顶点个顶点,因因此总边数此总边数=n(n-1)1234第5页，共35页，编辑于2022年，星期五5证明：证明：从从可以直接推论出无向完全图的边可以直接推论出无向完全图的边数数因为无方向，两弧合并为一边，所以边因为无方向，两弧合并为一边，所以边数减半，总边数为数减半，总边数为n(n-1)/2。无向完全图有无向完全图有n n n n(n n-1)/2-1)/2 条边条边条边条边。1234例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？第6页，共35页，编辑于2022年，星期五6稀疏图：稀疏图：稠密图：稠密图：设有两个图设有两个图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。子子 图：图：边较少的图。通常边数远少于边较少的图。通常边数远少于nlognnlogn边很多的图。边很多的图。无向图中，边数接近无向图中，边数接近n n(n n-1)/2-1)/2 有向图中，边数接近有向图中，边数接近n n(n n-1)-1)BBCABECFABECF例如：例如：第7页，共35页，编辑于2022年，星期五7ABECF1597211132有向网有向网或或无向网无向网是弧或边带权的图是弧或边带权的图。邻接点：邻接点：若边若边(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 为尾的弧的数目为尾的弧的数目;记为记为OD(v)OD(v).顶点顶点v v的入度的入度:以顶点以顶点v v 为头的弧的数目为头的弧的数目,记为记为ID(v)ID(v).顶点的度顶点的度(TD)=(TD)=出度出度(OD)+(OD)+入度入度(ID)(ID)问：当有向图中仅问：当有向图中仅1 1个顶点的入度个顶点的入度为为0,0,其余顶点的入度均为其余顶点的入度均为1 1，此时是何形状？，此时是何形状？答：是树！而答：是树！而且是一棵有向且是一棵有向树！树！第8页，共35页，编辑于2022年，星期五8路径路径:设图设图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-i,j-1 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页，共35页，编辑于2022年，星期五9连通图：连通图：无向无向图图G G中任意两中任意两个顶点之间都有路径相连通。个顶点之间都有路径相连通。连通分量：连通分量：非连通图中的非连通图中的极大连通子图。极大连通子图。BACDFEBACDFE强连通图：强连通图：在有向图中在有向图中,每一对顶点每一对顶点v vi i和和v vj j,都存在都存在一条从一条从v vi i到到v vj j和从和从v vj j到到v vi i的的路径路径强连通分量：强连通分量：非强连通图非强连通图中的极大强连通子图。中的极大强连通子图。ABECFABECF第10页，共35页，编辑于2022年，星期五10生成树：生成树：v1v2v3v4生成森林：生成森林：假设一个连通图有假设一个连通图有 n n 个顶点和个顶点和 e e 条边，其中条边，其中 n-1 n-1 条边和条边和 n n 个顶点构个顶点构成一个极小连通子图，称该极小连通成一个极小连通子图，称该极小连通子图为此连通图的生成树。子图为此连通图的生成树。由若干棵由若干棵生成树生成树组成，含全部顶点，但构成这些树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）的边是最少的。（对有向或无向图均适用）第11页，共35页，编辑于2022年，星期五11CreatGraph(&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页，共35页，编辑于2022年，星期五12对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回返回v v的的“第一个邻接点第一个邻接点”若该顶点在若该顶点在G G中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVex(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及其相关的弧。及其相关的弧。第13页，共35页，编辑于2022年，星期五13插入和删除弧插入和删除弧InsertArc(&G,v,w);/在在G G中增添弧中增添弧，若，若G G是无向的，是无向的，则还增添对称弧则还增添对称弧。DeleteArc(&G,v,w);/在在G G中删除弧中删除弧，若，若G G是无向是无向的，则还删除对称弧的，则还删除对称弧。DFSTraverse(G,v,Visit();/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个顶点调用函数，并对每个顶点调用函数VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G,v,Visit();/从顶点从顶点v起广度优先遍历图起广度优先遍历图G，并，并对每个顶点调用函数对每个顶点调用函数Visit一次且仅一次。一次且仅一次。遍遍 历历第14页，共35页，编辑于2022年，星期五147.2 7.2 图的存储结构图的存储结构图的特点：图的特点：链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：难！难！（多个顶点，无序可言，无法仅以（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）顶点坐标表达相互关系）可用可用多重链表多重链表1.1.邻接矩阵邻接矩阵(数组数组)表示法表示法2.2.邻接表邻接表(链式链式)表示法表示法3.十字链表十字链表表示法表示法4.邻接多重表邻接多重表表示法表示法但可但可用用数组数组描述元素间关系。描述元素间关系。非线性结构非线性结构（m:nm:n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原各种表示法成立的原则：存入电脑后能唯则：存入电脑后能唯一复原一复原第15页，共35页，编辑于2022年，星期五15 建立一个建立一个顶点表顶点表和一个和一个邻接矩阵邻接矩阵。1.1.1.1.邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法邻接矩阵（数组）表示法记录各个顶点信息记录各个顶点信息表示各个顶点之间关系表示各个顶点之间关系 设图设图 A=(A=(V V,E E)有有 n n 个顶点，则图的邻接矩阵个顶点，则图的邻接矩阵是一个二维数组是一个二维数组 A A.arcs.arcs n nn n，定义为：，定义为：第16页，共35页，编辑于2022年，星期五16分析分析分析分析1 1 1 1：无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；分析分析分析分析2 2 2 2：顶点顶点i i i i 的度的度的度的度第第 i i i i 行行行行(列列列列)中中中中1 1 的个数的个数；特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为特别：完全图的邻接矩阵中，对角元素为0 0 0 0，其余全，其余全，其余全，其余全1 1 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顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v4A第17页，共35页，编辑于2022年，星期五17例例2 2：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？分析分析分析分析1 1 1 1：有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。分析分析分析分析2 2 2 2：顶点顶点v vi i的出度的出度=第第i i行元素之和行元素之和;顶点顶点v vi i的入度的入度=第第i i列元素之和列元素之和;顶点的度顶点的度=第第i i行元素之和行元素之和+第第i i列元素之和。列元素之和。v1v2v3v4A邻接矩阵：邻接矩阵：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页，共35页，编辑于2022年，星期五18例例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第19页，共35页，编辑于2022年，星期五19 容易实现图的操作，如：求某顶点的度、判容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点断顶点之间是否有边（弧）、找顶点的邻接点等等。等等。n n个顶点需要个顶点需要n*nn*nn*nn*n个单元存储边个单元存储边(弧弧););空间效空间效率为率为O(O(n n2 2 2 2)。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：对稀疏图而言尤其对稀疏图而言尤其浪费空间。浪费空间。图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？（参见教材（参见教材P161P161）注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数typedef enum DG,DN,UDG,UDN GraphKind;/有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网 第20页，共35页，编辑于2022年，星期五20typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType/VRType是顶点关系类型。是顶点关系类型。/对无权图对无权图,用用1 1或或0 0表示相邻否；对带权图，则为权值类型表示相邻否；对带权图，则为权值类型。InfoType *info;/该弧相关该弧相关信息的指针信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrix arcs;/邻接矩阵邻接矩阵 int vexnum,arcnum;/顶点数，弧数顶点数，弧数 GraphKind kind;/图的种类标志图的种类标志 MGraph;第21页，共35页，编辑于2022年，星期五212.2.邻接表（链式）表示法邻接表（链式）表示法 对每个顶点对每个顶点对每个顶点对每个顶点vi i 建立一个建立一个建立一个建立一个单链表单链表，把与，把与，把与，把与vi i有关联的有关联的边（或以边（或以边（或以边（或以v vi为尾的弧为尾的弧为尾的弧为尾的弧)的信息链接的信息链接起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为3 3个域。个域。个域。个域。每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个表头结点表头结点（设为（设为2 2 2 2个域），存个域），存v v v vi i信息；信息；信息；信息；adjvexnextarcinfodatafirstarc表结点表结点头结点头结点邻接点域，表邻接点域，表示示v vi i 邻接点邻接点的位置的位置链域，链域，指向指向下一条边或下一条边或弧的结点弧的结点数据域，数据域，存储顶点存储顶点v vi i 信息信息链域，链域，指向指向单链表的第一单链表的第一个结点个结点 每个单链表的每个单链表的头结点另外用顺序存储结构头结点另外用顺序存储结构存储。存储。存储。存储。边或弧的信息边或弧的信息第22页，共35页，编辑于2022年，星期五22例例1 1：无向图的邻接表如何表示？：无向图的邻接表如何表示？v1v2v3v5v4v4邻接表：邻接表：0123413341420请注意：邻接表不唯一！因各请注意：邻接表不唯一！因各个边结点的链入顺序是任意的。个边结点的链入顺序是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4的位置的位置此无权图未开第此无权图未开第3 3分量分量TD(Vi)=单链表中单链表中V Vi i链接的结点个数链接的结点个数第23页，共35页，编辑于2022年，星期五23例例2 2：有向图的邻接表如何表示？：有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)01230123在有向图的邻接表中不易找到指向该顶点的弧。在有向图的邻接表中不易找到指向该顶点的弧。OD(Vi)=邻接表中邻接表中Vi链接的结点数链接的结点数ID(Vi)=逆邻接表中逆邻接表中Vi i链接的结点数链接的结点数TD(Vi)=OD(Vi)+ID(Vi)第24页，共35页，编辑于2022年，星期五24例例3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存储结构形成后，图便成后，图便唯一确定！唯一确定！第25页，共35页，编辑于2022年，星期五25分析分析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+e)O(n+e)。若是稀疏图，则比邻接矩阵表示。若是稀疏图，则比邻接矩阵表示法合适。法合适。它其实是对邻接矩阵法的一种改它其实是对邻接矩阵法的一种改进，两个结点表示一条边或弧进，两个结点表示一条边或弧邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。第26页，共35页，编辑于2022年，星期五26讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但顶点编号一致），但邻接表不唯一邻接表不唯一（链接次序与顶点编（链接次序与顶点编号无关）。号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂度为而邻接表的空间复杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)第27页，共35页，编辑于2022年，星期五27图的邻接表在机内如何表示？图的邻接表在机内如何表示？（参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef struct ArcNode /弧结构弧结构 int adjvex;/该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针指向下一条弧的指针 InfoArc *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode；第28页，共35页，编辑于2022年，星期五28Typedef struct /图结构图结构 AdjList vertics;/应包含邻接表应包含邻接表 int vexnum,arcnum;/应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph;Typedef struct VNode /顶点结构顶点结构 VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧的指针的指针VNode,AdjList MAX_VERTEX_NUM;/邻接表邻接表 第29页，共35页，编辑于2022年，星期五29 它是它是有向图有向图的另一种链式存储结构。的另一种链式存储结构。思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。合。(1)(1)开设弧结点，设开设弧结点，设5 5个域（每段弧是一个数据元素）个域（每段弧是一个数据元素）(2)(2)开设顶点结点，设开设顶点结点，设3 3个域（每个顶点也是一个数据元素）个域（每个顶点也是一个数据元素）tailvex headvex hlinktlinkinfo弧结点弧结点3.3.3.3.十字链表表示法十字链表表示法十字链表表示法十字链表表示法tailvex:弧尾顶点位置弧尾顶点位置 headvex:弧头顶点位置弧头顶点位置hlink:弧头相同的下一弧位置弧头相同的下一弧位置tlink:弧尾相同的下一弧位置弧尾相同的下一弧位置info:弧信息弧信息第30页，共35页，编辑于2022年，星期五30 data :顶点信息顶点信息firstin :以顶点为弧头的第一以顶点为弧头的第一条弧结点条弧结点firstout:以顶点为弧尾的第一条以顶点为弧尾的第一条弧结点弧结点问：问：n n个顶点的集合怎样储存？个顶点的集合怎样储存？顺序存储结构顺序存储结构data firstinfirstout顶点结点顶点结点十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。第31页，共35页，编辑于2022年，星期五31ABCABC0 1 20 2 0 12 1 2 0 例：画出有向图的十字链表。例：画出有向图的十字链表。tailvex headvex hlinktlink弧结点弧结点data firstinfirstout顶点结点顶点结点第32页，共35页，编辑于2022年，星期五32这是这是无向图无向图的另一种链式存储结构，当对边操作时建议采用此的另一种链式存储结构，当对边操作时建议采用此种结构存储。种结构存储。（1 1）设立边结点，）设立边结点，6 6个域（每条边是一个数据元素）个域（每条边是一个数据元素）（2 2）设立顶点结点，）设立顶点结点，2 2个域（每个顶点也是一个数据元素）个域（每个顶点也是一个数据元素）mark ivex ilink jvexjlink info边结点边结点4.4.邻接多重表表示法邻接多重表表示法mark：标志域，标记该边是否被搜索过。标志域，标记该边是否被搜索过。ivex，jvex:边依附的两个顶点位置边依附的两个顶点位置 ilink:指向下一条依附顶点指向下一条依附顶点 i i 的边位置的边位置Jlink：指向下一条依附顶点指向下一条依附顶点 j j 的边位置的边位置info:边信息边信息第33页，共35页，编辑于2022年，星期五33 data :存储顶点信息存储顶点信息firstedge:依附顶点的第一条依附顶点的第一条边结点边结点data firstedge顶点结点顶点结点问问:n n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度容易操作，如求顶点的度,对边操作对边操作等。等。空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。第34页，共35页，编辑于2022年，星期五34v1v2v3v5v4v4例：画出无向图的邻接多重表。例：画出无向图的邻接多重表。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)第35页，共35页，编辑于2022年，星期五35