数据结构图论部分.ppt

,Page 1,2023/6/21,第七章 图,Page 2,2023/6/21,学习目标领会图的类型定义。熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。熟练掌握图的两种遍历算法。理解各种图的应用问题的算法。重点和难点重点：图的各种应用问题的算法都比较经典，注意理解各种图的算法及其应用场合。,Page 3,2023/6/21,知识点图的类型定义图的存储表示图的深度优先搜索遍历和广度优先搜索遍历无向网的最小生成树拓扑排序关键路径最短路径,Page 4,2023/6/21,欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,图论欧拉,Page 5,2023/6/21,能否从某个地方出发，穿过所有的桥仅一次后再回到出发点？,哥尼斯堡七桥问题,Page 6,2023/6/21,七桥问题的图模型,欧拉回路的判定规则：1.如果通奇数桥的地方多于两个，则不存在欧拉回路；2.如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3.如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。,Page 7,2023/6/21,图的定义,图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。,在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。,7.1 图的定义和术语,Page 8,2023/6/21,线性表每个数据元素只有一个直接前驱和一个直接后继。树形结构每个数据元素只有一个直接前驱，但可能有多个直接后继。图形结构每个数据元素可能有多个直接前驱和多个直接后继。,图是比线性表和树复杂的数据结构，广泛应用于语言学、逻辑学、物理、化学等领域。,Page 9,2023/6/21,如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。,若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。,若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。,如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。,图的基本术语,Page 10,2023/6/21,简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。,数据结构中讨论的都是简单图。,Page 11,2023/6/21,图的基本术语,邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。,V1的邻接点：V2、V4V2的邻接点：V1、V3、V5,Page 12,2023/6/21,图的基本术语,邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。,V1的邻接点：V2、V3V3的邻接点：V4,Page 13,2023/6/21,无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。,有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。,图的基本术语,Page 14,2023/6/21,含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？,含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条边。,Page 15,2023/6/21,稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。,顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。,图的基本术语,顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。,Page 16,2023/6/21,图的基本术语,在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？,Page 17,2023/6/21,图的基本术语,在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？,Page 18,2023/6/21,权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。,图的基本术语,Page 19,2023/6/21,路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。,图的基本术语,一般情况下，图中的路径不惟一。,V1 到V4的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4,Page 20,2023/6/21,路径长度：,图的基本术语,非带权图路径上边的个数带权图路径上各边的权之和,V1 V4：长度为1V1 V2 V3 V4：长度为3V1 V2 V5V3 V4：长度为4,Page 21,2023/6/21,路径长度：,图的基本术语,非带权图路径上边的个数带权图路径上各边的权之和,V1 V4：长度为8V1 V2 V3 V4：长度为7V1 V2 V5V3 V4：长度为15,Page 22,2023/6/21,回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。,图的基本术语,Page 23,2023/6/21,子图：若图G=（V，E），G=（V，E），如果VV 且E E，则称图G是G的子图。,图的基本术语,Page 24,2023/6/21,连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(ij)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。连通分量：非连通图的极大连通子图称为连通分量。,图的基本术语,如何求得一个非连通图的连通分量?,Page 25,2023/6/21,V1,V2,V3,V4,V5,V6,V7,图的基本术语,连通分量是对无向图的一种划分。,Page 26,2023/6/21,强连通图：在有向图中，对图中任意一对顶点vi和vj(ij)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。强连通分量：非强连通图的极大强连通子图。,图的基本术语,如何求得一个非连通图的连通分量?,Page 27,2023/6/21,图的基本术语,V1,V2,Page 28,2023/6/21,生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。,生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。,如何理解极小连通子图?,图的基本术语,Page 29,2023/6/21,Page 30,2023/6/21,图的抽象数据类型定义如下：ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶 点集。数据关系R：R=VRVR|v,wV且P(v,w)，表示从v到w的 弧，谓词P(v,w)定义了弧的意义 或信息,Page 31,2023/6/21,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),Page 32,2023/6/21,CreateGraph(初始条件：图 G 存在，u 和 G 中顶点有相同特征。操作结果：若 G 中存在和 u 相同的顶点，则返回该顶点 在图中位置；否则返回其它信息。,Page 33,2023/6/21,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 的最后一个邻接点，则返回“空”。,Page 34,2023/6/21,PutVex(初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：删除 G 中顶点 v 及其相关的弧。,Page 35,2023/6/21,InsertArc(初始条件：图 G 存在，v 和 w 是 G 中两个顶点。操作结果：在 G 中删除弧，若 G 是无向的，则还 删除对称弧。,Page 36,2023/6/21,DFSTraverse(G,Visit();初始条件：图 G 存在，Visit 是顶点的应用函数。操作结果：对图 G 进行深度优先遍历。遍历过程中对每 个顶点调用函数Visit 一次且仅一次。一旦 visit()失败，则操作失败。FSTraverse(G,Visit();初始条件：图 G 存在，Visit 是顶点的应用函数。操作结果：对图 G 进行广度优先遍历。遍历过程中对每 个顶点调用函数Visit 一次且仅一次。一旦 visit()失败，则操作失败。ADT Graph,Page 37,2023/6/21,是否可以采用顺序存储结构存储图?,图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。,如何存储图?,考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。,7.2 图的存储结构,Page 38,2023/6/21,7.2 图的存储结构,数组表示法(邻接矩阵)将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。假设图中顶点数为n，则邻接矩阵A定义为,网的邻接矩阵的定义为，当vi到vj有弧相邻接时，aij的值应为该弧上的权值，否则为。,Page 39,2023/6/21,图的数组(邻接矩阵)存储表示#define INFINITY INT_MAX;/最大值#define MAX_VERTEX_NUM 20;/最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图，用1或0/表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶点信息AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧(边)数GraphKind kind;/图的种类标志 MGraph;,Page 40,2023/6/21,有向图的存储结构,G1.vexs=A,B,C,D,G1.vexnum=4,G1.arcnum=4,G1.kind=DG,Page 41,2023/6/21,有向图的邻接矩阵,如何求顶点 i 的出度？,邻接矩阵的第 i 行元素之和。,Page 42,2023/6/21,有向图的邻接矩阵,如何求顶点 i 的入度？,邻接矩阵的第 i 列元素之和。,Page 43,2023/6/21,有向图的邻接矩阵,如何判断从顶点 i 到顶点 j 是否存在边？,测试邻接矩阵中相应位置的元素arcij是否为1。,Page 44,2023/6/21,无向图的存储结构,G2.vexs=A,B,C,D,E,G2.vexnum=5,G2.arcnum=6,G2.kind=UDG,Page 45,2023/6/21,网图的存储结构,G3.vexs=A,B,C,D,E,G3.vexnum=5,G3.arcnum=8,G3.kind=UDN,Page 46,2023/6/21,如何求顶点i的度？,无向图的邻接矩阵,V1,V3,V4,V2,邻接矩阵的第i行（或第i列）非零元素的个数。,Page 47,2023/6/21,如何判断顶点 i 和 j 之间是否存在边？,无向图的邻接矩阵,V1,V3,V4,V2,测试邻接矩阵中相应位置的元素arcij是否为1。,Page 48,2023/6/21,如何求顶点 i 的所有邻接点？,无向图的邻接矩阵,V1,V3,V4,V2,将数组中第 i 行元素扫描一遍，若arcij为1，则顶点 j 为顶点 i 的邻接点。,Page 49,2023/6/21,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n。无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。邻接矩阵的优缺点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。缺点：边数较少时，空间浪费较大。,Page 50,2023/6/21,网图的邻接矩阵,网图的邻接矩阵可定义为：,Page 51,2023/6/21,7.2.2 图的邻接表表示法,引入原因邻接矩阵在稀疏图时空间浪费较大。实现为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。,每个链表附设一个表头结点。,与Vi邻接的点在表头数组中的位置,Page 52,2023/6/21,图的邻接表存储表示,#define MAX_VERTEX_NUM 20;typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置struct ArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧 AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;/顶点数组int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志 ALGraph;,Page 53,2023/6/21,无向图的邻接表,边表中的结点表示什么？,每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。,Page 54,2023/6/21,无向图的邻接表,如何求顶点 i 的度？,顶点i的边表中结点的个数。,Page 55,2023/6/21,如何判断顶点 i 和顶点 j之间是否存在边?,测试顶点 i 的边表中是否存在终点为 j 的结点。,无向图的邻接表,Page 56,2023/6/21,有向图的邻接表,如何求顶点 i 的出度？,顶点 i 的出边表中结点的个数。,Page 57,2023/6/21,有向图的邻接表,如何求顶点 i 的入度？,各顶点的出边表中以顶点 i 为终点的结点个数。,Page 58,2023/6/21,有向图的邻接表,如何求顶点 i 的所有邻接点？,遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。,Page 59,2023/6/21,网图的邻接表,Page 60,2023/6/21,优缺点优点：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；缺点：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。,逆邻接表,Page 61,2023/6/21,7.2.3 图的十字链表表示法,引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条出弧和第一条入弧的指针。,邻接表,Page 62,2023/6/21,7.2.3 图的十字链表表示法,引入原因对于同一个有向图需要同时用邻接表和逆邻接表时，不方便。实现将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条出弧和第一条入弧的指针。,逆邻接表,Page 63,2023/6/21,弧尾位置,弧头位置,弧尾相同的下一条弧指针,弧相关信息的指针,弧头相同的下一条弧指针,指向该顶点第一条入弧,指向该顶点第一条出弧,Page 64,2023/6/21,求结点的入度和出度的方法？,Page 65,2023/6/21,7.2.4 图的邻接多重表表示法,引入原因无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。有些时候需要同时找到表示同一条边的两个结点（如删除一条边）。,Page 66,2023/6/21,实现每条边用一个结点表示。,访问标记,边依附的一个顶点,边依附的另一个顶点,依附这个顶点的下一条边指针,依附这个顶点的下一条边指针,访问标记,指向第一条 依附该顶点的边,Page 67,2023/6/21,Page 68,2023/6/21,7.3 图的遍历,图的遍历从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次。可以从图中任意一个顶点出发进行遍历。遍历中需解决的问题确定一搜索路径；确保每个顶点被访问到；确保每个顶点只能被访问一次。解决方法深度优先和广度优先。设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。,Page 69,2023/6/21,7.3.1 深度优先搜索,方法从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；,若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,访问任意一个与V0邻接的顶点W1，再从W1出发；访问与W1邻接且未被访问过的任意顶点W2，再从W2出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。,Page 70,2023/6/21,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V5,Page 71,2023/6/21,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,V8,Page 72,2023/6/21,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1 图的逻辑结构,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,Page 73,2023/6/21,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V7,V2,V4,V5,V8,V3,V3,V6,V6,V7,Page 74,2023/6/21,深度优先遍历算法7.4、7.5,Boolen visitedMAX;/访问标志数组Status(*visitFunc)(int v);/函数变量void DFSTraverse(Graph G,Status(*visit)(int v)/对图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,Page 75,2023/6/21,void DFS(Graph G,int v)/从第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,Page 76,2023/6/21,深度遍历：V1,V3,V7,V6,V2,V5,V8,V4,Page 77,2023/6/21,深度遍历：V1,V3,V7,V6,V2,V4,V8,V5,Page 78,2023/6/21,广度优先搜索,方法从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,广度优先遍历的过程是以 v 为起始点，由近至远，依次访问和 v 有路径相通且最短路径长度为 1,2,的顶点。,Page 79,2023/6/21,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V1,Page 80,2023/6/21,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V2,V3,V3,Page 81,2023/6/21,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V3,V4,V4,V5,V5,Page 82,2023/6/21,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V4,V4,V5,V5,V6,V6,V7,V7,Page 83,2023/6/21,广度优先遍历序列?入队序列?出队序列?,遍历序列：,V1,V2,V3,V4,V5,V5,V6,V6,V7,V7,V8,V8,Page 84,2023/6/21,V8,V7,V6,V5,V4,V3,V2,V1,V8,V7,V6,V5,V4,V3,V2,V1,Page 85,2023/6/21,广度优先遍历算法7.6,void BFSTraverse(Graph G,Status(*visit)(int v)/对图G进行广度优先搜索遍历for(v=0;v=0;w=NextAjdVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);/访问第 w 个顶点 EnQueue(Q,w);/if/while/if DestroyQueue(Q);/BFSTraverse,123456789101112,Page 86,2023/6/21,Page 87,2023/6/21,74 图的连通性问题,7.4.1 无向图的连通分量和生成树无向图的连通分量对于连通图，仅需从图中任一顶点出发，进行DFS或BFS搜索，即可遍历图的全部顶点；对于非连通图，则需从多个顶点出发进行DFS或BFS搜索，才能遍历完图的全部顶点。每一次从一个新的起始点出发进行DFS或BFS搜索过程中所得的顶点访问序列就是各连通分量的顶点集。,Page 88,2023/6/21,Page 89,2023/6/21,深度优先遍历的结果为(3次DFS过程)从A出发：ALMJBFC从D出发：DE从G出发：GKHI连通分量：三个顶点集+依附于这个顶点集中顶点的边。,Page 90,2023/6/21,生成树所有顶点均由边连接在一起，但不存在回路的图称为生成树。一个有n个顶点的连通图的生成树有n-1条边；一个图可以有许多棵不同的生成树。对于连通图，调用DFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵深度优先生成树。对于连通图，调用BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵广度优先生成树。对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。,Page 91,2023/6/21,深度遍历,深度优先生成树,Page 92,2023/6/21,广度遍历,广度优先生成树,Page 93,2023/6/21,深度优先遍历：ALMJBFC DE GKHI,深度优先生成森林,Page 94,2023/6/21,7.4.2 最小生成树,问题描述用一个连通网表示 n 个居民点和各个居民点之间可能架设的通讯线路，网中边上的权值表示架设这条线路所需经费。在 n 个居民点间构建通讯网只需架设 n-1 条线路，则工程队面临的问题是架设哪几条线路能使总的工程费用最低？问题均等价于：在含有 n 个顶点的连通网中选择 n-1 条边，构成一棵极小连通子图，并使该连通子图中 n-1 条边上权值之和达到最小，则称这棵连通子图为连通网的最小生成树。类似此类的问题很多。,Page 95,2023/6/21,MST性质,假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。,Page 96,2023/6/21,构造最小生成树方法,方法一：克鲁斯卡尔(Kruskal)算法基本思想为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。具体作法初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量；在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；依此类推，直至T中所有顶点都在同一连通分量上为止。,Page 97,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,B,C,D,E,F,Page 98,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,B,C,D,E,F,连通分量A,B,E,C,D,F,Page 99,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,B,E,C,D,F,连通分量A,F,B,E,C,D,Page 100,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,F,B,E,C,D,连通分量A,F,B,E,C,D,Page 101,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,F,B,E,C,D,连通分量A,F,C,D,B,E,Page 102,2023/6/21,25,12,34,16,26,46,38,17,25,连通分量A,F,C,D,B,E,连通分量A,F,C,D,B,E,Page 103,2023/6/21,1.初始化：U=V；TE=；2.循环直到T中的连通分量个数为1 2.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算法伪代码,Page 104,2023/6/21,克鲁斯卡尔(Kruskal)算法,void minitree_KRUSKAL(void)int n,i,m,min,k,j;VEX tM;EDGE eM;printf(Input number of vertex and edge:);scanf(%d,%d,Page 105,2023/6/21,i=1;while(in)min=MAX;for(j=0;jm;j+)if(ej.weightmin,时间复杂度为O(ne),Page 106,2023/6/21,方法二：普里姆(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)为最小生成树。,Page 107,2023/6/21,关键:是如何找到连接U和V-U的最短边。,普里姆（Prim）算法,利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。,Page 108,2023/6/21,U=A V-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19,25,12,34,19,26,46,38,17,25,Prim算法,Page 109,2023/6/21,Prim算法,25,12,34,19,26,46,38,17,25,U=A,F V-U=B,C,D,Ecost=(A,B)34,(A,C)46,(F,C)25,(F,D)25,(F,E)26,Page 110,2023/6/21,Prim算法,25,12,34,19,26,46,38,17,25,U=A,F,C V-U=B,D,Ecost=(A,B)34,(F,D)25,(C,D)17,(F,E)26,Page 111,2023/6/21,Prim算法,25,12,34,19,26,46,38,17,25,U=A,F,C,D V-U=B,Ecost=(A,B)34,(F,E)26,(D,E)38,Page 112,2023/6/21,Prim算法,25,12,34,19,26,46,38,17,25,U=A,F,C,D,E V-U=Bcost=(A,B)34,(E,B)12,Page 113,2023/6/21,Prim算法,25,12,34,19,26,46,38,17,25,U=A,F,C,D,E,B V-U=,Page 114,2023/6/21,数组lowcostn：用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcostv=0表示顶点v已加入最小生成树中；数组adjvexn：用来保存依附于该边（集合V-U中各顶点与集合U中顶点的最短边）在集合U中的顶点。,数据结构设计,如何用数组lowcost和adjvex表示候选最短边集？,Page 115,2023/6/21,应用举例最小生成树,Page 116,2023/6/21,1.初始化两个辅助数组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算法伪代码,Page 117,2023/6/21,普里姆算法7.9,void MiniSpanTree_PRIM(MGraph G,VertexType u)/按普里姆算法从顶点 u 出发构造G的最小生成树，输出T的各条边。k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始状态，Uufor(i=1;iG.vexnum;+i)/选择其余 G.vexnum-1 个顶点 k=minimum(closedge);/求出T的下一个结点边 printf(closedgek.adjvex,G.vexsk);/输出生成树的边 closedgek.lowcost=0;/第 k 顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj.adj closedgej.lowcost)/新顶点并入U后重新选择最小边 closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree,时间复杂度为O(n),Page 118,2023/6/21,最小生成树算法的分析普里姆算法和图的边数无关，适合边稠密的情况。克鲁斯卡尔算法适合边稀疏的情况。,Page 119,2023/6/21,7.5 有向无环图及其应用,有向无环图无环的有向图叫有向无环图，简称DAG图。,应用在工程计划和管理方面有着广泛而重要的应用。描述一项工程或系统的进行进程的有效工具。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。,Page 120,2023/6/21,7.5.1 拓扑排序,学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业？,Page 121,2023/6/21,AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网。,若是图中有向边，vi是vj的直接前驱；vj是vi的直接后继。,Page 122,2023/6/21,拓扑排序把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列（拓扑序列）的过程。若网中所有顶点都在它的拓扑有序序列中，则该拓扑序列就是一个工程顺利完成的可行方案；否则，该工程无法顺利完成。拓扑排序的方法从图中选择一个入度为0的顶点输出；从图中删除该顶点及源自该顶点的所有弧；重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行。,Page 123,2023/6/21,拓扑序列,C1,Page 124,2023/6/21,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,C2,C1,拓扑序列,Page 125,2023/6/21,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12,C3,C2,C1,拓扑序列,Page 126,2023/6/21,C4,C5,C6,C7,C8,C9,C10,C11,C12,C4,C3,C2,C1,拓扑序列,Page 127,2023/6/21,C5,C6,C7,C8,C9,C10,C11,C12,C5,C4,C3,C2,C1,拓扑序列,Page 128,2023/6/21,C6,C7,C8,C9,C10,C11,C12,C7,C5,C4,C3,C2,C1,拓扑序列,Page 129,2023/6/21,C6,C8,C9,C10,C11,C12,C9,C7,C5,C4,C3,C2,C1,拓扑序列,Page 130,2023/6/21,C6,C8,C10,C11,C12,C10,C9,C7,C5,C4,C3,C2,C1,拓扑序列,Page 131,2023