数据结构课件-图.ppt

数据结构课件-图.ppt

《数据结构课件-图.ppt》由会员分享，可在线阅读，更多相关《数据结构课件-图.ppt（125页珍藏版）》请在冰点文库上搜索。

Page1,2023/5/28,画出下列二叉链表代表的二叉树（0代表NULL指针），并完成其先序线索链表,1234567891011121314,Page2,2023/5/28,数据结构,第8-1讲图的基础知识,清华大学自动化系黄双喜博士、副教授,Page3,2023/5/28,学习目标领会图的基本概念。

熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

熟练掌握图的两种遍历算法及应用。

理解各种图的应用问题的算法。

重点和难点重点：

图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。

Page4,2023/5/28,知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历最小生成树算法拓扑排序关键路径最短路径,图的基础知识,图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树,Page5,2023/5/28,2023/5/28,欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。

几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，复变函数的欧拉公式等等。

据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。

1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。

1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。

欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。

图论欧拉,Page7,2023/5/28,能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？

哥尼斯堡七桥问题,18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接。

当时该城的市民热衷于这样一个游戏：

“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？

”,2023/5/28,七桥问题的图模型,欧拉回路的判定规则：

1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。

Page9,2023/5/28,最短路问题（SPPshortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。

从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？

假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

旅行商问题（TSPtravelingsalesmanproblem）一名推销员准备前往若干城市推销产品。

如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？

这一问题的研究历史十分悠久，通常称之为旅行商问题。

中国邮递员问题（CPPChinesepostmanproblem）一名邮递员负责投递某个街区的邮件。

如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？

由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

运输问题（transportationproblem）某种原材料有N个产地，现在需要将原材料从产地运往M个使用这些原材料的工厂。

假定N个产地的产量和M家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？

公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。

假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

上述问题有两个共同的特点：

一、它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二、它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。

与图和网络相关的最优化问题就是网络最优化或称网络优化（networkoptimization）问题。

线性表每个数据元素只有一个直接前驱和一个直接后继。

树形结构每个数据元素只有一个直接前驱，但可能有多个直接后继。

图形结构每个数据元素可能有多个直接前驱和多个直接后继。

图是比线性表和树复杂的数据结构，广泛应用于计算机、逻辑学、物理、化学等领域。

图的基本特性,网络拓扑结构,社交网络,图像处理,物理化学结构,电脑游戏,2023/5/28,图的定义,图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：

G=（V，E）其中：

G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。

在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。

Page15,如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。

若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为（vi,vj）。

若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。

如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。

图的基本术语,Page16,简单图：

在图中，若不存在顶点到其自身的边，且同一条边不重复出现。

数据结构中讨论的都是简单图。

邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边（vi，vj），则称顶点vi和顶点vj互为邻接点，同时称边（vi，vj）依附于顶点vi和顶点vj。

V1的邻接点：

V2的邻接点：

V2、V4,V1、V3、V5,2023/5/28,邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。

V1的邻接点：

V3的邻接点：

V2、V3,V4,2023/5/28,无向完全图：

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

有向完全图：

在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

2023/5/28,含有n个顶点的无向完全图有多少条边？

含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n（n-1）/2条边。

含有n个顶点的有向完全图有n（n-1）条边。

2023/5/28,稀疏图：

称边数很少的图为稀疏图；稠密图：

称边数很多的图为稠密图。

顶点的度：

在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD（v）。

顶点的入度：

在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID（v）；顶点的出度：

在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD（v）。

2023/5/28,在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？

在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？

与边数之和的关系？

2023/5/28,权：

是指对边赋予的有意义的数值量。

网：

边上带权的图，也称网图。

图结构中的权和哈夫曼树中的权有什么区别？

2023/5/28,路径：

在无向图G=（V,E）中，从顶点vp到顶点vq之间的路径是一个顶点序列（vp=vi0,vi1,vi2,vim=vq），其中，（vij-1,vij）E（1jm）。

若G是有向图，则路径也是有方向的，顶点序列满足E。

一般情况下，图中两个顶点之间的路径不唯一。

在什么情况下唯一？

V1到V4的路径：

V1V4V1V2V3V4V1V2V5V3V4,2023/5/28,路径长度：

非带权图路径上边的个数带权图路径上各边的权之和,V1V4：

长度为1V1V2V3V4：

长度为3V1V2V5V3V4：

长度为4,2023/5/28,路径长度：

非带权图路径上边的个数带权图路径上各边的权之和,V1V4：

长度为8V1V2V3V4：

长度为7V1V2V5V3V4：

长度为15,2023/5/28,回路（环）：

第一个顶点和最后一个顶点相同的路径。

简单路径：

序列中顶点不重复出现的路径。

简单回路（简单环）：

除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。

2023/5/28,子图：

若图G=（V，E），G=（V，E），如果VV且EE，则称图G是G的子图。

2023/5/28,连通图：

在无向图中，如果从一个顶点vi到另一个顶点vj（ij）有路径，则称顶点vi和vj是连通的。

如果图中任意两个顶点都是连通的，则称该图是连通图。

连通分量：

非连通图的极大连通子图称为连通分量。

如何求得一个非连通图的连通分量?

2023/5/28,V1,V2,V3,V4,V5,V6,V7,连通分量是对无向图的一种划分。

Page32,2023/5/28,强连通图：

在有向图中，对图中任意一对顶点vi和vj（ij），若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。

强连通分量：

非强连通图的极大强连通子图。

如何求得一个有向非连通图的强连通分量?

2023/5/28,V1,V2,2023/5/28,生成树：

n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

生成森林：

在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。

如何理解极小连通子图?

2023/5/28,图的基础知识,图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树,Page36,2023/5/28,2023/5/28,图的抽象数据类型定义如下：

ADTGraph数据对象V：

V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：

R=VRVR|v,wV且P（v,w），表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息,Page38,2023/5/28,G1=（V1,VR1）V1=A,B,C,D,EVR1=,G2=（V2,VR2）V2=A,B,C,D,E,FVR2=（A,B）,（A,E）,（B,E）,（C,D）,（D,F）,（B,F）,（C,F）,Page39,2023/5/28,图的基本操作：

CreateGraph（初始条件：

图G存在，u和G中顶点有相同特征。

操作结果：

若G中存在和u相同的顶点，则返回该顶点在图中位置；否则返回其它信息。

GetVex（G,v）;初始条件：

图G存在，v是G中某个顶点。

操作结果：

返回v的值。

FirstAdjVex（G,v）;初始条件：

图G存在，v是G中某个顶点。

操作结果：

返回v的第一个邻接点。

若该顶点在G中没有邻接点，则返回“空”。

NextAdjVex（G,v,w）;初始条件：

图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：

返回v的（相对于w的）下一个邻接点。

若w是v的最后一个邻接点，则返回“空”。

Page41,2023/5/28,PutVex（初始条件：

图G存在，v是G中某个顶点。

操作结果：

删除G中顶点v及其相关的弧。

2023/5/28,InsertArc（初始条件：

图G存在，v和w是G中两个顶点。

操作结果：

在G中删除弧，若G是无向的，则还删除对称弧。

Page43,2023/5/28,DFSTraverse（G,Visit（）;初始条件：

图G存在，Visit是顶点的应用函数。

操作结果：

对图G进行深度优先遍历。

遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

BFSTraverse（G,Visit（）;初始条件：

图G存在，Visit是顶点的应用函数。

操作结果：

对图G进行广度优先遍历。

遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦visit（）失败，则操作失败。

ADTGraph,2023/5/28,是否可以采用顶点的顺序存储结构存储图?

图的特点：

顶点之间的关系是m:

n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。

如何存储图?

考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。

数组表示法（邻接矩阵）将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。

假设图中顶点数为n，则邻接矩阵A定义为,网的邻接矩阵的定义为，当vi到vj有弧相邻接时，aij的值应为该弧上的权值，否则为。

1、图的邻接矩阵表示法,2023/5/28,图的数组（邻接矩阵）存储表示#defineINFINITYINT_MAX;/最大值#defineMAX_VERTEX_NUM20;/最大顶点个数typedefenumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedefstructArcCellVRTypeadj;/VRType是顶点关系类型。

对无权图，用1或0/表示相邻否；对带权图，则为权值类型。

InfoType*info;/该弧的相关信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点信息AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧（边）数GraphKindkind;/图的种类标志MGraph;,2023/5/28,有向图的存储结构,G1.vexs=A,B,C,D,G1.vexnum=4,G1.arcnum=4,G1.kind=DG,Page48,2023/5/28,如何求顶点i的出度？

邻接矩阵的第i行元素之和。

Page49,2023/5/28,如何求顶点i的入度？

邻接矩阵的第i列元素之和。

2023/5/28,如何判断从顶点i到顶点j是否存在边？

测试邻接矩阵中相应位置的元素arcij是否为1。

2023/5/28,无向图的存储结构,G2.vexs=A,B,C,D,E,G2.vexnum=5,G2.arcnum=6,G2.kind=UDG,2023/5/28,如何求顶点i的度？

V1,V3,V4,V2,邻接矩阵的第i行（或第i列）非零元素的个数。

2023/5/28,如何判断顶点i和j之间是否存在边？

V1,V3,V4,V2,测试邻接矩阵中相应位置的元素arcij是否为1。

Page54,2023/5/28,如何求顶点i的所有邻接点？

V1,V3,V4,V2,将数组中第i行元素扫描一遍，若arcij为1，则顶点j为顶点i的邻接点。

网图的邻接矩阵定义：

Page56,2023/5/28,G3.vexs=A,B,C,D,E,G3.vexnum=5,G3.arcnum=8,G3.kind=UDN,2023/5/28,邻接矩阵表示的特点：

无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n（n+1）/2。

有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n。

无向图中顶点Vi的度TD（Vi）是邻接矩阵A中第i行元素之和。

有向图中，顶点Vi的出度是A中第i行元素之和。

顶点Vi的入度是A中第i列元素之和。

邻接矩阵的优缺点优点：

容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。

缺点：

边数较少时，空间浪费较大。

2023/5/28,2、图的邻接表表示法,引入原因邻接矩阵在稀疏图时空间浪费较大。

实现为图中每个顶点建立一个单链表（边表），第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。

每个链表附设一个表头结点（顶点结点）。

与Vi邻接的点在表头数组中的位置,Page59,2023/5/28,图的邻接表存储表示,#defineMAX_VERTEX_NUM20;typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针ArcNode;/边表结点typedefstructVNodeVertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧AdjListMAX_VERTEX_NUM;/顶点表typedefstructAdjListvertices;/顶点数组intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;,Page60,2023/5/28,边表中的结点表示什么？

每个结点对应图中的一条边，邻接表的空间复杂度为O（n+2e）。

2023/5/28,如何求顶点i的度？

顶点i的边表中结点的个数。

无向图的邻接表,2023/5/28,如何判断顶点i和顶点j之间是否存在边?

测试顶点i的边表中是否存在终点为j的结点。

Page63,有向图的邻接表,如何求顶点i的出度？

顶点i的出边表中结点的个数。

2023/5/28,如何求顶点i的入度？

各顶点的出边表中以顶点i为终点的结点个数。

Page65,2023/5/28,如何求顶点i的所有邻接点？

遍历顶点i的边表，该边表中的所有终点都是顶点i的邻接点。

Page66,2023/5/28,网图的邻接表,2023/5/28,优缺点优点：

空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；缺点：

求有向图顶点的入度则不容易，要遍历整个表。

为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。

逆邻接表,2023/5/28,3图的十字链表表示法,引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。

实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条出弧和第一条入弧的指针。

邻接表,2023/5/28,引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。

实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条出弧和第一条入弧的指针。

逆邻接表,2023/5/28,弧尾位置,弧头位置,弧头相同的下一条弧指针,弧相关信息的指针,弧尾相同的下一条弧指针,指向该顶点第一条入弧,指向该顶点第一条出弧,2023/5/28,求结点的入度和出度的方法？

Page72,2023/5/28,4图的邻接多重表表示法,引入原因无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。

有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。

Page73,实现每条边用一个结点表示。

访问标记,边依附的一个顶点,边依附的另一个顶点,依附这个顶点的下一条边指针,依附这个顶点的下一条边指针,访问标记,指向第一条依附该顶点的边,2023/5/28,图的基础知识,图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树,Page75,2023/5/28,2023/5/28,图的遍历从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次。

可以从图中任意一个顶点出发进行遍历。

遍历中需解决的问题确定一搜索路径；确保每个顶点被访问到；确保每个顶点只能被访问一次。

解决方法深度优先和广度优先。

设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。

Page77,1深度优先搜索,方法从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；,若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

访问任意一个与V0邻接的顶点W1，再从W1出发；访问与W1邻接且未被访问过的任意顶点W2，再从W2出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。

Page78,2023/5/28,深一层递归,递归返回,深度优先遍历序列?

入栈序列?

出栈序列?

V1,遍历序列：

V1,V2,V2,V4,V4,V5,V5,Page79,2023/5/28,深一层递归,递归返回,深度优先遍历序列?

入栈序列?

出栈序列?

V1,遍历序列：

V1,V2,V2,V4,V4,V5,V8,V8,Page80,2023/5/28,深一层递归,递归返回,深度优先遍历序列?

入栈序列?

出栈序列?

V1,遍历序列：

V1,V2,V2,V4,V4,V5,V8,Page81,2023/5/28,深一层递归,递归返回,深度优先遍历序列?

入栈序列?

出栈序列?

V1,遍历序列：

V1,V7,V2,V4,V5,V8,V3,V3,V6,V6,V7,2023/5/28,深度优先遍历算法,BoolenvisitedMAX;/访问标志数组Status（*visitFunc）（intv）;/函数变量voidDFSTraverse（GraphG,Status（*visit）（intv）/对图G作深度优先遍历visitFunc=visit;/使用全局变量visitFunc，/使DFS不必设函数指针参数for（v=0;vG.vexnum;+v）visitedv=FALSE;/访问标识数组初始化for（v=0;vG.vexnum;+v）if（!

visitedv）DFS（G,v）;/对尚未访问的/顶点调用DFS,2023/5/28,voidDFS（GraphG,intv）/从第v个顶点出发递归地对图G进行深度优先搜索visitFunc（v）;/访问第v个顶点visitedv=TRUE;/设访问标志for（w=FirstAdjVex（G,v）;w=0;w=NextAdjVex（G,v,w）if（!

visitedw）DFS（G,w）;/对v的尚未访问过的邻接/顶点w递归调用DFS/DFS,2023/5/28,深度遍历：

V1,V3,V7,V6,V2,V5,V8,V4,2023/5/28,深度遍历：

V1,V3,V7,V6,V2,V4,V8,V5,Page86,2广度优先搜索,方法从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

广度优先遍历的过程是以v为起始点，由近至远，依次访问和v有路径相通且最短路径长度为1,2,的顶点。

Page87,2023/5/28,广度优先遍历序列?

入队序列?

出队序列?

遍历序列：

V1,V1,Page88,2023/5/28,广度优先遍历序列?

入队序列?

出队序列?

遍历序列：

V1,V2,V2,V3,V3,Page89,2023/5/28,广度优先遍历序列?

入队序列?

出队序列?

遍历序列：

V1,V2,V3,V3,V4,V4,V5,V5,Page90,2023/5/28,广度优先遍历序列?

入队序列?

出