【精品数据结构课件】图

1、2020/9/5,1,第7章 图,本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算 教学难点：图结构存储方式的选择，几种经典图算法的实现 本章内容：图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,2020/9/5,2,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2020/9/5,3,图（G

2、raph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。 在线性结构中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及

3、数学的其它分支中。,2020/9/5,4,7. 1 .1 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) V = x | x 某个数据对象 ， 是顶点的有穷非空集合； R边的有限集合 R = (x, y) | x, y V 无向图 或 R = | x, y V /邻接矩阵类型 typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的顶点数和弧数 MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀

4、疏矩阵，因此会造成一定存储空间的浪费。,2020/9/5,23,建立邻接矩阵算法: void CreateMGraph(MGraph ,j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; return; ,2020/9/5,24,void PrintMGraph(MGraph G) /输出 int i,j; printf(Output Vertices:); printf(%s,G.vexs); printf(n); printf(Output AdjMatrix:n); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+

5、) printf(%4d,G.arcsij); printf(n); return; ,2020/9/5,25,7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。,2020/9/5,26,把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下

6、标 ， 链域nextarc存放指向同一链表中下一个表结点的指针 ，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。,2020/9/5,27,带权图的边结点中info保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。 在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。 建立邻

7、接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。,2020/9/5,28,有向图的邻接表和逆邻接表,在有向图的邻接表中，第 i 个链表中结点的个数是顶点Vi的出度。 在有向图的逆邻接表中，第 i 个链表中结点的个数是顶点Vi 的入度。,2020/9/5,29,图7-7 为图7-6 (a)的的邻接表和逆邻接表,图7-7 有向图的邻接表和逆邻接表,7-6 (a),2020/9/5,30,网络 (带权图) 的邻接表,2020/9/5,31,存储表示 typedef struct ArcNode int adjvex; struct ArcNode *nextar

8、c; int info; ArcNode; /边结点类型 typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; /邻接表 int vexnum,arcnum; ALGraph;,2020/9/5,32,int LocateVex(ALGraph G,char u) int i; for (i=0;iG.vexnum;i+) if(u= =G.verticesi.data) return i; if (i= =G.

9、vexnum) printf(Error u!n);exit(1); return 0; ,void CreateALGraph_adjlist(ALGraph ,2020/9/5,33,printf(Input Arcs(v1,v2 ,2020/9/5,34,7.2.3 十字链表 十字链表 (Orthogonal List)是有向图的另一种链式存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。 在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点

10、vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。 弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。 hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点,顶点结点,弧结点,2020/9/5,35,图7-8 十字链表,图7-8为图7-6 (a)有向图的十字链表。,采用十字链表表示有向图，很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。,2020/9/5,36,十字链表的

11、数据类型定义如下： #define MAXV typedef struct /弧结点 int tailvex,headvex; /弧尾和弧头顶点位置 struct ArcNode *hlink,*tlink; /弧头相同和弧尾相同的弧的链域 ArcNode; typedef struct /顶点结点 VertexType data; /顶点信息 ArcNode *firstin,*firstout; /分别指向该顶点的第一条入弧和出弧 VexNode;,2020/9/5,37,7.2.4 邻接多重表 邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包

12、含五个域，结构如下所示：,其中：mark 域 标志域，用于对该边进行标记； ivex 域 存放该边依附的一个顶点vi的位置信息； ilink 域 该链域指向依附于顶点vi的另一条边的边结点； jvex 域 存放该边依附的另一个顶点vj的位置信息； jlink 域 该链域指向依附于顶点vj的另一条边的边结点。 邻接多重表为每个顶点设置一个结点，其结构如下：,2020/9/5,38,图7-9 邻接多重表,图7-9为图7-5 (a)无向图的邻接多重表。,由邻接多重表可以看出，表示边（vi，vj）的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中，实现了用一个边结点表示一个边的

13、目的，克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多重表是无向图的一种很有效的存储结构。,2020/9/5,39,邻接多重表的结点数据类型定义如下： #define MAXV typedef struct /边结点类型 int mark; /访问标识 int ivex,jvex; /该边的两个顶点位置信息 struct Enode *ilink,*jlink; /分别指向依附这两个顶点的下一条边 Enode; typedef struct /顶点结点类型 VertexType data; /顶点数据域 ENode *firstedge; /指向第一条依附该顶点的边 Vnode;,20

14、20/9/5,40,7.3 图的遍历,和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。 (Traversing Graph)。 但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到，因此，图的遍历较树的遍历更复杂。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。,2020/9/5,41,7.3.1 深度优先搜索（DFS） 1 深度优先搜索思想 深度优先搜索遍历

15、类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作： （1）访问搜索到的未被访问的邻接点； （2）将此顶点的visited数组元素值置1； （3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。 深度优先搜索DFS可描述为： （1）访问v0顶点； （2）置 visitedv0=1； （3）搜索v0未被访问的邻接点w，若存在邻接点w，则DFS(w)。,2020/9/5,42,遍历过程： DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1

16、 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,2020/9/5,43,深度优先搜索的示例,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅

17、助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited i 为 1，防止它被多次访问。,2020/9/5,44,对上图，深度优先搜索遍历的顺序（之一）为： v1 v2v4 v8 v5v6v3v7。,图7-10 深度优先搜索,2020/9/5,45,深度优先搜索算法： int visitedMAX_VERTEX_NUM; void DFS(ALGraph G, int v) ArcNode *p; printf(%c,G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; whil

18、e (p) if (!visitedp-adjvex) DFS(G,p-adjvex); p=p-nextarc; /从第v个顶点出发DFS,2020/9/5,46,整个图的DFS遍历 void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v=0;vG.vexnum;+v) if (!visitedv) DFS(G,v); 对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。,2020/9/5,47,7.3.2 广度优先搜索（BFS） 1 广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍

19、历。 对于无向连通图，广度优先搜索是从图的某个顶点v0出发，在访问v0之后，依次搜索访问v0的各个未被访问过的邻接点w1，w2，。然后顺序搜索访问w1的各未被访问过的邻接点，w2的各未被访问过的邻接点，。即从v0开始，由近至远，按层次依次访问与v0有路径相通且路径长度分别为1，2，的顶点，直至连通图中所有顶点都被访问一次。 广度优先搜索的顺序不是唯一的，例如图7-10 (a) 连通图的广度优先搜索遍历顺序可为v1，v2，v3，v4，v5，v6，v7，v8 也可为v1，v3，v2，v7，v6，v5，v4，v8。,2020/9/5,48,1 广度优先搜索思想 设图G的初态是所有顶点均未访问，在G

20、中任选一顶点i作为初始点，则广度优先搜索的基本思想是： （1）从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visitedi=1； （2）依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到； （3）分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶 点的邻接点”先于“后被访问的顶点的邻接 点”被访问，直到图中所有已被访问过的顶 点的邻接点都被访问到。 依此类推，直到图中所有顶点都被访问完为止 。,2020/9/5,49,广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在

21、广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。,广度优先搜索过程 广度优先生成树,广度优先搜索的示例,2020/9/5,50,广度优先搜索过程可描述为： （1）f=0;r=0; /队列初始化，空队列；f-队首指针，r-队尾指针 （2）访问v0; （3）visitedv0=1; （4）insert(Queue,f,r,v0); /v0进入队尾 （5）while f0 do (i)delete(Queue,f,r,x); /队首元素出队并赋于x (ii)对所有x的邻接点w

22、 if visitedw=0 then （a）访问w; （b）visitedw=1; （c）insert(Queue,f,r,w); /w进队列,2020/9/5,51,以邻接表为存储结构，广度优先搜索遍历算法如下： #define MAXV void bfs(ALGraph *g,int v) ArcNode *p; int queueMAXV; /定义存放队列的数组 int visitedMAXV； /定义存放结点的访问标志的数组 int f=0,r=0,x,i; /队列头尾指针初始化，把队列置空 for(i=0,in;i+) /访问标志数组初始化 visitedi=0; printf(“

23、d”,v); /访问初始顶点v visitedv=1; /置已访问标记 r=(r+1)MAXV; queuer=v; /v进队 while(f!=r) /若队列不空时循环 f=(f+1)MAXV; x=queuetf; /出队并赋给x p=g-adjlistx.firstarc; /找与顶点x邻接的第一个顶点,2020/9/5,52,p=g-adjlistx.firstarc; /找与顶点x邻接的第一个顶点 while(p!=NULL) if (visitedp-adjvex=0) /若当前邻接点未被访问 visitedp-adjvex=l; /置该顶点已被访问的标志 printf(“d”，p

24、-adjvex); /访问该顶点 r=(r+1)MAXV; queuer=p-adjvex; /该顶点进队 p=p-nextarc; /找下一个邻接点 / w进队列,2020/9/5,53,算法分析：,如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。,2020/9/5,54,7.4 最小生成树,1. 生成树 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G 称做图G的生成树。一个图可以有多个生成

25、树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。,图7-12 生成树,2020/9/5,55,按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图. 由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树 在图论中，常常将树

26、定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。,2020/9/5,56,假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和

27、普里姆(Prim)算法。,7.4.1 克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。,2020/9/5,57,算法的基本思想： 在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。 假设G=（V，E）是一个具有n个顶点的带权无向连通图，T= (U，TE)是G的最小生成树，其中U

28、是T的顶点集，TE是T的边集，则构造最小生成树的过程如下： (1) 置U的初值等于V，TE的初值为空集； (2) 按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。,2020/9/5,58,应用克鲁斯卡尔算法构造最小生成树的过程:,2020/9/5,59,为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。 假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的

29、边数。克鲁斯卡尔算法如下： #define MAXE #define MAXV typedef struct int vex1; /边的起始顶点 int vex2; /边的终止顶点 int weight; /边的权值 Edge;,2020/9/5,60,Void kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for(i=0;in;i+) /初始化辅助数组 for(i=0;in;i+) /初始化辅助数组 vseti=i; k=1; /表示当前构造最小生成树的第k条边，初值为1 j=0; /E中边的下标，初值为

30、0 while(ke) /生成的边数小于e时继续循环 ml=Ej.vex1;m2=Ej.vex2;/取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2; /分别得到两个顶点所属的集合编号 if(sn1!=sn2) /两顶点分属于不同的集合，该边是最小生成树的一条边,2020/9/5,61, printf(“(m1，m2)：dn”,Ej.weight); k+; /生成边数增l for(i=0;in;i+) /两个集合统一编号 if (vseti= /集合编号为sn2的改为sn1 vseti=sn1; j+; /扫描下一条边 ,如果给定带权无向连通图G有e条边，且边已经按权值递增的

31、次序存放在数组E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O (e)。克鲁斯卡尔算法的时间复杂度与边数e有关，该算法适合于求边数较少的带权无向连通图的最小生成树。,2020/9/5,62,7.4.2 普里姆(Prim)算法 普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，

32、把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,2020/9/5,63,假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下： （1）初始状态，TE为空，U=v0，v0V； （2）在所有uU，vV-U的边(u，v) E中找一条代价最小的边(u，v)并入TE，同时将v并入U； 重复执行步骤（2）n-1次，直到U=V为止。 在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放

33、顶点的序号和边的权值。 对于每一个顶点vV-U，closestv为U中距离v最近的一个邻接点，即边 (v，closestv) 是在所有与顶点v相邻、且其另一顶点jU的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv=costvclosestv，,2020/9/5,64,采用邻接表作为存储结构： 设置一个辅助数组closedge： lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值； adjvex域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。,设置一个辅助数组closedge： lowcost域：存放在V-U中各个顶点到集

34、合U中的当前最小权值； adjvex域： 记录该边所依附的在U中的顶点,2020/9/5,65,若选择从顶点0出发，即u0 = 0，则辅助数组的两个域的初始状态为： 然后反复做以下工作： 在 closedge i中选择 adjvex 0 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; void MiniSpanTree_PRIM(MGraph G,VertexType u) int k,j,i,minCost; k=LocateVex(G,u); for (j=0;jG.vexnum;+j) if (j!=k)

35、 closedgej.adjvex=u; closedgej.lowcost=G.arcskj; ,2020/9/5,68,closedgek.lowcost=0; for (i=1;iG.vexnum;+i) k=minimum(closedge); minCost=INFINITY; for (j=0;jG.vexnum;+j) if (closedgej.lowcost minCost ,2020/9/5,69,普里姆算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此普里姆算法的时间复杂度为O(n2)。普里姆算法的时间复杂度与边数e无关，该算法更适合于求

36、边数较多的带权无向连通图的最小生成树。,2020/9/5,70,7.5 最短路径,交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通? 在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。 另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。 路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。,2020/9/5

37、,71,最短路径： 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 对于带权的图，通常把一条路径上所经过边或弧上的权值之和定义为该路径的路径长度。从一个顶点到另一个顶点可能存在着多条路径，把路径长度最短的那条路径称为最短路径，其路径长度称为最短路径长度。无权图实际上是有权图的一种特例，我们可以把无权图的每条边或弧的权值看成是l，每条路径上所经过的边或弧数即为路径长度。本章讨论两种最常见的最短路径问题。,2020/9/5,72,问题解法 边上权值非负情形的单源最短路径问题 Dijkstra算法 所有顶点之间的最短

38、路径 Floyd算法 边上权值非负情形的单源最短路径问题 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,2020/9/5,73,7.5.1 求一顶点（单源点）到其余顶点的最短路径 单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。 迪杰斯特拉(Dijkstra)在做

39、了大量观察后,首先提出了按路径长度递增产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。 算法的基本思想是:设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。,2020/9/5,74,具体做法是:设源点为Vl,则S中只包含顶点Vl，令W=V-S，则W中包含除Vl外图中所有顶点，Vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧则Vj顶点的距离为此弧权值，否则为(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的

40、顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。,2020/9/5,75,图7-16 带权有向图,设G=(V，E)是一个带权有向图，指定的顶点v0为源点，求v0到图的其余各顶点的最短路径。如图7-16所示，若以顶点0为v0，它到其余各顶点的最短路径分别为： 顶点0 顶点1：无路径 顶点0 顶点2：最短路径为（0，2），最短路径长度为10 顶点0 顶点4：最短路径为（0，4），最短路径长度为30 顶点0

41、顶点3：最短路径为（0，4，3），最短路径长度为50 顶点0 顶点5：最短路径为（0，4，3，5），最短路径长度为60,2020/9/5,76,从以上图7-16的最短路径可以看出： (1) 最短路径并不一定是经过边或弧数最少的路径。如从顶点0到顶点5的路径（0，5）长度为100，路径（0，4，5）长度为90，路径（0，2，3，5）长度为70，路径（0，4，3，5）长度为60，其中最短路径为（0，4，3，5），最短路径长度为60。 (2) 这些最短路径中，长度最短的路径上只有一条弧，且它的权值在从源点出发的所有弧的权值中最小。如从源点0出发有3条弧，其中以弧的权值为最小。此时（0，2）不仅是顶点

42、 0到顶点2 的一条最短路径，而且它在从源点0到其它各顶点的最短路径中长度最短。 (3)按照路径长度递增的次序产生最短路径。求得第二条最短路径（0，4）；之后求得第三条最短路径（0，4，3），它经过已求出的第二条最短路径（0，4）到达顶点3；求得的第四条最短路径（0，4，3，5），经过已求出的第三条最短路径（0，4，3）到达顶点5。,2020/9/5,77,迪杰斯特拉算法的求解过程：,2020/9/5,78,图7-17 迪杰斯特拉算法求最短路径过程及结果,2020/9/5,79,Dijkstra算法可描述如下：,初始化： S v0 ; Dj arcs0j, j = 1, 2, , n-1; /

43、 n为图中顶点个数 求出最短路径的长度： Dk min Di , i V- S ; S S U k ; 修改： Di min Di, Dk + arcski , 对于每一个 i V- S ; 判断： 若S = V, 则算法结束，否则转。,2020/9/5,80,狄杰斯特拉算法dijkstra，其中n为图G的顶点数，v0为源点。 #define INF 32767 /INF表示 #define MAXV void dijkstra(int costMAXV，int n，int vO) int distMAXV，pathMAXV； int sMAXV； int mindis； int i，j，k；

44、 for(i=0;in;i+) disti=costvOi; /距离初始化 si=0; /s初始化 if (costvOiINF) /路径初始化 pathi=vO; else pathi=-1; svO=1; /源点v0放入S中 for(i=1;in;i+) /重复，直到求出v0到其余所有顶点的最短路径,2020/9/5,81,for(i=1;in;i+) /重复，直到求出v0到其余所有顶点的最短路径 mindis=INF; k=vO; for(j=1;jn;j+) /从V-S中选取具有最小距离的顶点v k if(sj=0 /输出最短路径,2020/9/5,82,通过pathi向前回推直到v0

45、为止，可以找出从v 0到顶点v i的最短路径。输出最短路径的算法dispath如下： void dispath(int dist,int path,int s,int n,int vO) int i,k; for(i=0;in;i+) if(si=1) /S中顶点 k=i; printf(“d 到 d的最短路径为:”, v0,i); while(k!=v0) printf(“d-”,k); k=pathk; printf(“d 路径长度为:dn”,v0,disti); else printf(“d-d不存在路径n”,i,v0); ,2020/9/5,83,在狄克斯特拉算法中，求一条最短路径所花

46、费的时间：从V-S中选取具有最小距离的顶点v k花费时间O(n)；修改V-S中顶点的距离花费时间O(n)；输出最短路径花费时间O(n)。因此求出n-1条最短路径的时间复杂度为O(n2)。,2020/9/5,84,7.5.2 每对顶点之间的最短路径 顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(VW),找出V到W的最短距离和W到V的最短距离。 解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。 弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的算法，虽然其时

47、间复杂度也是 O(n3)，但其算法的形式更简单，易于理解和编程。,2020/9/5,85,弗洛伊德算法仍然使用前面定义的图的邻接矩阵arcsn+1n+1来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=O时, A (0)ij=arcsij 以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：,2020

48、/9/5,86,第一步，让所有边上加入中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的值，完成后得到A(1)， 第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,A(n)ij表示顶点i到顶点j的最短距离。,因此，弗洛伊德算法可以描述为: A(0)ij=arcsij; /arcs为图的邻接矩阵 A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj 其中 k=1,2,n,2020/9/5,87,Floyd算法的基本思想： 定义一个n阶方阵序列： D(-1)

49、, D(0), , D(n-1). 其中 D(-1) ij = G.arcsij； D(k) ij = min D(k-1)ij， D(k-1)ik + D(k-1)kj , k = 0,1, n-1 D(0) ij是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, D(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径长度, D(n-1)ij是从顶点vi 到vj 的最短路径长度。,2020/9/5,88,Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。 本章给出的求解最短路径的算法不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图

50、可以看作是有往返二重边的有向图，只要在顶点vi 与vj 之间存在无向边(vi , vj )，就可以看成是在这两个顶点之间存在权值相同的两条有向边和。,2020/9/5,89,弗洛伊德算法floyd如下： #define INF 32767 /INF表示 #define MAXV void floyd(int costMAXV，int n) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for(i=0;i(Aik+Akj),2020/9/5,90,if(Aij(Aik+Akj) Aij=Aik+Akj; pathij=k; dispath(A,path,n); /

51、输出最短路径 以下是输出最短路径的算法dispath，其中ppath（）函数在path中递归输出从顶点vi到vj的最短路径。 void ppath(int pathMAXV,int i,int j) int k; k=pathij; if(k=-1) /pathij=-1时,顶点vi和vj之间无中间顶点 return; ppath(path,i,k); printf(“d,”,k); ppath(path,k,j); ,2020/9/5,91,void dispath(int AMAXV,int pathMAXV,int n) int i,j; for(i=0;in;i+) for(j=0;j

52、n;j+) if(Aij=INF) if(i!=j) printf(“从顶点d到顶点d没有路径n”,i,j); else printf(“从顶点d到顶点d路径为:”,i,j);； printf(“d ,”,i); ppath(path,i,j); printf(“d”,j); printf(“路径长度为:dn”,Aij); 弗洛伊德算法包含一个三重循环，其时间复杂度为O(n3)。,2020/9/5,92,1.拓扑排序 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。 例如，计算机专业

53、学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-21给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。,7.6 拓扑排序,2020/9/5,93,图7-21 课程名称及相应的课程安排次序,图7-22 课程安排的AOV网,在图7-22中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(Actire On Vertices)简称为AOV

54、网。,2020/9/5,94,AOV网Activity On Vertex Network 用顶点表示活动，用弧表示活动间 的优先关系的有向图，称为顶点表 示活动的网。 AOV 网中不能有回路 拓扑排序： 假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，vn称做一个拓扑序列(Topological Order)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。,2020/9/5,95,由于AOV网

55、中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。 对图7-22进行拓扑排序，可得一个拓扑序列： C1，C3，C2，C4，C7，C6，C5 也可得到另一个拓扑序列： C2，C7，C1，C3，C4，C5，C6 还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。 在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。 判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。,2020/9/5,96,进行拓扑排序的

56、方法： 输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 、 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,2020/9/5,97,拓扑排序的过程,2020/9/5,98,最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也

57、排出了先后次序关系。,2020/9/5,99,在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下： typedef struct /表头结点 Vertex data; /顶点信息 int count; /存放顶点入度 ArcNode *firstarc; /指向第一条弧 Vnode;,在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下：,2020/9/5,100,void topsort(VNode adj,int n) int i,j; int stackMAXV,top=0; /栈stack的指针为top ArcNode *p; for(i=0;i0) /栈不为空 i=stacktop; top-; /顶点vi出栈 printf(“d”,i); /输出vi p=adji.firstarc; /指向以vi为弧尾的第一条弧 while(p!=