数据结构第次课图

数据结构第次课图1第1页，共41页，2023年，2月20日，星期六数据结构课程的内容多对多（m:n)2第2页，共41页，2023年，2月20日，星期六7.1基本术语7.2存储结构7.3图的遍历7.4图的其他运算7.5图的应用第7章图3第3页，共41页，2023年，2月20日，星期六7.1图的基本术语图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向图：无向图：完全图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若

n个顶点的无向图有

n(n-1)/2条边,

称为无向完全图若

n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge4第4页，共41页，2023年，2月20日，星期六例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边G1的顶点集合为V(G1)={0,1,2,3}边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图5第5页，共41页，2023年，2月20日，星期六

稀疏图：边较少的图。通常边数<<n2

子图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且

E’E,则称图G’是图G的子图。稠密图：边很多的图。无向图中，边数接近n(n-1)/2

；

有向图中，边数接近n(n-1)

带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。网络：＝带权图6第6页，共41页，2023年，2月20日，星期六简单路径：路径上各顶点v1,v2,...,vm均不互相重复。回路：例：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点

vi出发,沿一些边经过一些顶点

vp1,vp2,…,vpm，到达顶点vj。则称顶点序列

(vi

vp1vp2...vpm

vj)

为从顶点vi到顶点

vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。7第7页，共41页，2023年，2月20日，星期六例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页，2023年，2月20日，星期六弧头和弧尾：有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。

顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。邻接顶点：若(u,v)是E(G)中的一条边，则称u与v互为邻接顶点度、入度和出度：问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！9第9页，共41页，2023年，2月20日，星期六生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。V1V2V4V5V3V7V6V8例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V810第10页，共41页，2023年，2月20日，星期六连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。强连通图：有两类图形不在本章讨论之列：连通图245136强连通图356536非连通图连通分量11第11页，共41页，2023年，2月20日，星期六ADTGraph

{数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}；VR={<v,w>|v,w∈V且P(v,w),

<v,w>表示从v到w的弧，

谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：

CreatGraph

(G,V,VR);

初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。InsertVex(G,v);

初始条件：图G存在，v和图中顶点有相同特征。

操作结果：在图G中添加新顶点。

………………（参见P135-136）}图的抽象数据类型注意：V的大小写含义不同！12第12页，共41页，2023年，2月20日，星期六7.2图的存储结构图的特点：非线性结构（m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法13第13页，共41页，2023年，2月20日，星期六一、邻接矩阵（数组）表示法建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：v1v2v3v5v4v4A例1：邻接矩阵：A.Edge=（v1v2

v3v4v5

）v1v2v3v4v500

0

0000

0000

00000000000000分析1：无向图的邻接矩阵是对称的，对角元素为0

；分析2：顶点i的度＝第i行(列)中1

的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10顶点表：14第14页，共41页，2023年，2月20日，星期六例2：有向图的邻接矩阵分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A.Edge[i][j]

顶点的入度=第i列元素之和。ID(Vi)=A.Edge[j][i]

顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4A邻接矩阵：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

00015第15页，共41页，2023年，2月20日，星期六容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。特别讨论：网（即有权图）的邻接矩阵定义为：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(

v1v2

v3v4v5v6)邻接矩阵法优点：邻接矩阵法缺点：顶点表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞16第16页，共41页，2023年，2月20日，星期六关联矩阵——表示顶点与边的关联关系的矩阵定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵例15324G2123456432156A[i][j]=1

i顶点与j

边相连0i顶点与j

边不相连对无向图：17第17页，共41页，2023年，2月20日，星期六A[i][j]=1

i顶点与j

边相连,且i为尾0i顶点与j

边不相连-1i顶点与j

边相连,且i为头对有向图：例BDAC123456ABCD43215618第18页，共41页，2023年，2月20日，星期六4321例G124131234特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中“1”的个数顶点Vi的入度是A中第i行中“-1”的个数19第19页，共41页，2023年，2月20日，星期六二、邻接表（链式）表示法对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；每个单链表还应当附设一个头结点（设为2个域），存vi信息；adjvexnextarcinfodatafirstarc表结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi信息链域，指向单链表的第一个结点每个单链表的头结点另外用顺序存储结构存储。20第20页，共41页，2023年，2月20日，星期六例1：无向图的邻接表v1v2v3v5v4v4邻接表01234^1334^142^0例2：有向图的邻接表v1v2v3v4V4V3^V2V12^3^0^1邻接表(出边)V4V3V2V1^3^0^2^0逆邻接表(入边)注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v523^142^021第21页，共41页，2023年，2月20日，星期六例3：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储结构形成后，图便唯一确定！22第22页，共41页，2023年，2月20日，星期六分析1:

对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(e<<n2)，则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点：分析2:

在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。—它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：需遍历全表邻接表的优点：TD(Vi)=单链表中链接的结点个数OD(Vi)＝单链出边表中链接的结点数ID(Vi)＝邻接点为Vi的弧个数TD(Vi)=OD(Vi)+ID(Vi)空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。23第23页，共41页，2023年，2月20日，星期六讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。(考试怎么办？给定顺序）②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)24第24页，共41页，2023年，2月20日，星期六三、十字链表（自学）

（适用于有向图）

四、邻接多重表（自学）

（适用于无向图）25第25页，共41页，2023年，2月20日，星期六

它是有向图的另一种链式结构。

思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、每条弧对应一个结点(称为弧结点，设5个域）2、每个顶点也对应一个结点（称为顶点结点，设3个域）tailvexheadvexHlinktlinkinfo顶点结点弧结点三、十字链表（自学）tailvex:弧尾顶点位置headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息n个顶点—用顺序存储结构data:存储顶点信息。Firstin:以顶点为弧头的第一条弧结点。Firstout:以顶点为弧尾的第一条弧结点。dataFirstinFirstout——适用于有向图26第26页，共41页，2023年，2月20日，星期六0v11v22v33v4v1v2v3v4010^2202^^3例：画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。3^03^^13^^2^数组下标不属结点分量27第27页，共41页，2023年，2月20日，星期六这是无向图的另一种存储结构，当对边操作时，无向图应采用此种结构存储。1、每条边只对应一个结点（称为边结点），设立6个域；2、每个顶点也对应一个结点（顶点结点），设立2个域；markivexilinkjvexjlinkinfo边结点四、邻接多重表（自学）mark：标志域，如处理过或搜索过。ivex，jvex:顶点域，边依附的两个顶点位置。ilink:指向下一条依附顶点i的边结点位置。jlink;指向下一条依附顶点j的边结点位置。info:边信息，如权值等。n个顶点——用顺序存储结构data:存储顶点信息。Firstedge:依附顶点的第一条边结点。dataFirstedge顶点结点——适用于无向图28第28页，共41页，2023年，2月20日，星期六0v11v22v33v44v501^…0312^1423^24^3^4v1v2v3v5v4v4例：画出无向图的邻接多重表邻接多重表优点：容易操作，如求顶点的度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。数组下标不属结点分量29第29页，共41页，2023年，2月20日，星期六一.深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V77.3图的遍历30第30页，共41页，2023年，2月20日，星期六V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V3V6V7V531第31页，共41页，2023年，2月20日，星期六深度优先遍历算法算法P150~152算法7-1，7-2开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY32第32页，共41页，2023年，2月20日，星期六V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V433第33页，共41页，2023年，2月20日，星期六V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍历：V1V3V7V6V2V4V8V534第34页，共41页，2023年，2月20日，星期六二.广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V835第35页，共41页，2023年，2月20日，星期六V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例广度遍历：V1V2V3