数据结构课件-图讲述

Page12023/10/9画出下列二叉链表代表的二叉树（0代表NULL指针），并完成其先序线索链表InfoABCDEFGHIJKLMNLtagLchild24607010012130000RtagRchild3500891100014000InfoABCDEFGHIJKLMNLtag00010101001111Lchild246273101412131391011Rtag00110001110111Rchild35658911312131401181234567891011121314Page22023/10/9数据结构第8-1讲图的基础知识清华大学自动化系黄双喜博士、副教授huangsx@Page32023/10/9学习目标领会图的基本概念。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法及应用。理解各种图的应用问题的算法。重点和难点重点：图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。Page42023/10/9知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历最小生成树算法拓扑排序关键路径最短路径图的基础知识图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树Page52023/10/92023/10/9欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉Page72023/10/9能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接。当时该城的市民热衷于这样一个游戏：“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”2023/10/9CADB七桥问题的图模型欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。Page92023/10/9×√×√最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。中国邮递员问题（CPP－Chinesepostmanproblem）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。运输问题(transportationproblem)某种原材料有N个产地，现在需要将原材料从产地运往M个使用这些原材料的工厂。假定N个产地的产量和M家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？上述问题有两个共同的特点： 一、它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题； 二、它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（networkoptimization）问题。

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

图是比线性表和树复杂的数据结构，广泛应用于计算机、逻辑学、物理、化学等领域。图的基本特性网络拓扑结构社交网络图像处理物理化学结构电脑游戏2023/10/9图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：

G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。Page15如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。

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

Page16简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图简单图V1V2V3V4V5

数据结构中讨论的都是简单图。邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2的邻接点：V2、V4V1、V3、V52023/10/9邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj

。

V1V2V3V4V1的邻接点：V3的邻接点：V2、V3V42023/10/9无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

V1V2V3V1V2V3V42023/10/9含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V42023/10/9稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。2023/10/9V1V2V3V4V5在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？å==niievTD12)(V1V2V3V4在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii==åå==11)()(nn2023/10/9权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。V1V2V3V42785图结构中的权和哈夫曼树中的权有什么区别？2023/10/9路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<vij-1,vij>∈E。V1V2V3V4V5一般情况下，图中两个顶点之间的路径不唯一。在什么情况下唯一？V1到V4的路径：V1V4

V1V2V3V4V1V2V5V3V42023/10/9路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V1V2V3V4V5V1V4：长度为1V1V2V3V4：长度为3V1V2V5V3V4：长度为42023/10/9路径长度：非带权图——路径上边的个数带权图——路径上各边的权之和V1V4：长度为8V1V2V3V4：长度为7V1V2V5V3V4：长度为15V1V2V3V4V52563282023/10/9回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。V1V2V3V4V5V1V2V3V42023/10/9子图：若图G=（V，E），G'=（V'，E'），如果V'

V

且E'

E

，则称图G'是G的子图。V1V2V3V4V5V1V2V3V4V5V1V3V42023/10/9连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。

如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。2023/10/9连通分量1

V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2连通分量是对无向图的一种划分。Page322023/10/9强连通图：在有向图中，对图中任意一对顶点vi和vj

(i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。

如何求得一个有向非连通图的强连通分量?2023/10/9V1V2V3V4强连通分量1

强连通分量2V1V3V4V22023/10/9生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

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

如何理解极小连通子图?多——构成回路少——不连通含有n-1条边2023/10/9V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林图的基础知识图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树Page362023/10/92023/10/9图的抽象数据类型定义如下：ADTGraph{数据对象V

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

点集。数据关系R

：

R={VR}

VR＝{<v,w>|v,w∈V且P(v,w)，<v,w>表示从v到w的

弧，谓词P(v,w)定义了弧<v,w>的意义

或信息}Page382023/10/9G1=(V1,VR1)V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,

<D,B>,<D,A>,<E,C>}G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),

(D,F),(B,F),(C,F)}Page392023/10/9图的基本操作：

CreateGraph(&G,V,VR);

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

操作结果：按V和VR的定义构造图

G。

DestroyGraph(&G);

初始条件：图G存在。

操作结果：销毁图

G。

LocateVex(G,u);

初始条件：图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的最后一个邻接点，则返回“空”。Page412023/10/9

PutVex(&G,v,value);

初始条件：图G存在，v是G中某个顶点。

操作结果：对v赋值value。

InsertVex(&G,v);

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

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

DeleteVex(&G,v);

初始条件：图G存在，v是G中某个顶点。

操作结果：删除G中顶点v及其相关的弧。2023/10/9 InsertArc(&G,v,w);

初始条件：图G存在，v和w是G中两个顶点。

操作结果：在G中增添弧<v,w>，若G是无向的，则还

增添对称弧<w,v>。

DeleteArc(&G,v,w);

初始条件：图G存在，v和w是G中两个顶点。

操作结果：在G中删除弧<v,w>，若G是无向的，则还

删除对称弧<w,v>。Page432023/10/9 DFSTraverse(G,Visit());

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图G进行深度优先遍历。遍历过程中对每

个顶点调用函数Visit一次且仅一次。一旦

visit()失败，则操作失败。

BFSTraverse(G,Visit());

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图G进行广度优先遍历。遍历过程中对每

个顶点调用函数Visit一次且仅一次。一旦

visit()失败，则操作失败。}ADTGraph2023/10/9是否可以采用顶点的顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。数组表示法(邻接矩阵)将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。假设图中顶点数为n，则邻接矩阵A定义为网的邻接矩阵的定义为，当vi到vj有弧相邻接时，aij的值应为该弧上的权值，否则为∞。1、图的邻接矩阵表示法2023/10/9图的数组(邻接矩阵)存储表示#defineINFINITY INT_MAX;

//最大值∞#defineMAX_VERTEX_NUM 20;

//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcCell{

VRType adj;

//VRType是顶点关系类型。对无权图，用1或0

//表示相邻否；对带权图，则为权值类型。

InfoType *info; //该弧的相关信息

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{

VertexType vexs[MAX_VERTEX_NUM]; //顶点信息

AdjMatrix arcs;

//邻接矩阵

int vexnum,arcnum;

//图的当前顶点数和弧(边)数

GraphKind kind;

//图的种类标志

}MGraph;2023/10/9有向图的存储结构G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DGPage482023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。Page492023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。2023/10/9V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素arc[i][j]是否为1。2023/10/9无向图的存储结构AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG2023/10/9如何求顶点i的度？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。2023/10/9如何判断顶点i和j之间是否存在边？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arc[i][j]是否为1。Page542023/10/9如何求顶点i的所有邻接点？V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第i

行元素扫描一遍，若arc[i][j]为1，则顶点j

为顶点i的邻接点。网图的邻接矩阵定义：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）∞/0若i=j∞其他V1V2V3V42785∞25∞∞∞∞∞∞∞∞87∞∞∞arc=Page562023/10/9ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN2023/10/9邻接矩阵表示的特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²。无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。邻接矩阵的优缺点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、

入度）。缺点：边数较少时，空间浪费较大。2023/10/92、图的邻接表表示法引入原因邻接矩阵在稀疏图时空间浪费较大。实现为图中每个顶点建立一个单链表（边表），第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。每个链表附设一个表头结点（顶点结点）。表结点adjvexnextarcinfo与Vi邻接的点在表头数组中的位置头结点datafirstarcPage592023/10/9图的邻接表存储表示#defineMAX_VERTEX_NUM20;typedefstructArcNode{

int adjvex;

//该弧所指向的顶点的位置

structArcNode *nextarc;

//指向下一条弧的指针

InfoType *info;

//该弧相关信息的指针

}ArcNode;//边表结点typedefstructVNode{

VertexType data;

//顶点信息

ArcNode *firstarc;

//指向第一条依附该顶点的弧

}AdjList[MAX_VERTEX_NUM];//顶点表typedefstruct{

AdjListvertices;

//顶点数组

intvexnum,arcnum;

//图的当前顶点数和弧数

intkind;

//图的种类标志

}ALGraph;Page602023/10/9103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+2e)。2023/10/9103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2如何求顶点i的度？顶点i的边表中结点的个数。无向图的邻接表2023/10/9如何判断顶点i和顶点j之间是否存在边?测试顶点i的边表中是否存在终点为j的结点。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2Page63有向图的邻接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的出度？顶点i的出边表中结点的个数。2023/10/9V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的入度？各顶点的出边表中以顶点i为终点的结点个数。Page652023/10/9V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的所有邻接点？遍历顶点i的边表，该边表中的所有终点都是顶点i的邻接点。Page662023/10/9网图的邻接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧2023/10/9优缺点优点：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；缺点：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。bdac0123acdbdatafirstarc30^0^^2^adjvexnext逆邻接表2023/10/93图的十字链表表示法引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。G1bdac0123acdbdatafirstarc2130^^^^adjvexnext邻接表2023/10/9引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。G1bdac逆邻接表0123acdbdatafirstarc30^0^^2^adjvexnext2023/10/9弧结点tailvexheadvexhlinktlinkinfo顶点结点datafirstinfirstout弧尾位置弧头位置弧头相同的下一条弧指针弧相关信息的指针弧尾相同的下一条弧指针指向该顶点第一条入弧指向该顶点第一条出弧2023/10/902012320323130bdacabcd0123^^^^^^^^求结点的入度和出度的方法？弧头弧尾出边入边同尾同头Page722023/10/94图的邻接多重表表示法引入原因无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。aecbd0123acdbdatafirstarc3101^^^adjvexnext4e324^04212^Page73实现每条边用一个结点表示。边结点markivexilinkjvexjlinkinfo顶点结点markfirstedge访问标记边依附的一个顶点边依附的另一个顶点依附这个顶点的下一条边指针依附这个顶点的下一条边指针访问标记指向第一条依附该顶点的边2023/10/9aecbd0123acdb4e010323212441^^^^^图的基础知识图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树Page752023/10/92023/10/9图的遍历从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次。可以从图中任意一个顶点出发进行遍历。遍历中需解决的问题确定一搜索路径；确保每个顶点被访问到；确保每个顶点只能被访问一次。解决方法深度优先和广度优先。设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。Page771深度优先搜索方法从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。访问任意一个与V0邻接的顶点W1，再从W1出发；访问与W1邻接且未被访问过的任意顶点W2，再从W2出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。Page782023/10/9深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5

V5Page792023/10/9深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8

V8Page802023/10/9深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8Page812023/10/9深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V72023/10/9深度优先遍历算法Boolenvisited[MAX]; //访问标志数组Status(*visitFunc)(intv); //函数变量voidDFSTraverse(GraphG,Status(*visit)(intv)){

//对图G作深度优先遍历

visitFunc=visit; //使用全局变量visitFunc，

//使DFS不必设函数指针参数

for(v=0;v<G.vexnum;++v)

visited[v]=FALSE;

//访问标识数组初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v); //对尚未访问的

//顶点调用DFS}2023/10/9voidDFS(GraphG,intv){

//从第v个顶点出发递归地对图G进行深度优先搜索

visitFunc(v);

//访问第v个顶点

visited[v]=TRUE;

//设访问标志

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w); //对v的尚未访问过的邻接

//顶点w递归调用DFS}//DFS2023/10/9V1V2V4V5V3V7V6V8深度遍历：V1

0123V1V3V4V2datafirstarc1672^^^adjvexnext4V5530^40171^V6V7V8567625243^^^V3V7V6V2V5V8V42023/10/9V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc1672^^^adjvexnext4V55^371^V6V7V85676^^^深度遍历：V1

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

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

的顶点。Page872023/10/9广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V1Page882023/10/9广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3Page892023/10/9广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5Page902023/10/9广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7Page912023/10/9广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8Page922023/10/9广度优先遍历算法voidBFSTraverse(GraphG,Status(*visit)(intv)){

//对图G进行广度优先搜索遍历

for(v=0;v<G.vexnum;++v)visited[v]=FALSE; InitQueue(Q);

//设置空队列Q for(v=0;v<G.vexnum;++v) if(!visited[v]){

//v未被访问

visited[v]=TRUE;Visit(v);

//访问v

EnQueue(Q,v);

//v入队列

while(!QueueEmpty(Q)){

DeQueue(Q,u);

//队头元素出队并置为u

for(w=FirstAdjVex(G,u);w>=0;w=NextAjdVex(G,u,w))

if(!visited[w]){

visited[w]=TRUE;Visit(w);

//访问第w个顶点

EnQueue(Q,w);

}//if

}//while

}//ifDestroyQueue(Q);}//BFSTraverse1

2

3

4

5

6

7

8

9

10

11

122023/10/91423501231342datafirstarc4432^^^adjvexnext450^40032^111、4、3、2、5图的基础知识图的概念与基本术语图的类型定义与存储图的遍历图的连通性与最小生成树Page942023/10/9Page952023/10/9无向图的连通分量对于连通图，仅需从图中任一顶点出发，进行DFS或BFS搜索，即可遍历图的全部顶点；对于非连通图，则需从多个顶点出发进行DFS或BFS搜索，才能遍历完图的全部顶点。每一次从一个新的起始点出发进行DFS或BFS搜索过程中所得的顶点访问序列就是各连通分量的顶点集。2023/10/9ABLMCFDEGHKIJ邻接表1211109876543210MLKJIHGFEDCBA1152

112

0

0

4

3

0108

710

6

612

117

6129

0119

12023/10/9深度优先遍历的结果为(3次DFS过程)从A出发：ALMJBFC从D出发：DE从G出发：GKHI连通分量：三个顶点集+依附于这个顶点集中顶点的边。DEGHKIABLMCFJ2023/10/9生成树所有顶点均由边连接在一起，但不存在回路的图称为生成树。一个有n个顶点的连通图的生成树有n-1条边；一个图可以有许多棵不同的生成树。对于连通图，调用DFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵深度优先生成树。对于连通图，调用BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵广度优先生成树。对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。为什么深度和广度遍历后得到的是极小连通子图？2023/10/9V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍历V1V2V4V5V3V7V6V8深度优先生成树2023/10/9V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1广度遍历V1V2V4V5V3V7V6V8广度优先生成树2023/10/9ABLMCFDEGHKIJ深度优先遍历： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度优先生成森林Page102网的最小生成树问题描述用一个连通网表示n个居民点和各个居民点之间可能架设的通讯线路，网中边上的权值表示架设这条线路所需经费。在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？问题均等价于：在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。类似此类的问题很多。16543271317918127524101654327139510最小生成树的性质设G=(V，E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U，v∈V-U，且(u,v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u,v)的最小生成树。构造最小生成树的基本原则：◆尽可能选取权值最小的边，但不能构成回路；◆选择n-1条边构成最小生成树。2023/10/9构造最小生成树方法方法一：克鲁斯卡尔(Kruskal)算法基本思想为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；依此类推，直至T中所有顶点都在同一连通分量上为止。2023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}2023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}12连通分量＝{A},{B,E},{C},{D},{F}2023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C},{D},{F}12连通分量＝{A,F},{B,E},{C},{D}162023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C},{D}12连通分量＝{A,F},{B,E},{C,D}16172023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C,D}12连通分量＝{A,F,C,D},{B,E}1617252023/10/9251234162646381725ABEDCFABEDCF连通分量＝{A,F,C,D},{B,E}12连通分量＝{A,F,C,D,B,E}16172526Page1112023/10/91.初始化：U=V；TE={}；2.循环直到T中的连通分量个数为12.1在E中寻找最短边(u，v);2.2如果顶点u、v位于T的两个不同连通分量，则

2.2.1将边(u，v)并入TE；

2.2.2将这两个连通分量合为一个，编号改为相同；

2.3在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；Kruskal算法——伪代码解决方法：定义一个一维数组Vset[n]，存放图T中每个顶点所在的连通分量的编号。◆

初值：Vset[i]=i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。◆当往T中增加一条边(vi，vj)时，先检查Vset[i]和Vset[j]值：☆

若Vset[i]=Vset[j]：vi和vj处在同一个连通分量中；☆若Vset[i]≠Vset[j]：vi和vj不在同一个连通分量中2023/10/9克鲁斯卡尔(Kruskal)算法for(j=0;j<G->vexnum;j++)Vset[j]=j;/*初始化数组Vset[n]，记录连通分量编号*/sort(G->edgelist);/*对边表按权值从小到大排序*/j=0;k=0;while(k<G->vexnum-1&&j<G->edgenum){s1=Vset[G->edgelist[j].vex1];s2=Vset[G->edgelist[j].vex2];/*若边的两个顶点的连通分量编号不同,边加入到TE中*/if(s1!=s2)

{TE[k].vex1=G->edgelist[j].vex1;TE[k].vex2=G->edgelist[j].vex2;TE[k].weight=G->edgelist[j].weight;k++;for(v=0;v<G->vexnum;v++)//将Vset中所有值等于s2的都改为s1，成为一个连通分量

if(Vset[v]==s2)Vset[v]=s1;}j++;}free(Vset);return(TE);为什么k<G->vexnum-1？O(n)O(e㏒e)O(n)O(n^2)O(e㏒e+n2)2023/10/9方法二：普里姆(Prim)算法基本思想首先选取图中任意一个顶点v作为生成树的根，之后继续往生成树中添加顶点w，则在顶点w和顶点v之间必须有边，且该边上的权值应在所有和v相邻接的边中属最小。具体作法

TE是N上最小生成树中边的集合初始令U={u0},(u0V),TE=；在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)；将(u0,v0)并入集合TE，同时v0并入U；重复上述操作直至U=V为止，则T=(V,{TE})为最小生成树。构造最小生成树方法2023/10/9U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCF2023/10/9251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(A,C)46,(F,C)25,(F,D)25,(F,E)26}2023/10/9251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(F,D)25,(C,D)17