数据结构第次课图精.ppt

《数据结构第次课图精.ppt》由会员分享，可在线阅读，更多相关《数据结构第次课图精.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第次课图1第1页，本讲稿共41页数据结构课程的内容数据结构课程的内容多对多多对多（m:n)2第2页，本讲稿共41页7.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用第第7 7章章 图图3第3页，本讲稿共41页7.1 7.1 图的基本术语图的基本术语图：图：记为记为 G(V,E)其中：其中：V 是是G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E 是是G的边的边集合，是有穷集。集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答

2、：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；v v若若若若 n n 个顶点的无向图有个顶点的无向图有个顶点的无向图有个顶点的无向图有 n n(n n-1)/2-1)/2 条边条边条边条边,称为称为称为称为无向完全图无向完全图无向完全图无向完全图v v若若若若 n n 个顶点的有向图有个顶点的有向图有个顶点的有向图有个顶点的有向图

3、有n n(n-n-1)1)条边条边条边条边,称为称为称为称为有向完全图有向完全图有向完全图有向完全图V=vertex E=edge4第4页，本讲稿共41页例：例：判断下列判断下列4种图形各属什么类型？种图形各属什么类型？无向无向图(树)有向图有向n n(n n-1)/2-1)/2 条边条边条边条边n n(n n-1)-1)条边条边条边条边G1G1的顶点集合为的顶点集合为V(G1)V(G1)=0,1,2,3=0,1,2,3边集合为边集合为E(G1)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,

4、3)完全图完全图完全图完全图5第5页，本讲稿共41页稀疏图：边较少的图。通常边数边较少的图。通常边数n2子 图：设有两个图设有两个图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。稠密图：边很多的图。无向图中，边数接近边很多的图。无向图中，边数接近n n(n n-1)/2-1)/2 ；有向图中，边数接近有向图中，边数接近n n(n n-1)-1)带权图：带权图：即边上带权的图。其中即边上带权的图。其中权权是指每条边可以标上具有某是指每条边可以标上具有某种含义的数值（即与边相关的数）。种含义的数值（即与边相关的数）。网网 络：络：带

5、权图带权图6第6页，本讲稿共41页简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不均不互相重复互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，则称这样重合，则称这样的路径为的路径为回路或环回路或环。路径：在图在图在图在图 G G(V V,E E)中中中中,若从顶点若从顶点若从顶点若从顶点 v vi i 出发出发出发出发,沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点沿一些边经过一些顶点 v vp p1 1,v vp p2 2,v vpmpm，到达顶点，到达顶点，

6、到达顶点，到达顶点v vj j。则称顶点序列。则称顶点序列。则称顶点序列。则称顶点序列 (v vi i v vp p1 1 v vp p2 2.v vpm pm v vj j)为从顶点为从顶点为从顶点为从顶点v vi i 到顶点到顶点到顶点到顶点 v vj j 的的的的路径路径路径路径。它经过的边。它经过的边。它经过的边。它经过的边(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)应当是属于应当是属于应当是属于应当是属于E E的边。的边。的边。的边。路径长度：非带权图的路径长度是指此路径非带权图的路径长度是指此路径非带权图的路

7、径长度是指此路径非带权图的路径长度是指此路径上边的条数上边的条数上边的条数上边的条数；带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和各边的权之和各边的权之和各边的权之和。7第7页，本讲稿共41页例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5(路径上结点数-1)简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，18第8页，本讲稿共41

8、页弧头和弧尾：有向边有向边(u,v)称为弧，边的始点称为弧，边的始点u叫叫弧尾弧尾，终点，终点v叫叫弧头弧头 顶点顶点v的度的度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)。在在有向图有向图中中,顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数,记作记作 OD(v)。邻接顶点：若若(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互为互为邻接顶点

9、邻接顶点度、入度和出度：问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的入度均其余顶点的入度均为为1 1，此时是何形状？，此时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！9第9页，本讲稿共41页生成树：生成树：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有n n-1-1条边条边条边条边。v v如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定

10、构成一个环。条边，必定构成一个环。条边，必定构成一个环。v v若图中有若图中有若图中有若图中有n n个顶点，却少于个顶点，却少于个顶点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。条边，必为非连通图。生成森林：生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少由若干棵生成树组成，含全部顶点，但构成这些树的边是最少由若干棵生成树组成，含全部顶点，但构成这些树的边是最少由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。的。的。的。V1V2V4V5V3V7V6V8例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8

11、10第10页，本讲稿共41页连连 通通 图：图：在在在在无向无向无向无向图中图中图中图中,若从顶点若从顶点若从顶点若从顶点v v1 1到顶点到顶点到顶点到顶点v v2 2有路径有路径有路径有路径,则称顶点则称顶点则称顶点则称顶点v v1 1与与与与v v2 2是是是是连通连通连通连通的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的,则称此图则称此图则称此图则称此图是是是是连通图连通图连通图连通图。非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图非连通图的极大连通子图叫做叫做叫做叫做连通分量

12、连通分量连通分量连通分量。在在在在有向有向有向有向图中图中图中图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点v vi i和和和和v vj j,都存在一条从都存在一条从都存在一条从都存在一条从v vi i到到到到v vj j和和和和从从从从v vj j到到到到v vi i的路径的路径的路径的路径,则称此图是则称此图是则称此图是则称此图是强连通图强连通图强连通图强连通图。非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做叫做叫做强连通分量强连通分量强连通分量强连通分量。强连通图：强连通图：有两类图形不在本章有两类

13、图形不在本章讨论之列：讨论之列：连通图245136强连通图356536非连通图连通分量11第11页，本讲稿共41页ADT Graph 数据对象数据对象V：v v是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R：R=VRR=VR；VR=VR=|v,wV|v,wV 且且 P(v,w)P(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作基本操作P：CreatGraph(G,V,VR);初始条件：初始条件：V V是图的顶点是图的顶点集集，VRVR是图中弧的集合。

14、是图中弧的集合。操作结果：操作结果：按按V V和和VRVR的定义构造图的定义构造图G G。InsertVex(G,v);初始条件：初始条件：图图G G存在，存在，v v和图中顶点有相同特征。和图中顶点有相同特征。操作结果：操作结果：在图在图G G中添加新顶点。中添加新顶点。（参见（参见P135-136P135-136）图的抽象数据类型图的抽象数据类型注意：V 的大小写含义不同！12第12页，本讲稿共41页7.2 7.2 图的存储结构图的存储结构图的特点：非线性结构（图的特点：非线性结构（m:n m:n）邻接表邻接表邻接多重表邻接多重表十字链表十字链表设计为邻接矩阵链式存储结构：链式存储结构：顺

15、序存储结构：顺序存储结构：无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可但可用用数组数组数组数组描述元素间关系。描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍：邻接矩阵邻接矩阵(数组数组)表示法表示法邻接表邻接表(链式链式)表示法表示法13第13页，本讲稿共41页一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法v v建立一个建立一个建立一个建立一个顶点表顶点表顶点表顶点表（记录各个顶点信息）（记录各个顶点信息）（记录各个顶点信息）（记录各个顶点信息）和一个和一个和一个和一个邻接矩阵邻接矩阵邻接矩阵邻接矩阵（表示各个（

16、表示各个（表示各个（表示各个顶点之间关系）顶点之间关系）顶点之间关系）顶点之间关系）。v v设图设图设图设图 A=(A=(V V,E E)有有有有 n n 个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组 A A.Edge.Edge n n n n，定义为：，定义为：，定义为：，定义为：v1v2v3v5v4v4A例例例例1 1：邻接矩阵：A.Edge=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分

17、析分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是无向图的邻接矩阵是对称对称对称对称的的的的，对角元素为对角元素为对角元素为对角元素为0 0；分析分析分析分析2 2：顶点顶点顶点顶点i i 的的的的度度度度第第第第 i i 行行行行(列列列列)中中中中1 1 的个数；的个数；的个数；的个数；特别：特别：特别：特别：完全图完全图完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全，其余全，其余全1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1

18、 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：14第14页，本讲稿共41页例例2：有向图的邻接矩阵有向图的邻接矩阵分析分析分析分析1 1 1 1：有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。分析分析分析分析2 2 2 2：顶点的顶点的出度出度=第第i i行元素之和行元素之和，OD(Vi)=A.Edge i j 顶点的顶点的入度入度=第第i i列元素之和列元素之和。ID(Vi)=A.Edge j i 顶点的顶点的度度=第第i i行元素之和行元素之和+第第i i列元素之和列元素之和,即：即：TD(Vi)=OD(Vi)+ID(Vi)v

19、1v2v3v4A A邻接矩阵：A.Edge=(v1 v2 v3 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行行含义含义：以结点：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列列含义含义：以结点：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 15第15页，本讲稿共41页 容易实现图的操作，如：求某顶点的度、判断顶点之间是否容

20、易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。特别讨论特别讨论：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义为：A.Edge i j=Wij 或（或（vi,vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：N.Edge=(v1 v2 v3 v4 v5 v6 )邻接矩阵法邻接矩阵法

21、优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 16第16页，本讲稿共41页关联矩阵表示顶点与边的关联关系的矩阵定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵例15324G2123456432156A i j=1 i 顶点与顶点与j 边相连边相连0 i 顶点与顶点与j 边不相连边不相连对无向图：对无向图：17第17页，本讲稿共41页A i j=1 i 顶点与顶点与j 边相连边相连,且且i为尾为尾0 i 顶点与顶点与j 边不相连边不相连-1 i 顶点与顶点与j 边相连

22、边相连,且且i为头为头对有向图：对有向图：例BDAC123456ABCD43215618第18页，本讲稿共41页4321例G124131234特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中“1”的个数顶点Vi的入度是A中第i行中“-1”的个数19第19页，本讲稿共41页二、邻接表（链式）表示法二、邻接表（链式）表示法二、邻接表（链式）表示法二、邻接表（链式）表示法v v对每个顶点对每个顶点对每个顶点对每个顶点v vi i 建立一个建立一个建立一个建立一个单链表单链表单链表单链

23、表，把与，把与，把与，把与v vi i有关联的有关联的有关联的有关联的边的信息边的信息边的信息边的信息（即度或出度（即度或出度（即度或出度（即度或出度边）边）边）边）链接链接链接链接起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为起来，表中每个结点都设为3 3个域；个域；个域；个域；v v每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个每个单链表还应当附设一个头结点头结点头结点头结点（设为（设为（设为（设为2 2个域），存个域），存个域），存个域），存v vi i信息；信息；信息；信息；adjvex nextarcinfodatafirstarc

24、表结点表结点表结点表结点头结点头结点头结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi 信息链域，指向单链表的第一个结点v v 每个单链表的每个单链表的每个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。结构存储。结构存储。20第20页，本讲稿共41页例例例例1 1：无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表v1v2v3v5v4v4邻接表0123413341420例例例例2 2：有向图的邻接表有向图的邻接表有向图的邻接表有向图的邻接

25、表v1v2v3v4V4V3V2V12301邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)注：注：注：注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v523142021第21页，本讲稿共41页例例例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存

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

27、n+e)。若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶点的度？邻接表的邻接表的缺点：缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表邻接表的邻接表的优点：优点：TD(Vi)TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D(Vi)邻接点为邻接点为ViVi的弧个数的弧个数TD

28、(Vi)=OD(Vi)+I D(Vi)空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。的单链表，没有邻接矩阵方便。23第23页，本讲稿共41页讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表邻接表中每个链表对应对应于邻接矩阵中的一行，链于邻接矩阵中的一行，链表中结点个数表中结点个数等于等于一行中非零元素的个数。一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，对于任一确定的无向图，邻接矩

29、阵是唯一邻接矩阵是唯一的（行列号的（行列号与顶点编号一致），但与顶点编号一致），但邻接表不唯一邻接表不唯一（链接次序与顶点（链接次序与顶点编号无关）。编号无关）。(考试怎么办？考试怎么办？给定顺序给定顺序）邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),而邻接表的空间复杂度而邻接表的空间复杂度为为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)24第24页，本讲稿共41页三、三、十字链表十字链表（自学

30、自学）（适用于有向图）适用于有向图）四、四、邻接多重表邻接多重表（自学自学）（适用于无向图）（适用于无向图）25第25页，本讲稿共41页 它是它是有向图有向图的另一种链式结构。的另一种链式结构。思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、每条弧对应一个结点每条弧对应一个结点(称为称为弧结点，弧结点，设设5 5个域）个域）2 2、每个顶点也对应一个结点（称为、每个顶点也对应一个结点（称为顶点结点，顶点结点，设设3 3个域）个域）tailvexheadvexHlinktlinkinfo顶点结点顶点结点弧结点弧结点三、十字链表（自学

31、）三、十字链表（自学）tailvex:tailvex:弧尾顶点位置 headvex:headvex:弧头顶点位置hlink:hlink:弧头相同的下一弧位置tlink:tlink:弧尾相同的下一弧位置info:info:弧信息 n个顶点个顶点用顺序存储结构用顺序存储结构 data :存储顶点信息。存储顶点信息。Firstin :以顶点为弧头的第一条弧结点。Firstout:以顶点为弧尾的第一条弧结点。dataFirstinFirstout适用于有向图适用于有向图26第26页，本讲稿共41页0v11v22v33v4v1v2v3v40 1022 023例：画出有向图的十字链表。例：画出有向图的十字

32、链表。十字链表优点：十字链表优点：容易操作，如求顶点的入度、出度等。容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。303132数组下标不属结点分量27第27页，本讲稿共41页这是这是无向图无向图的另一种存储结构，当对边操作时，无向图应采用此种结构存的另一种存储结构，当对边操作时，无向图应采用此种结构存储。储。1、每条边只对应一个结点（称为、每条边只对应一个结点（称为边结点边结点），设立），设立6个域个域；2、每个顶点也对应一个结点（、每个顶点也对应一个结点（顶点结点顶点结点），设立），设立2个域；个

33、域；markivexilinkjvexjlinkinfo边结点边结点四、邻接多重表（自学）四、邻接多重表（自学）mark：标志域，如处理过或搜索过。ivex，jvex:顶点域，边依附的两个顶点位置。ilink:指向下一条依附顶点 i 的边结点位置。jlink;指向下一条依附顶点 j 的边结点位置。info:边信息，如权值等。n个顶点个顶点用顺序存储结构用顺序存储结构 data :存储顶点信息。Firstedge:依附顶点的第一条边结点。dataFirstedge顶点结点顶点结点适用于无向图适用于无向图28第28页，本讲稿共41页0v11v22v33v44v501031214232434v1v2

34、v3v5v4v4例：画出无向图的邻接多重表例：画出无向图的邻接多重表邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。数组下标不属结点分量29第29页，本讲稿共41页一一.深度优先遍历深度优先遍历(DFS)方法：从图的某一顶点方法：从图的某一顶点V0出发，出发，访问此顶点访问此顶点；然后依；然后依次从次从V0的未被访问的邻接点出发，深度优先遍历图，的未被访问的邻接点出发，深度优先遍历图，直至图中所有和直至图中所有和V0相通的顶点都被访问到；若此时图相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶中尚有顶点

35、未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访点作起点，重复上述过程，直至图中所有顶点都被访问为止问为止V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V77.3 7.3 图的遍历图的遍历30第30页，本讲稿共41页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V531第31页，本讲稿共41页深度优先遍历

36、算法算法 P150152 算法7-1，7-2开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi=Vexnums结束NNYY32第32页，本讲稿共41页V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdata firstarc 2 7 8 3adjvex next55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V433第33页，本讲稿共41页V1V2V4V5V3V7V6V8例12341342vexdata firstar

37、c 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V534第34页，本讲稿共41页二二.广度优先遍历广度优先遍历(BFS)方法：从图的某一顶点方法：从图的某一顶点V0出发，访问此顶点后，出发，访问此顶点后，依次访问依次访问V0的各个未曾访问过的邻接点的各个未曾访问过的邻接点；然后分别从这些邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个

38、未被访问的顶点作起点，重复上述过程，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V835第35页，本讲稿共41页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V536第36页，本讲稿共41页广度优先遍历算法 P153算法7-3开始标

39、志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi=Vexnums结束NNYY37第37页，本讲稿共41页开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY38第38页，本讲稿共41页例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 339第39页，本讲稿共41页例142351234

40、1342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 540第40页，本讲稿共41页0 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 241第41页，本讲稿共41页