华师本科生数据结构课件 第7章 图

1、1,2,图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素 之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子） 相关，但只能和上一层中一个元素（双亲）相关；而在图形结构中，结点之间 的关系可以是任意的，任意两个数据元素之间都可能相关。 图在各个领域都有着广泛的应用,如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理；另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多

2、实际问题，如果间接地用图来表示，处理起来比较方便。这些技术领域都是把图作为解决问题的主要数学手段来使用，因此，如何在计算机中表示和处理图结构，就是计算机科学需研究的一项重要课题。,3,【学习目标】,1领会图的类型定义.2熟悉图的各种存储结构及其构造算法, 了解各种存储结构的特点和选用原则.3熟练掌握图的两种遍历算法.4理解各种图的应用问题的算法. 5.了解广义表的结构和使用,4,【重点和难点】,图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。,【知识点】,图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生

3、成树、最短路径、拓扑排序、关键路径,5,第七章 习题,基础知识 P47：7.1 7.5 7.7 7.9 7.10 7.11 作业 P49：7.22 7.23 7.24 7.28 7.32 P50：7.36 7.41,6,7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 连通网的最小生成树 7.5 单源最短路径 7.6 拓扑排序 7.7 关键路径 7.8 广义表,第7章 图和广义表,7,7.1 图的基本术语,图：记为 G( V, E ) 其中：V 是G的顶点集合，是有穷非空集； E 是G的边集合，是有穷集。,问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点

4、而没有边。,有向图： 无向图： 完全图：,图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图,V=vertex E=edge,8, 完全有向图有n(n-1)条边。 证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条连线，即有2(n-1)条边， 顶点2有2(n-2)条边，顶点n-1有2条边,顶点n有0条边. 总边数2( n-1 n-210)=2(n-1+0)n/2= n(n-1),完全无向图有n(n-1)/2 条边。

5、证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，顶点n-1有1条边,顶点n有0条边. 总边数 n-1 n-210=（n-1+0)n/2= n(n-1)/2,9,例：判断下列4种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1) 条边,G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,10,图G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,图G2中：V(G2)=1,2,3,4

6、,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),11,稀疏图：稠密图：,设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。,子 图：,边较少的图。通常边数n2 边很多的图。无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近n(n-1),12,带权图：,即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。,连通图：,在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图

7、。 非连通图的极大连通子图叫做连通分量。,带权图,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。,强连通图：,网 络：,有两类图形不在本课程讨论之列：,13,邻接点：,有向边(u, v)称为弧，边的始点u叫弧尾，终点v叫弧头,顶点v的度是与它相关联的边的条数。记作D(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,若 (u, v) 是 E

8、(G) 中的一条边，则称 u 与 v 互为邻接顶点,弧头和弧尾：,度、入度和出度：,生成树：,是一个极小连通子图,它含有图中全部顶点,但只有n-1条边。 如果在生成树上添加1条边，必定构成一个环。 若图中有n个顶点，却少于n-1条边，必为非连通图。,生成森林：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,答：是树！而且是一棵有向树！,14,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回 路：,例：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,路径：,

9、在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。,15,16,路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7

10、 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1,17,连通图,强连通图,非连通图 连通分量,18,CreatGraph( /从顶点v起广度优先遍历图G,并对每个顶点调用Visit一次。,结构的建立和销毁 对顶点的访问操作 插入或删除顶点 插入和删除 对邻接点的操作 遍历,基本操作,19,7.2 图的存储结构,图的特点：非线性结构（m :n ）,邻接表 邻接多重表 十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言） 但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法 邻接表(链式)表示法

11、,20,一、邻接矩阵(数组)表示法,建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn，定义为：,例：,邻接矩阵：,A.Edge =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,分析1：无向图的邻接矩阵是对称的； 分析2：顶点i 的度第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。,0 1 0 1 0 1 0 1 0 1

12、 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,顶点表：,21,例 ：有向图的邻接矩阵,分析1：有向图的邻接矩阵可能是不对称的。 分析2：顶点的出度=第i行元素之和，OD( Vi )= A.Edge i j 顶点的入度=第i列元素之和。ID( Vi )= A.Edge j i 顶点的度=第i行元素之和+第i列元素之和, 即：TD(Vi)=OD( Vi ) + ID( Vi ),邻接矩阵：,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0

13、0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,22,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,特别讨论 ：网（即有权图）的邻接矩阵,定义为：,以有向网为例：,邻接矩阵：, ,N.Edge =,( v1 v2 v

14、3 v4 v5 v6 ),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,23,注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, AG,AN GraphKind; /有向/无向图，有向/无向网 Typedef struct ArcCell /弧（边）结点的定义 VRType adj; /顶点间关系，无权图取1或0；有权图取权值类型 InfoType *

15、info; /该弧相关信息的指针 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ; Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可 AdjMatrix arcs; /邻接矩阵 int vernum, arcnum; /顶点总数，弧（边）总数 GraphKind kind; /图的种类标志 Mgraph;,图的邻接矩阵存储表示,对于n个顶点的图或网，空间效率=O(n2),24,Status CreateUDN(Mgraph /CreateUDN,例：用邻接矩阵

16、生成无向网的算法,对于n个顶点e条弧的网， 建网时间效率 = O(n2+n+e*n),25,二、邻接表(链式)表示法,对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；,每个单链表还应当附设一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi一个邻接点的位置,链域，指向vi下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi 信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,26,例：无向图的邻接表,邻接表,例：有向图的邻接表,邻接表(出边),注：邻接表不唯一，因各

17、个边结点的链入顺序是任意的。,当邻接表的存储结构形成后，图便唯一确定！,27,分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2: 在有向图中,邻接表中除了n个头结点外,只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？ 怎样计算有向图顶点的入度？ 怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD( Vi )

18、=单链表中链接的结点个数,OD( Vi )单链出边表中链接的结点数 I D( Vi ) 邻接点为Vi的弧个数,TD( Vi ) = OD( Vi ) + I D( Vi ),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,28,讨论：邻接表与邻接矩阵有什么异同之处？,联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)

19、。 用途：邻接矩阵多用于稠密图的存储(e接近n(n-1)/2)；而邻接表多用于稀疏图的存储(en2),29,图的邻接表存储表示,#define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef struct ArcNode int adjvex; /该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针 ArcNode； Typedef struct VNode /顶点结构 VertexType data; /顶点信息 ArcNode * firstarc; /指向依附该顶点的第一

20、条弧的指针 VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /图结构 AdjList vertics ; /应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志） ALGraph; /图结构,空间效率为O(n+2e)或O(n+e) 时间效率为O(n+e*n),30,void CreateUDG(ALGraph /for / CreateUDG,31,一、深度优先搜索 二、广度优先搜索,7.3 图的遍历,遍历定义：从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使

21、每个顶点仅被访问一次,就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。 图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路：可设置一个辅助数组 visited n ，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。,图常用的遍历：,怎样避免重复访问？,32,深度优先搜索(DFS),V2,V4,V8,V5,V3,V6,V7,生成树 遍历序列,广度优先搜索(BFS),V2,V3,V4,V5,V6,

22、V7,V8,最短路径！,图的遍历-例子,33,一、深度优先搜索( DFS ),基本思想：仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 结果,v4 v6,起点,起点,遍历步骤,1、深度优先搜索: 有向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。 如：结点5的邻接结点有两个6、7，则先访问结点6，再访问结点7。,5,6,7,2,4,1,3,5,6,7,2,3,1,4,从结点 出发的搜索序列： 5、6、2、3、1、4、7 适用的数据结构：栈,5,1,

23、2,4,3,从结点 出发的搜索序列： 1、2、3、4没有搜索 到所有的结点，必 须另选图中未访 问过的结点， 继续进行 搜索。,1,35,一、深度优先搜索遍历图,连通图的深度优先搜索遍历：从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V ; for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍

24、历;,解决的办法是:为每个顶点设立一个“访问标志visitedw”;,2. 如何判别V的邻接点是否被访问？,36,深度优先搜索（遍历）步骤：,详细归纳： 在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1； 再从w1出发,访问与w1邻接但还未被访问过的顶点w2； 然后再从w2出发,进行类似的访问, 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。 如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问； 如果没有,就再退回一步进行搜索。 重复上述过程,直到连通图中所有顶点都被访问

25、过为止。,简单归纳： 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点； 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,37,讨论1：计算机如何实现DFS？,DFS 结果,邻接矩阵 A,辅助数组 visited n ,起点,v2v1v3v5v4v6,开辅助数组 visited n ！,例：,38,讨论2：DFS算法如何编程？,DFS1(A, n, v) visit（v）; visitedv=1; for( j=1; j=n; j+) if ( Av, j ,可以用递归算法！,/Ann为邻接矩阵，v为起始顶点(编号）,/访问（例如打印）顶点v,Av,j 1 有邻接点,vis

26、ited n =0 未访问过,/访问后立即修改辅助数组标志,/从v所在行从头搜索邻接点,建议：在递归函数中增加一计数器sum，初值为n，每访问一次就减1,减到0则return，可避免递归时间过长。,39,讨论3：在图的邻接表中如何进行DFS？,v0 v1 v2 v3,DFS 结果,辅助数组 visited n ,例：,照样借用visited n ！,起点,0 1 2 3,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。,40,讨论4：邻接表的DFS算法如何编程？,DFS2(List, v, p) visit（v）; visitedv=1; p=p-link; if (!p

27、) return; v=p-data; while ( !visitedv ) DFS2(list, v, p); return; ,仍可用递归算法,41,void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); /对尚未访问的顶点调用DFS ,首先将图中每个顶点的访问标志设为

28、 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,42,void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for (w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); /对v的尚未访问的邻接顶点w递归调用DFS / DFS,时间复杂性： 邻接矩阵: O(n2) 邻接表: O(n+e) n：结点数 e：

29、边数,结论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。,43,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,a,c,h,d,k,f,e,44,二、广度优先搜索( BFS ),基本思想：仿树的层次遍历过程。,Breadth_First Search,v1,BFS 结果:,例：,例：,v3 ,BFS 结果:,v4 v5 ,起点,遍历步骤,起点,v2 v1 v6 ,v9 v8 v7,无向图的实例：为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。 结点1的邻接结点有

30、三个2、12、11，则先访问结点2、11，再访问结点12。,广度(宽度)优先搜索:,图的广度优先的访问次序： 1、2、11、12、3、6、7、10、4、5、8、9 适用的数据结构：队列,1,2,12,11,3,6,7,10,4,5,8,9,1,2,12,11,3,6,7,10,4,5,8,9,队列的变化：,广度（宽度）优先搜索:,A,B,C,D,E,F,G,H,I,J,K,L,树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L 适用的数据结构：队列,A,B,C,D,1、结点A进队,2、结点A出队、访问，队空 3、结点A的儿子结点进队 4、结点B出队、访问 5、结点B的

31、儿子结点进队 6、结点C出队、访问 7、结点C的儿子结点进队,C,D,E,F,G,C,D,E,F,G,D,E,F,G,D,H,47,广度优先搜索（遍历）步骤,简单归纳： 在访问了起始点v之后，依次访问 v的邻接点； 然后再依次访问这些顶点中未被访问过的邻接点； 直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,48,讨论1：计算机如何实现BFS？,邻接表,除辅助数组visited n 外，还需再开一辅助队列！,例：,起点,辅助队列,v2已访问过了,BFS 遍

32、历结果,入队！,初始f=n-1,r=0,49,讨论2：BFS算法如何编程？,BFS1(List, n, v) Visit(v); Visitedv=1; front=n-1; rear=0; qrear=v; while(rear!=front) front=(front+1)%n; v=qfront; p=Listv.firstarc; while ( !p ) if(! Visitedadjvex(p) ) Visit(adjvex(p); Visitedadjvex(p)=1; rear=(rear+1)%n; qrear= adjvex(p) p=nextarc(p); return

33、,层次遍历应当用队列！,/List为邻接表，v为起点，Qn为辅助队列,/访问（例如打印）顶点v并修改标志,/指向单链表中下一个邻接点,/队列指针初始化,/起始点入队,/队不空时,/访问过的顶点出队,/P指向第1个邻接点,/未到表尾，且邻接域未访问过，,/则先输出再改标/记，最后再入队,图的广度遍历程序,使用的变量说明：Boolean visitedMAX;/用于标识结点是否已被访问过 Status (*VisitFunc)(int v); /函数变量,void BFSTraverse( Graph G, Status ( * VisitFunc) (int v); VisitFunc = Vi

34、sit; for (v=0;vG.vexnum;+v) visitedv=FALSE; InitQueue(Q); for (v=0; vG.vexnum; +v) if (!Visitedv) Visited v = TRUE; Visit(v); EnQueue(Q,v); while (!EmptyQueue(Q) DeQueue(Q,u); for (w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if (!Visitedw) Visitedv =TRUE; Visit(v); EnQueue(Q, w) ; ,时间复杂性： 邻接矩阵：O(n2) 邻接

35、表: O(n+e) n：结点数 e：边数,51,BFS 算法效率分析:,DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用了堆栈或队列）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,52,图的广度遍历演示,53,54,55,求迷宫的最短路径,迷宫简介,迷宫可用一个二维位

36、数组表示，0表示连通，1表示不连通。连通方向又分为4连通和八连通两种。,如下图所示，右图表示了一个八连通的所有方向所形成的有向图。,最后形成有向图,56,g = i+div h = j+div v = 0,1,2,3,4,5,6,7,（1）如何得到和迷宫相应的有向图,求迷宫的最短路径,57,（2）如何得到路径,求迷宫的最短路径,58,数据结构：,求迷宫的最短路径,程序：,链式队列：纪录搜索过程,堆栈：保存结果,求m行n列的迷宫maze中从入口00到出口m-1n-1的最短路径，若存在，则返回TRUE，此时栈S中从栈顶到栈底为最短路径所经过的各个方位;若该迷宫不通，则返回FALSE，此时栈S为空栈

37、。,该路口可行条件： 若 0=npos,xposm-1, 0=npos,yposn-1, Mazenpos.xposnpos.ypos=0 , visitednpos.xposnpos.ypos=FALSE 则Pass函数为TRUE,否则为FALSE,堆栈操作程序,最短路径程序,迷宫搜索程序,队列处理程序堆栈,数组：表示迷宫、已到位置和方向,59,ypedef struct int xpos; int ypos; PosType; typedef struct DQNode PosType seat; struct DQNode *next; DQNode *pre; DQNode, *DQu

38、encePtr; typedef struct DQuencePtr fronr; DQuencePtr rear; DLinkQuence; void InitQuence( DLinkQuence ,60,bool ShortestPath(int maze,int m,int n,Stack /ShortestPath,时间复杂度：O(m*n),int Pass( PosType npos ) if ( npos,xpos=0 ,61,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：对连通图

39、进行遍历，得到的是什么？ 得到的将是一个极小连通子图，即图的生成树！ 由深度优先搜索得到的生成树，称为深度优先搜索生成树。 由广度优先搜索得到的生成树，称为广度优先搜索生成树。 思考2：对非连通图进行遍历，得到的是什么？ 得到的将是各连通分量的生成树，即图的生成森林！,7.4 连通图的小生成树,求图的生成树,生成树的特征n个顶点的连通网络的生成树有n个顶点、n-1条边。,求生成树的方法DFS(深度优先搜索)和BFS(广度优先搜索),62,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n1条线路，使

40、总费用最少？,典型用途：,数学模型： 顶点表示城市，有n个； 边表示线路，有n1条； 边的权值表示线路的经济代价； 连通网表示n个城市间通信网。,显然此连通网是一个生成树！,问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree),63,例：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,64,有多种算法，但最常用的是以下两种：,最小生成树的 MST 性质如下：,Kruskal（克鲁斯卡尔）算法 Prim（普里姆）算法,Kr

41、uskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。 这两个算法，都是利用MST 性质来构造最小生成树的。,若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在最小生成树上。,应用：n个城市建网，如何选择n1条线路，使总费用最少？,求最小生成树,目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。,65,步骤： (1) 首先构造一个只有n个顶点但没有边的非连通图T=V, 图中每个顶点自成一个连通分量。 (2) 当在边集 E 中选到一条具有最小权值的边时,若该边的两

42、个顶点落在T中不同的连通分量上，则将此边加入到生成树的边集合T 中；否则将此边舍去，重新选择一条权值最小的边。 (3) 如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求（最小生成树）。,一、克鲁斯卡尔(Kruskal)算法,设N =V,E 是有n个顶点的连通网，,Kruskal算法采用邻接表作为图的存储表示,66,例：应用克鲁斯卡尔算法构造最小生成树的过程,67,Kruskal（克鲁斯卡尔）算法,例 ：,a,e,d,c,b,g,f,14,8,5,3,16,21,例如:,7,12,18,19,68,计算机内怎样实现Kruskal算法？,设计思路： 设每条边对应的结构类型为：,特

43、点：将边归并适于求稀疏网的最小生成树。 故采用邻接表作为图的存储表示。, 取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时log2(e)； 重复上一步，注意每次加入时要判断是否“多余”（即是否已被新表中的连通分量包含）； 直到堆空。,显然，Kruskal算法的时间效率O(elog2e),初态：按权值排序(以堆排序为佳，堆顶即为权值最小的边）,69,算法描述:,构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使S

44、T中产生回路，则输出边(u,v); 且k+; ,最小代价生成树,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,1,2,4,3,5,6,1,5,3,4,2,5,5,最小代价生成树（简称：最小生成树）,实例的执行过程,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,图G,1、初始连通分量：1,2,3,4,5,6 2、反复执行添加、放弃动作。条件：边数 不等于n-1时 边 动作 连通分量 (1,3) 添加 1,3,4,5,6,2 (4,6) 添加 1,3,4, 6,2,5 (2,5) 添加 1,3,4, 6,2,5 (3,6) 添加 1,3,4, 6,2,5 (1,

45、4) 放弃 因构成回路 (3,4) 放弃 因构成回路 (2,3) 添加 1,3,4,5,6,2,最小代价生成树,1,2,4,3,5,6,1,5,3,4,2,5,5,算法实现要点: 每个结点增加一个数据场，用于标识该结点所属的集合。可用于判断新的边加入后是否构成回路。,71,（0）用顶点数组和边数组存放顶点和边信息 （1）初始时，令每个顶点的set互不相同；每个边的flag为0 （2）选出权值最小且flag为0的边 （3）若该边依附的两个顶点的set 值不同，即非连通，则令 该边的flag=1, 选中该边；再令该边依附的两顶点的集合 以及两集合中所有顶点的set相同 若该边依附的两个顶点的set

46、值相同，即连通，则令该 边的flag=2, 即舍去该边 （4）重复上述步骤，直到选出n-1条边为止,顶点结点： typedef struct int data; /顶点信息 int set; VEX;,边结点： typedef struct int vexs, vexe; /边依附的两顶点 int score; /边的权值 int flag; /标志域 EDGE;,72,1,1,1,1,1,4,2,1,1,1,2,2,2,2,2,73,取图中任意一个顶点v作为生成树的根,之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边,并且该边的权值在所有连通顶点v和w之

47、间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。,二、普里姆(Prim)算法,一般情况下所添加的顶点应满足下列条件:在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,74,（1）初始状态：U =u0 ,（ u0V）， TE= , （2）从E中选择顶点分别属于U、V-U两个集合、且权值最小的边（ u0, v0)，将顶点v0归并到集合U中，边（u0, v0)归并到TE中； （3）直到U=V为止。此时TE中必有n-1条边，T(V,TE)就

48、是最小生成树。,设：N =（V,E）是个连通网， 另设U为最小生成树的顶点集，TE为最小生成树的边集。,构造步骤:,普利姆(Prim)算法,75,1,76,例如:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和=14+8+3+5+16+21 = 67,例：,1,注：在最小生成树的生成过程中，所选的边都是一端在 V-U中，另一端在U中。,77,设计思路： 增设一辅助数组Closedgen， 每个数组分量都有两个域：,要求：使Colsedgei.lowcost = min(u ,vi) uU,计算机内怎样实现Prim（普里姆）算法？,Prime算法特点: 将顶点归并，与

49、边数无关，适于稠密网。 故采用邻接矩阵作为图的存储表示。,vi 在U中的邻点u,Colsedgei,V-U中顶点vi,u与vi之间对应的边权,从u1un中挑,78,具体示例：,1,2,3,4,5,6,1, 3,2, 4, 5, 6,1,3,6,2, 4,5,1,3, 6,4,2, 5,1,3,6,4,2,5,1,3,6,4,2,5,1,3,起点,4,6,2,4,5,2,3,5,1 2 3 4 5 6,显然，Prim算法的时间效率O(n2),79,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,19 m m

50、 14 m 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14 12 m 8 m 16 m m m 21 m 27 18 m m m 16 27,80,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,81,7.5 求最短路径,两种常见的最短路径问题： 一、 单源最短路径用Dijkstra（迪杰斯特拉）算法 二、所有顶点间的最短路径用Floyd（弗洛伊德）算法,典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间

51、）最少？ 问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。,（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）,任意两顶点之间,一顶点到其余各顶点,82,一、最短路径,用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径,从某个源点到其余各顶点的最短路径,13,8,13,19,21,20,83,二、单源最短路径 (Dijkstra算法),目的：设一有向图

52、G=(V,E)，已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。,例1：,源点,从FA的路径有4条： FA： 24 FBA： 518=23 FBCA：5+7+9=21 FDCA：25+12+9=36,又： 从FB的最短路径是哪条？ 从FC的最短路径是哪条？,84,10,30,100,例：,60,0 1 2 3 4,50,90,70,讨论：计算机如何自动求出这些最短路径？,60,85,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。,

53、v2,求最短路径的迪杰斯特拉算法：,一般情况下， Distk = 或者 = + ,设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。,86,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点:,路径长度最短的最短路径的特点:,它只可能有两种情况:或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是，直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由

54、两条弧组成)； 或者是，从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)； 或者是，从源点经 过已求得最短路径的顶点，再到达该顶点。,87,三、迪杰斯特拉(Dijkstra)算法思想,按路径长度递增次序产生最短路径算法： 把V分成两组： (1) S：已求出最短路径的顶点的集合 (2) V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中，保证 (1) 从源点V0到S中各顶点的最短路径长度都不大于从V0到T中 任何顶点的最短路径长度 (2) 每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶

55、点作中间顶点的最 短路径长度,依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之 和（反证法可证）,88,算法描述：,（1）设Ann为有向网的带权邻接矩阵，Aij表示弧(vi，vj )权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为v0.辅助数组distn为各终点当前找到的最短路径的长度，它的初始值为 distiAv0,i /即邻接矩阵中第v0行的权值,（2）选择u，使得 distumindistw|wV-S /w是S集之外的顶点 /distu是从源点v0到S集外所有顶点的弧中最短的一条 S=Su /将u加入

56、S集,（3）对于所有不在S中的终点w，若 distu+ Au,w distw /即(v0,u)(u,w)(v0,w) 则修改distw为： distw distu+ Au,w,（4）重复操作(2)、(3)共n-1次，由此求得从v0到各终点的最短路径。,89,20 0 10 30 max max max,Dist7,20 0 10 30 15 max max,Dist7,Path77,S=b,Dist和Path的初始状态， 从中求得从b到c的最短路径,b,a,c,b,b,d,Path77,S=b,c,修改Dist和Path的值， 从中求得从b到e的最短路径,b,a,c,b,b,d,c,b,e,单

57、元最短路径算法执行过程示例,90,20 0 10 27 15 max 30,Dist7,20 0 10 27 15 max 29,Dist7,Path77,S=b,c,e,Dist和Path的初始状态， 从中求得从b到a的最短路径,b,a,c,b,Path77,S=b,c,e,a,修改Dist和Path的值， 从中求得从b到d的最短路径,b,a,c,b,b,c,c,b,e,单元最短路径算法执行过程示例,a,b,g,e,d,b,c,e,d,c,b,e,b,c,e,g,91,20 0 10 27 15 max 29,Dist7,20 0 10 27 15 max 29,Dist7,Path77,S=b,c,e,a,d,Dist和Path的初始状态， 从中求得从b到g的最短路径