数据结构图论部分

数据结构图论部分第1页，共191页，2023年，2月20日，星期六学习目标领会图的类型定义。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法。理解各种图的应用问题的算法。重点和难点重点：图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。第2页，共191页，2023年，2月20日，星期六2023/4/212知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历无向网的最小生成树拓扑排序关键路径最短路径第3页，共191页，2023年，2月20日，星期六2023/4/213欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。图论——欧拉第4页，共191页，2023年，2月20日，星期六2023/4/214能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题

第5页，共191页，2023年，2月20日，星期六2023/4/215CADB七桥问题的图模型欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。第6页，共191页，2023年，2月20日，星期六2023/4/216图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。7.1图的定义和术语第7页，共191页，2023年，2月20日，星期六2023/4/217线性表每个数据元素只有一个直接前驱和一个直接后继。树形结构每个数据元素只有一个直接前驱，但可能有多个直接后继。图形结构每个数据元素可能有多个直接前驱和多个直接后继。图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。第8页，共191页，2023年，2月20日，星期六2023/4/218如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。

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

第9页，共191页，2023年，2月20日，星期六2023/4/219简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图简单图V1V2V3V4V5

数据结构中讨论的都是简单图。第10页，共191页，2023年，2月20日，星期六2023/4/2110图的基本术语

邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V5第11页，共191页，2023年，2月20日，星期六2023/4/2111图的基本术语

邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj

。

V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4第12页，共191页，2023年，2月20日，星期六2023/4/2112无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

图的基本术语

V1V2V3V1V2V3V4第13页，共191页，2023年，2月20日，星期六2023/4/2113含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V4第14页，共191页，2023年，2月20日，星期六2023/4/2114稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。图的基本术语

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。第15页，共191页，2023年，2月20日，星期六2023/4/2115V1V2V3V4V5图的基本术语

在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？å==niievTD12)(第16页，共191页，2023年，2月20日，星期六2023/4/2116V1V2V3V4图的基本术语

在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii==åå==11)()(nn第17页，共191页，2023年，2月20日，星期六2023/4/2117权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。图的基本术语

V1V2V3V42785第18页，共191页，2023年，2月20日，星期六2023/4/2118路径：在无向图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

V1V2V3V4V1V2V5V3V4第19页，共191页，2023年，2月20日，星期六2023/4/2119路径长度：图的基本术语

非带权图——路径上边的个数带权图——路径上各边的权之和V1V2V3V4V5V1V4：长度为1V1V2V3V4：长度为3V1V2V5V3V4：长度为4第20页，共191页，2023年，2月20日，星期六2023/4/2120路径长度：图的基本术语

非带权图——路径上边的个数带权图——路径上各边的权之和V1V4：长度为8V1V2V3V4：长度为7V1V2V5V3V4：长度为15V1V2V3V4V5256328第21页，共191页，2023年，2月20日，星期六2023/4/2121回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。图的基本术语

V1V2V3V4V5V1V2V3V4第22页，共191页，2023年，2月20日，星期六2023/4/2122子图：若图G=（V，E），G'=（V'，E'），如果V'V且E'

E，则称图G'是G的子图。图的基本术语

V1V2V3V4V5V1V2V3V4V5V1V3V4第23页，共191页，2023年，2月20日，星期六2023/4/2123连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。

图的基本术语

如何求得一个非连通图的连通分量?1.含有极大顶点数；2.依附于这些顶点的所有边。第24页，共191页，2023年，2月20日，星期六2023/4/2124连通分量1

V1V2V3V4V5V6V7V1V2V4V5V3V6V7连通分量2图的基本术语

连通分量是对无向图的一种划分。第25页，共191页，2023年，2月20日，星期六2023/4/2125强连通图：在有向图中，对图中任意一对顶点vi和vj

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

图的基本术语

如何求得一个非连通图的连通分量?第26页，共191页，2023年，2月20日，星期六2023/4/2126图的基本术语

V1V2V3V4强连通分量1

强连通分量2V1V3V4V2第27页，共191页，2023年，2月20日，星期六2023/4/2127生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

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

如何理解极小连通子图?图的基本术语

多——构成回路少——不连通含有n-1条边第28页，共191页，2023年，2月20日，星期六2023/4/2128V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林第29页，共191页，2023年，2月20日，星期六2023/4/2129图的抽象数据类型定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶

点集。数据关系R：

R={VR}

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

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

或信息}第30页，共191页，2023年，2月20日，星期六2023/4/2130G1=(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)}第31页，共191页，2023年，2月20日，星期六2023/4/2131

CreateGraph(&G,V,VR);

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

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

DestroyGraph(&G);

初始条件：图G存在。

操作结果：销毁图G。

LocateVex(G,u);

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

操作结果：若G中存在和u相同的顶点，则返回该顶点

在图中位置；否则返回其它信息。 第32页，共191页，2023年，2月20日，星期六2023/4/2132 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的最后一个邻接点，则返回“空”。第33页，共191页，2023年，2月20日，星期六2023/4/2133

PutVex(&G,v,value);

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

操作结果：对v赋值value。

InsertVex(&G,v);

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

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

DeleteVex(&G,v);

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

操作结果：删除G中顶点v及其相关的弧。第34页，共191页，2023年，2月20日，星期六2023/4/2134 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>。第35页，共191页，2023年，2月20日，星期六2023/4/2135 DFSTraverse(G,Visit());

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

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

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

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

FSTraverse(G,Visit());

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

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

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

visit()失败，则操作失败。}ADTGraph第36页，共191页，2023年，2月20日，星期六2023/4/2136是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。7.2图的存储结构第37页，共191页，2023年，2月20日，星期六2023/4/21377.2图的存储结构数组表示法(邻接矩阵)将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。假设图中顶点数为n，则邻接矩阵A定义为网的邻接矩阵的定义为，当vi到vj有弧相邻接时，aij的值应为该弧上的权值，否则为∞。第38页，共191页，2023年，2月20日，星期六2023/4/2138图的数组(邻接矩阵)存储表示#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;第39页，共191页，2023年，2月20日，星期六2023/4/2139有向图的存储结构G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DG第40页，共191页，2023年，2月20日，星期六2023/4/2140有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。第41页，共191页，2023年，2月20日，星期六2023/4/2141有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。第42页，共191页，2023年，2月20日，星期六2023/4/2142有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素arc[i][j]是否为1。第43页，共191页，2023年，2月20日，星期六2023/4/2143无向图的存储结构AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG第44页，共191页，2023年，2月20日，星期六2023/4/2144网图的存储结构ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN第45页，共191页，2023年，2月20日，星期六2023/4/2145如何求顶点i的度？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。第46页，共191页，2023年，2月20日，星期六2023/4/2146如何判断顶点i和j之间是否存在边？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arc[i][j]是否为1。第47页，共191页，2023年，2月20日，星期六2023/4/2147如何求顶点i的所有邻接点？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第i行元素扫描一遍，若arc[i][j]为1，则顶点j为顶点i的邻接点。第48页，共191页，2023年，2月20日，星期六2023/4/2148特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²。无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。邻接矩阵的优缺点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、

入度）。缺点：边数较少时，空间浪费较大。第49页，共191页，2023年，2月20日，星期六2023/4/2149网图的邻接矩阵网图的邻接矩阵可定义为：

arc[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞∞∞∞087∞∞0arc=第50页，共191页，2023年，2月20日，星期六2023/4/21507.2.2图的邻接表表示法引入原因邻接矩阵在稀疏图时空间浪费较大。实现为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。每个链表附设一个表头结点。表结点adjvexnextarcinfo与Vi邻接的点在表头数组中的位置头结点datafirstarc第51页，共191页，2023年，2月20日，星期六2023/4/2151图的邻接表存储表示#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;第52页，共191页，2023年，2月20日，星期六2023/4/2152103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表边表中的结点表示什么？每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。第53页，共191页，2023年，2月20日，星期六2023/4/2153103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表如何求顶点i的度？顶点i的边表中结点的个数。第54页，共191页，2023年，2月20日，星期六2023/4/2154如何判断顶点i和顶点j之间是否存在边?测试顶点i的边表中是否存在终点为j的结点。103∧23∧1∧01∧V1V2

V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表第55页，共191页，2023年，2月20日，星期六2023/4/2155有向图的邻接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的出度？顶点i的出边表中结点的个数。第56页，共191页，2023年，2月20日，星期六2023/4/2156有向图的邻接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的入度？各顶点的出边表中以顶点i为终点的结点个数。第57页，共191页，2023年，2月20日，星期六2023/4/2157有向图的邻接表V1V2V3V412∧3∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的所有邻接点？遍历顶点i的边表，该边表中的所有终点都是顶点i的邻接点。第58页，共191页，2023年，2月20日，星期六2023/4/2158网图的邻接表V1V2V3V4278521V1V2

V3V40123vertexfirstedge∧52∧83∧70∧第59页，共191页，2023年，2月20日，星期六2023/4/2159优缺点优点：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；缺点：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。bdac0123acdbdatafirstarc30^0^^2^adjvexnext逆邻接表第60页，共191页，2023年，2月20日，星期六2023/4/21607.2.3图的十字链表表示法引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。G1bdac0123acdbdatafirstarc2130^^^^adjvexnext邻接表第61页，共191页，2023年，2月20日，星期六2023/4/21617.2.3图的十字链表表示法引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。G1bdac逆邻接表0123acdbdatafirstarc30^0^^2^adjvexnext第62页，共191页，2023年，2月20日，星期六2023/4/2162弧结点tailvexheadvexhlinktlinkinfo顶点结点datafirstinfirstout弧尾位置弧头位置弧尾相同的下一条弧指针弧相关信息的指针弧头相同的下一条弧指针指向该顶点第一条入弧指向该顶点第一条出弧第63页，共191页，2023年，2月20日，星期六2023/4/216302012320323130bdacabcd0123^^^^^^^^求结点的入度和出度的方法？第64页，共191页，2023年，2月20日，星期六2023/4/21647.2.4图的邻接多重表表示法引入原因无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。aecbd0123acdbdatafirstarc3101^^^adjvexnext4e324^04212^第65页，共191页，2023年，2月20日，星期六2023/4/2165实现每条边用一个结点表示。边结点markivexilinkjvexjlinkinfo顶点结点markfirstedge访问标记边依附的一个顶点边依附的另一个顶点依附这个顶点的下一条边指针依附这个顶点的下一条边指针访问标记指向第一条依附该顶点的边第66页，共191页，2023年，2月20日，星期六2023/4/2166aecbd0123acdb4e010323212441^^^^^第67页，共191页，2023年，2月20日，星期六2023/4/21677.3图的遍历图的遍历从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次。可以从图中任意一个顶点出发进行遍历。遍历中需解决的问题确定一搜索路径；确保每个顶点被访问到；确保每个顶点只能被访问一次。解决方法深度优先和广度优先。设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。第68页，共191页，2023年，2月20日，星期六2023/4/21687.3.1深度优先搜索方法从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。访问任意一个与V0邻接的顶点W1，再从W1出发；访问与W1邻接且未被访问过的任意顶点W2，再从W2出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。第69页，共191页，2023年，2月20日，星期六2023/4/2169深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5

V5第70页，共191页，2023年，2月20日，星期六2023/4/2170深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8

V8第71页，共191页，2023年，2月20日，星期六2023/4/2171深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1图的逻辑结构V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8第72页，共191页，2023年，2月20日，星期六2023/4/2172深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V7第73页，共191页，2023年，2月20日，星期六2023/4/2173深度优先遍历算法7.4、7.5Boolenvisited[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}第74页，共191页，2023年，2月20日，星期六2023/4/2174voidDFS(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}//DFS第75页，共191页，2023年，2月20日，星期六2023/4/2175V1V2V4V5V3V7V6V8深度遍历：V10123V1V3V4V2datafirstarc1672^^^adjvexnext4V5530^40171^V6V7V8567625243^^^V3V7V6V2V5V8V4第76页，共191页，2023年，2月20日，星期六2023/4/2176V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc1672^^^adjvexnext4V55^371^V6V7V85676^^^深度遍历：V1V3V7V6V2V4V8V5第77页，共191页，2023年，2月20日，星期六2023/4/21777.3.2广度优先搜索方法从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。广度优先遍历的过程是以v为起始点，由近至远，依次访问和v有路径相通且最短路径长度为1,2,…的顶点。第78页，共191页，2023年，2月20日，星期六2023/4/2178广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V1第79页，共191页，2023年，2月20日，星期六2023/4/2179广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V3第80页，共191页，2023年，2月20日，星期六2023/4/2180广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V5第81页，共191页，2023年，2月20日，星期六2023/4/2181广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V7第82页，共191页，2023年，2月20日，星期六2023/4/2182广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8第83页，共191页，2023年，2月20日，星期六2023/4/2183V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1第84页，共191页，2023年，2月20日，星期六2023/4/2184广度优先遍历算法7.6voidBFSTraverse(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

12第85页，共191页，2023年，2月20日，星期六2023/4/21851423501231342datafirstarc4432^^^adjvexnext450^40032^11第86页，共191页，2023年，2月20日，星期六2023/4/21867·4图的连通性问题7.4.1无向图的连通分量和生成树无向图的连通分量对于连通图，仅需从图中任一顶点出发，进行DFS或BFS搜索，即可遍历图的全部顶点；对于非连通图，则需从多个顶点出发进行DFS或BFS搜索，才能遍历完图的全部顶点。每一次从一个新的起始点出发进行DFS或BFS搜索过程中所得的顶点访问序列就是各连通分量的顶点集。第87页，共191页，2023年，2月20日，星期六2023/4/2187ABLMCFDEGHKIJ邻接表1211109876543210MLKJIHGFEDCBA1152112004301087106612117612901191第88页，共191页，2023年，2月20日，星期六2023/4/2188深度优先遍历的结果为(3次DFS过程)从A出发：ALMJBFC从D出发：DE从G出发：GKHI连通分量：三个顶点集+依附于这个顶点集中顶点的边。DEGHKIABLMCFJ第89页，共191页，2023年，2月20日，星期六2023/4/2189生成树所有顶点均由边连接在一起，但不存在回路的图称为生成树。一个有n个顶点的连通图的生成树有n-1条边；一个图可以有许多棵不同的生成树。对于连通图，调用DFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵深度优先生成树。对于连通图，调用BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵广度优先生成树。对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。第90页，共191页，2023年，2月20日，星期六2023/4/2190V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍历V1V2V4V5V3V7V6V8深度优先生成树第91页，共191页，2023年，2月20日，星期六2023/4/2191V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1广度遍历V1V2V4V5V3V7V6V8广度优先生成树第92页，共191页，2023年，2月20日，星期六2023/4/2192ABLMCFDEGHKIJ深度优先遍历： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度优先生成森林第93页，共191页，2023年，2月20日，星期六2023/4/21937.4.2最小生成树问题描述用一个连通网表示n个居民点和各个居民点之间可能架设的通讯线路，网中边上的权值表示架设这条线路所需经费。在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？问题均等价于：在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。类似此类的问题很多。16543271317918127524101654327139510第94页，共191页，2023年，2月20日，星期六2023/4/2194MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。顶点集UV－Uu'vv'u顶点集T1T2第95页，共191页，2023年，2月20日，星期六2023/4/2195构造最小生成树方法方法一：克鲁斯卡尔(Kruskal)算法基本思想为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；依此类推，直至T中所有顶点都在同一连通分量上为止。第96页，共191页，2023年，2月20日，星期六2023/4/2196251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}第97页，共191页，2023年，2月20日，星期六2023/4/2197251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}12连通分量＝{A},{B,E},{C},{D},{F}第98页，共191页，2023年，2月20日，星期六2023/4/2198251234162646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C},{D},{F}12连通分量＝{A,F},{B,E},{C},{D}16第99页，共191页，2023年，2月20日，星期六2023/4/2199251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C},{D}12连通分量＝{A,F},{B,E},{C,D}1617第100页，共191页，2023年，2月20日，星期六2023/4/21100251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C,D}12连通分量＝{A,F,C,D},{B,E}161725第101页，共191页，2023年，2月20日，星期六2023/4/21101251234162646381725ABEDCFABEDCF连通分量＝{A,F,C,D},{B,E}12连通分量＝{A,F,C,D,B,E}16172526第102页，共191页，2023年，2月20日，星期六2023/4/211021.初始化：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算法——伪代码第103页，共191页，2023年，2月20日，星期六2023/4/21103克鲁斯卡尔(Kruskal)算法voidminitree_KRUSKAL(void){ intn,i,m,min,k,j; VEXt[M]; EDGEe[M]; printf("Inputnumberofvertexandedge:");

scanf("%d,%d",&n,&m); for(i=1;i<=n;i++){

printf(“t[%d].data=:”,i);

scanf(“%d”,&t[i].data);

t[i].set=i;} for(i=0;i<m;i++){

printf("vexh,vext,weight:");

scanf("%d,%d,%d",&e[i].vexh,&e[i].vext,&e[i].weight);

e[i].flag=0;}第104页，共191页，2023年，2月20日，星期六2023/4/21104 i=1; while(i<n){ min=MAX;

for(j=0;j<m;j++) if(e[j].weight<min&&e[j].flag==0)

{min=e[j].weight;k=j;}

if(t[e[k].vexh].set!=t[e[k].vext].set){

e[k].flag=1;

t[e[k].vext].set=t[e[k].vexh].set;

for(j=1;j<=n;j++)

if(t[j].set==t[e[k].vext].set)

t[j].set=t[e[k].vexh].set;

i++;

}

else

e[k].flag=2; } for(i=0;i<m;i++)

if(e[i].flag==1)

printf("%d,%d:%d\n",e[i].vexh,e[i].vext,e[i].weight);}时间复杂度为O(ne)第105页，共191页，2023年，2月20日，星期六2023/4/21105方法二：普里姆(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})为最小生成树。第106页，共191页，2023年，2月20日，星期六2023/4/21106关键:是如何找到连接U和V-U的最短边。

普里姆（Prim）算法

利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。第107页，共191页，2023年，2月20日，星期六2023/4/21107U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCFPrim算法

第108页，共191页，2023年，2月20日，星期六2023/4/21108Prim算法

251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(A,C)46,(F,C)25,(F,D)25,(F,E)26}第109页，共191页，2023年，2月20日，星期六2023/4/21109Prim算法

251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(F,D)25,(C,D)17,(F,E)26}

第110页，共191页，2023年，2月20日，星期六2023/4/21110Prim算法

251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26,(D,E)38}

第111页，共191页，2023年，2月20日，星期六2023/4/21111Prim算法

251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(A,B)34,(E,B)12}

第112页，共191页，2023年，2月20日，星期六2023/4/21112Prim算法

251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}第113页，共191页，2023年，2月20日，星期六2023/4/21113数组lowcost[n]：用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcost[v]=0表示顶点v已加入最小生成树中；数组adjvex[n]：用来保存依附于该边（集合V-U中各顶点与集合U中顶点的最短边）在集合U中的顶点。数据结构设计表示顶点vi和顶点vk之间的权值为w，其中：vi∈V-U且vk∈Ulowcost[i]=wadjvex[i]=k如何用数组lowcost和adjvex表示候选最短边集？第114页，共191页，2023年，2月20日，星期六2023/4/21114i数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出adjvexlowcostA34A46A∞A∞A19{A}{B,C,D,E,F}(AF)19adjvexlowcostA34F25F25F26

{A,F}{B,C,D,E}(FC)25adjvexlowcostA34

C17F26

{A,F,C}{B,D,E}(CD)17adjvexlowcostA34

F26

{A,F,C,D}{B,E}(FE)26adjvexlowcostE12

{A,F,C,D,E}{B}(EB)12adjvexlowcost

{A,F,C,D,E,B}{}

应用举例——最小生成树第115页，共191页，2023年，2月20日，星期六2023/4/211151.初始化两个辅助数组lowcost和adjvex；2.输出顶点u0，将顶点u0加入集合U中；3.重复执行下列操作n-1次3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；3.2输出顶点k和对应的权值；3.3将顶点k加入集合U中；3.4调整数组lowcost和adjvex；Prim算法——伪代码

第116页，共191页，2023年，2月20日，星期六2023/4/21116普里姆算法7.9voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){

//按普里姆算法从顶点u出发构造G的最小生成树，输出T的各条边。 k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//辅助数组初始化

if(j!=k)closedge[j]={u,G.arcs[k][j].adj}; closedge[k].lowcost=0;//初始状态，U＝{u} for(i=1;i<G.vexnum;++i){//选择其余G.vexnum-1个顶点

k=minimum(closedge);//求出T的下一个结点边

printf(closedge[k].adjvex,G.vexs[k]);//输出生成树的边

closedge[k].lowcost=0;//第k顶点并入U集

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

if(G.arcs[k][j].adj<closedge[j].lowcost)

//新顶点并入U后重新选择最小边

closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}//for}//MiniSpanTree时间复杂度为O(n²)第117页，共191页，2023年，2月20日，星期六2023/4/21117最小生成树算法的分析普里姆算法和图的边数无关，适合边稠密的情况。克鲁斯卡尔算法适合边稀疏的情况。第118页，共191页，2023年，2月20日，星期六2023/4/211187.5有向无环图及其应用有向无环图无环的有向图叫有向无环图，简称DAG图。应用在工程计划和管理方面有着广泛而重要的应用。描述一项工程或系统的进行进程的有效工具。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。123456第119页，共191页，2023年，2月20日，星期六2023/4/211197.5.1拓扑排序课程代号课程名称先修课C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？第120页，共191页，2023年，2月20日，星