数据结构图论部分课件

DataStructure第七章图100865104/2/20231学习目标领会图的类型定义。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法。理解各种图的应用问题的算法。重点和难点重点：图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。4/2/20232知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历无向网的最小生成树拓扑排序关键路径最短路径4/2/20233能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？哥尼斯堡七桥问题

4/2/20235CADB七桥问题的图模型欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。4/2/20236图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。7.1图的定义和术语4/2/20237如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。

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

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

数据结构中讨论的都是简单图。4/2/202310图的基本术语

邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V54/2/202311无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

图的基本术语

V1V2V3V1V2V3V44/2/202313含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V44/2/202314稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。图的基本术语

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。4/2/202315V1V2V3V4图的基本术语

在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？evODvIDiiii==åå==11)()(nn4/2/202317权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。图的基本术语

V1V2V3V427854/2/202318路径：在无向图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

V1V2V3V4V1V2V5V3V44/2/202319路径长度：图的基本术语

非带权图——路径上边的个数带权图——路径上各边的权之和V1V4：长度为8V1V2V3V4：长度为7V1V2V5V3V4：长度为15V1V2V3V4V52563284/2/202321回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。图的基本术语

V1V2V3V4V5V1V2V3V44/2/202322子图：若图G=（V，E），G'=（V'，E'），如果V'V且E'

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

V1V2V3V4V5V1V2V3V4V5V1V3V44/2/202323连通分量1

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

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

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

图的基本术语

如何求得一个非连通图的连通分量?4/2/202326V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成森林4/2/202329图的抽象数据类型定义如下：ADTGraph{数据对象V

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

点集。数据关系R

：

R={VR}

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

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

或信息}4/2/202330G1=(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)}4/2/202331

CreateGraph(&G,V,VR);

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

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

DestroyGraph(&G);

初始条件：图G存在。

操作结果：销毁图G。

LocateVex(G,u);

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

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

在图中位置；否则返回其它信息。 4/2/202332 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的最后一个邻接点，则返回“空”。4/2/202333

PutVex(&G,v,value);

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

操作结果：对v赋值value。

InsertVex(&G,v);

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

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

DeleteVex(&G,v);

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

操作结果：删除G中顶点v及其相关的弧。4/2/202334 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>。4/2/202335 DFSTraverse(G,Visit());

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

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

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

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

FSTraverse(G,Visit());

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

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

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

visit()失败，则操作失败。}ADTGraph4/2/202336是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。7.2图的存储结构4/2/2023377.2图的存储结构数组表示法(邻接矩阵)将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。假设图中顶点数为n，则邻接矩阵A定义为网的邻接矩阵的定义为，当vi到vj有弧相邻接时，aij的值应为该弧上的权值，否则为∞。4/2/202338图的数组(邻接矩阵)存储表示#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;4/2/202339有向图的存储结构G1BDACG1.vexs=[A,B,C,D]G1.vexnum=4G1.arcnum=4G1.kind=DG4/2/202340有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。4/2/202341有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。4/2/202342有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素arc[i][j]是否为1。4/2/202343无向图的存储结构AECBDG2G2.vexs=[A,B,C,D,E]G2.vexnum=5G2.arcnum=6G2.kind=UDG4/2/202344网图的存储结构ADEBC75318642G3G3.vexs=[A,B,C,D,E]G3.vexnum=5G3.arcnum=8G3.kind=UDN4/2/202345如何求顶点i的度？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。4/2/202346如何判断顶点i和j之间是否存在边？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arc[i][j]是否为1。4/2/202347如何求顶点i的所有邻接点？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第i行元素扫描一遍，若arc[i][j]为1，则顶点j为顶点i的邻接点。4/2/202348特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²。无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。邻接矩阵的优缺点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、

入度）。缺点：边数较少时，空间浪费较大。4/2/202349网图的邻接矩阵网图的邻接矩阵可定义为：

arc[i][j]＝

wij

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

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

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

V3V40123vertexfirstedgeV1V3V4V2无向图的邻接表4/2/202355有向图的邻接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的出度？顶点i的出边表中结点的个数。4/2/202356有向图的邻接表V1V2V3V412∧2∧0∧V1V2

V3V40123vertexfirstedge∧如何求顶点i的入度？各顶点的出边表中以顶点i为终点的结点个数。4/2/202357有向图的邻接表V1V2V3V412∧3∧0∧V1V2

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

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

V1遍历序列：V1V2

V2V4

V4V5

V54/2/202370深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V8

V84/2/202371深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?6.1图的逻辑结构V1V3V2V4V5V6V7V8

V1遍历序列：V1V2

V2V4

V4V5V84/2/202372深一层递归递归返回深度优先遍历序列?入栈序列?出栈序列?V1V3V2V4V5V6V7V8

V1遍历序列：V1

V7V2V4V5V8V3

V3V6

V6V74/2/202373深度优先遍历算法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}4/2/202374voidDFS(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}//DFS4/2/202375V1V2V4V5V3V7V6V8深度遍历：V10123V1V3V4V2datafirstarc1672^^^adjvexnext4V5530^40171^V6V7V8567625243^^^V3V7V6V2V5V8V44/2/202376V1V2V4V5V3V7V6V80123V1V3V4V2datafirstarc1672^^^adjvexnext4V55^371^V6V7V85676^^^深度遍历：V1V3V7V6V2V4V8V54/2/2023777.3.2广度优先搜索方法从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。广度优先遍历的过程是以v为起始点，由近至远，依次访问和v有路径相通且最短路径长度为1,2,…的顶点。4/2/202378广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V14/2/202379广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V2V3V34/2/202380广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V3V4V4V5V54/2/202381广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V4V5V5V6V6V7V74/2/202382广度优先遍历序列?入队序列?出队序列?V1V3V2V4V5V6V7V8遍历序列：V1V2V3V4V5V5V6V6V7V7V8V84/2/202383V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V14/2/202384广度优先遍历算法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

124/2/2023851423501231342datafirstarc4432^^^adjvexnext450^40032^114/2/2023867·4图的连通性问题7.4.1无向图的连通分量和生成树无向图的连通分量对于连通图，仅需从图中任一顶点出发，进行DFS或BFS搜索，即可遍历图的全部顶点；对于非连通图，则需从多个顶点出发进行DFS或BFS搜索，才能遍历完图的全部顶点。每一次从一个新的起始点出发进行DFS或BFS搜索过程中所得的顶点访问序列就是各连通分量的顶点集。4/2/202387ABLMCFDEGHKIJ邻接表1211109876543210MLKJIHGFEDCBA11521120043010871066121176129011914/2/202388深度优先遍历的结果为(3次DFS过程)从A出发：ALMJBFC从D出发：DE从G出发：GKHI连通分量：三个顶点集+依附于这个顶点集中顶点的边。DEGHKIABLMCFJ4/2/202389生成树所有顶点均由边连接在一起，但不存在回路的图称为生成树。一个有n个顶点的连通图的生成树有n-1条边；一个图可以有许多棵不同的生成树。对于连通图，调用DFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵深度优先生成树。对于连通图，调用BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵广度优先生成树。对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。4/2/202390V1V2V4V5V3V7V6V8V7V6V3V5V8V4V2V1深度遍历V1V2V4V5V3V7V6V8深度优先生成树4/2/202391V1V2V4V5V3V7V6V8V8V7V6V5V4V3V2V1广度遍历V1V2V4V5V3V7V6V8广度优先生成树4/2/202392ABLMCFDEGHKIJ深度优先遍历： ALMJBFC

DE

GKHIABLMCFJDEGHKI深度优先生成森林4/2/2023937.4.2最小生成树问题描述用一个连通网表示n个居民点和各个居民点之间可能架设的通讯线路，网中边上的权值表示架设这条线路所需经费。在n个居民点间构建通讯网只需架设n-1条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？问题均等价于：在含有n个顶点的连通网中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。类似此类的问题很多。165432713179181275241016543271395104/2/202394MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。顶点集UV－Uu'vv'u顶点集T1T24/2/202395构造最小生成树方法方法一：克鲁斯卡尔(Kruskal)算法基本思想为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出n-1条互不构成回路的权值最小边为止。具体作法初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量；在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；依此类推，直至T中所有顶点都在同一连通分量上为止。4/2/202396251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}4/2/202397251234162646381725ABEDCFABEDCF连通分量＝{A},{B},{C},{D},{E},{F}12连通分量＝{A},{B,E},{C},{D},{F}4/2/202398251234162646381725ABEDCFABEDCF连通分量＝{A},{B,E},{C},{D},{F}12连通分量＝{A,F},{B,E},{C},{D}164/2/202399251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C},{D}12连通分量＝{A,F},{B,E},{C,D}16174/2/2023100251234162646381725ABEDCFABEDCF连通分量＝{A,F},{B,E},{C,D}12连通分量＝{A,F,C,D},{B,E}1617254/2/2023101251234162646381725ABEDCFABEDCF连通分量＝{A,F,C,D},{B,E}12连通分量＝{A,F,C,D,B,E}161725264/2/20231021.初始化：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算法——伪代码4/2/2023103克鲁斯卡尔(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;}4/2/2023104 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)4/2/2023105方法二：普里姆(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})为最小生成树。4/2/2023106关键:是如何找到连接U和V-U的最短边。

普里姆（Prim）算法

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

4/2/2023108Prim算法

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}4/2/2023109Prim算法

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

4/2/2023110Prim算法

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

4/2/2023111Prim算法

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

4/2/2023112Prim算法

251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}4/2/2023113数组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表示候选最短边集？4/2/2023114i数组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}{}

应用举例——最小生成树4/2/20231151.初始化两个辅助数组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算法——伪代码

4/2/2023116普里姆算法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²)4/2/2023117最小生成树算法的分析普里姆算法和图的边数无关，适合边稠密的情况。克鲁斯卡尔算法适合边稀疏的情况。4/2/20231187.5有向无环图及其应用有向无环图无环的有向图叫有向无环图，简称DAG图。应用在工程计划和管理方面有着广泛而重要的应用。描述一项工程或系统的进行进程的有效工具。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。1234564/2/20231197.5.1拓扑排序课程代号课程名称先修课C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？4/2/2023120AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork)，简称AOV网。C1C2C3C4C5C6C7C8C9C10C11C12若<vi,vj>是图中有向边，vi是vj的直接前驱；vj是vi的直接后继。4/2/2023121拓扑排序把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列（拓扑序列）的过程。若网中所有顶点都在它的拓扑有序序列中，则该拓扑序列就是一个工程顺利完成的可行方案；否则，该工程无法顺利完成。拓扑排序的方法从图中选择一个入度为0的顶点输出；从图中删除该顶点及源自该顶点的所有弧；重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行。4/2/2023122C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列C14/2/2023123C2C3C4C5C6C7C8C9C10C11C12C2C1拓扑序列4/2/2023124C3C4C5C6C7C8C9C10C11C12C3C2C1拓扑序列4/2/2023125C4C5C6C7C8C9C10C11C12C4C3C2C1拓扑序列4/2/2023126C5C6C7C8C9C10C11C12C5C4C3C2C1拓扑序列4/2/2023127C6C7C8C9C10C11C12C7C5C4C3C2C1拓扑序列4/2/2023128C6C8C9C10C11C12C9C7C5C4C3C2C1拓扑序列4/2/2023129C6C8C10C11C12C10C9C7C5C4C3C2C1拓扑序列4/2/2023130C6C8C11C12C11C10C9C7C5C4C3C2C1拓扑序列4/2/2023131C6C8C6C11C10C9C7C5C4C3C2C1拓扑序列C124/2/2023132C8C12C12C6C11C10C9C7C5C4C3C2C1拓扑序列4/2/2023133C8C12C6C11C10C9C7C5C4C3C2C1拓扑序列C84/2/2023134C12C6C11C10C9C7C5C4C3C2C1拓扑序列C8C1C2C3C4C5C6C7C8C9C10C11C12课程代号课程名称先修课C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析一个AOV网的拓扑序列不是唯一的编程如何实现？4/2/2023135321040122inlink4432^^^vexnext3^14^130012345^top16toptop123456邻接表结点的入度入度为0的顶点入栈4/2/20231360122inlink5543^^^vexnext3^25^240123456^输出序列：63210416toptop1234564/2/20231370122inlink5543^^^vexnext3^25^240123456^输出序列：6321041topp1234564/2/20231380122inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp1234564/2/20231390122inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp1234564/2/20231400112inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp1234564/2/20231410112inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp=NULL1234564/2/20231420112inlink5543^^^vexnext2^25^240123456^输出序列：61321041toptop1234564/2/20231430112inlink5543^^^vexnext2^25^240123456^输出序列：6132104topp1234564/2/20231440102inlink5543^^^vexnext2^25^240123456^输出序列：6132104topp41234564/2/20231450102inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top1234564/2/20231460102inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top1234564/2/20231470002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top31234564/2/20231480002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top31234564/2/20231490002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top31234564/2/20231500001inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top31234564/2/20231510001inlink5543^^^vexnext2^25^240123456^输出序列：6132104p=NULL4top31234564/2/20231520001inlink5543^^^vexnext2^25^240123456^输出序列：613321044top31234564/2/20231530001inlink5543^^^vexnext2^25^240123456^输出序列：613321044topp1234564/2/20231540001inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp1234564/2/20231550001inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp1234564/2/20231560000inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp21234564/2/20231570000inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp21234564/2/20231580000inlink5543^^^vexnext1^25^240123456^输出序列：613321044top2p=NULL1234564/2/20231590000inlink55