第12讲-加权图课件.ppt

1、第12讲 加权图及其应用1内容提要使用连接矩阵和优先队列来表示加权边设计加权图设计实现最小生成树Prim算法设计实现最小生成树Kruskal算法设计实现单源最短路径Dijkstra算法设计实现单源最短路径Floyd算法2加权图的表示3加权边的表示：边数组加权邻接矩阵优先邻接链表加权边的表示：边数组4int edges=0,1,2,0,3,8,1,0,2,1,2,7,1,3,3,2,1,7,2,3,4,2,4,5,3,0,8,3,1,3,3,2,4,3,4,6,4,2,5,4,3,6;4 2 7 8 3 6 5 0 1 2 3 4 带权图及其邻接矩阵带权图及其邻接矩阵 加权邻接矩阵 4 2 7

2、8 3 6 5 0 1 2 3 4 6 0 1 2 3 4 0 1 2 3 4 2 3 4 null 2 null 8 null 2 null 7 3 null null 7 null 4 5 8 3 4 null 6 null null 5 6 null Integer adjacencyMatrix=null,2,null,8,null,2,null,7,3,null,null,7,null,4,5,8,3,4,null,6,null,null,5,6,null;优先邻接链表 4 2 7 8 3 6 5 0 1 2 3 4 7 queues0 queues1 queues2 queues3

3、 queues4 WeightedEdge(0,1,2)WeightedEdge(0,3,8)WeightedEdge(1,0,2)WeightedEdge(1,3,3)WeightedEdge(1,2,7)WeightedEdge(2,3,4)WeightedEdge(2,4,5)WeightedEdge(2,1,7)WeightedEdge(3,1,3)WeightedEdge(3,2,4)WeightedEdge(3,0,8)WeightedEdge(3,4,6)WeightedEdge(4,2,5)WeightedEdge(4,3,6)8GraphTestWeightedGraphAb

4、stractGraphWeightedGraphTestWeightedGraph interface Graph AbstractGraph WeightedGraph-queues:java.util.PriorityQueue+WeightedGraph(edges:int,vertices:V)+WeightedGraph(edges:List,vertices:List)+WeightedGraph(edges:int,numberOfVertices:int)+WeightedGraph(edges:List,numberOfVertices:int)+printWeightedE

5、dges():void+getMinimumSpanningTree():MST+getMinimumSpanningTree(index:int):MST+getShortestPath(index:int):ShortestPathTree+getWeightedEdges():java.util.PriorityQueue queuesi is a priority queue that contains all the edges adjacent to vertex i.Constructs a weighted graph with the specified edges and

6、the number of vertices in arrays.Constructs a weighted graph with the specified edges and the number of vertices.Constructs a weighted graph with the specified edges in an array and the number of vertices.Constructs a weighted graph with the specified edges in a list and the number of vertices.Displ

7、ays all edges and weights.Returns a minimum spanning tree starting from vertex 0.Returns a minimum spanning tree starting from vertex v.Returns all single-source shortest paths.Returns all weighted edges for each vertex in a priority queue.最小生成树最小生成树的基本概念最小生成树的基本概念 一个有一个有n个结点的连通图的个结点的连通图的生成树生成树是原图的极

8、小连通是原图的极小连通子图，它包含原图中的所有子图，它包含原图中的所有n个结点，并且有保持图连个结点，并且有保持图连通的最少的边。通的最少的边。如果无向连通图是一个带权图，那么它的所有生成树如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生中必有一棵边的权值总和最小的生成树，我们称这棵生成树为成树为最小代价生成树最小代价生成树，简称，简称最小生成树最小生成树。无向图和它的不同的生成树无向图和它的不同的生成树 最小生成树11 5 6 10 5 8 7 7 12 7 10 8 8 5 5 6 7 7 8 5 5 6 7 7 8 从最小生成树的定义可知，构

9、造有从最小生成树的定义可知，构造有n个结点的无个结点的无向连通带权图的最小生成树向连通带权图的最小生成树,必须满足以下三条：必须满足以下三条：（1）构造的最小生成树必须包括）构造的最小生成树必须包括n个结点；个结点；（2）构造的最小生成树中有且只有）构造的最小生成树中有且只有n-1条边；条边；（3）构造的最小生成树中不存在回路。）构造的最小生成树中不存在回路。构造最小生成树的方法有许多种，典型的构造构造最小生成树的方法有许多种，典型的构造方法有两种，一种称作方法有两种，一种称作普里姆普里姆（Prim）算法，另）算法，另一种称作一种称作克鲁斯卡尔克鲁斯卡尔（Kruskal）算法。）算法。普里姆算

10、法普里姆算法假设假设G=(V,E)为一个带权图，其中为一个带权图，其中V为带权图中结点的集为带权图中结点的集合，合，E为带权图中边的权值集合。设置两个新的集合为带权图中边的权值集合。设置两个新的集合U和和T，其中其中U用于存放带权图用于存放带权图G的最小生成树的结点的集合，的最小生成树的结点的集合，T用于存放带权图用于存放带权图G的最小生成树的权值的集合。的最小生成树的权值的集合。普里姆算法思想普里姆算法思想是：令集合是：令集合U的初值为的初值为U=u0（即假设（即假设构造最小生成树时从结点构造最小生成树时从结点u0开始），集合开始），集合T的初值为的初值为T=。从所有结点从所有结点uU和结点

11、和结点vV-U的带权边中选出具有最小的带权边中选出具有最小权值的边权值的边(u,v)，将结点，将结点v加入集合加入集合U中，将边中，将边(u,v)加入加入集合集合T中。如此不断重复，当中。如此不断重复，当U=V时则最小生成树构造完时则最小生成树构造完毕。此时集合毕。此时集合U中存放着最小生成树结点的集合，集合中存放着最小生成树结点的集合，集合T中存放着最小生成树边的权值集合。中存放着最小生成树边的权值集合。Prim Algorithm minimumSpanningTree()Let V denote the set of vertices in the graph;Let T be a se

12、t for the vertices in the spanning tree;Initially,add the starting vertex to T;while(size of T n)find u in T and v in V T with the smallest weight on the edge(u,v),as shown in Figure 28.4;add v to T;14Prim Algorithm 15 u v T V-T Vertices already in the spanning tree Vertices not currently in the spa

13、nning tree 例1654326513566425131163141643142116432142516543214253普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程Prim算法实现18 AbstractGraph.Tree WeightedGraph.MST-totalWeight:int+MST(root:int,parent:int,totalWeight:int)+getTotalWeight():int Total weight of the tree.Constructs a MST with the specified root,parent array,a

14、nd total weight for the tree.Returns the totalWeight of the tree.时间复杂度19对于每个顶点，程序都会为它创建一个邻接边的优先队列。将一条边插入优先队列（或者从优先队列删除一条边）的时间复杂度为 O(log|V|)，|V|代表顶点的个数。所以，程序的总体时间复杂度为 O(|E|log|V|),|E|代表边的条数。Test MST20TestMinimumSpanningTreeTestMinimumSpanningTree Seattle San Francisco Los Angeles Denver Chicago Kansa

15、s City Houston Boston New York Atlanta Miami 661 888 1187 810 Dallas 1331 2097 1003 807 381 1015 1267 1663 1435 239 496 781 864 1260 983 787 214 533 599 1 2 3 4 6 7 8 9 10 11 5 普里姆算法实现采用邻接矩阵方法普里姆算法实现采用邻接矩阵方法克鲁斯卡尔算法克鲁斯卡尔算法 克鲁斯卡尔克鲁斯卡尔算法是：设无向连通带权图算法是：设无向连通带权图G=(V,E)，其中，其中V为为结点的集合，结点的集合，E为边的集合。设带权图为边的集合

16、。设带权图G的最小生成树的最小生成树T由结点由结点集合和边的集合构成，其初值为集合和边的集合构成，其初值为T=(V,)，即初始时最小生成，即初始时最小生成树树T只由带权图只由带权图G中的结点集合组成，各结点之间没有一条边。中的结点集合组成，各结点之间没有一条边。这样，最小生成树这样，最小生成树T中的各个结点各自构成一个连通分量。然中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图后，按照边的权值递增的顺序考察带权图G中的边集合中的边集合E中的中的各条边。若被考察的边的两个结点属于各条边。若被考察的边的两个结点属于T的两个不同的连通分的两个不同的连通分量，则将此边加入到最小

17、生成树量，则将此边加入到最小生成树T，同时把两个连通分量连接，同时把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于为一个连通分量；若被考察的边的两个结点属于T的同一个连的同一个连通分量，则将此边舍去。如此下去，当通分量，则将此边舍去。如此下去，当T中的连通分量个数为中的连通分量个数为1时，时，T中的该连通分量即为带权图中的该连通分量即为带权图G的一棵最小生成树。的一棵最小生成树。克鲁斯卡尔算法构造最小生成树的过程克鲁斯卡尔算法构造最小生成树的过程 普里姆算法 克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围最小生成树两种算法的比较最短路径在一个图中，若从

18、一个结点到另一个结点存在着在一个图中，若从一个结点到另一个结点存在着路径，定义路径，定义路径长度路径长度为一条路径上所经过的边的为一条路径上所经过的边的数目。图中从一个结点到另一个结点可能存在着数目。图中从一个结点到另一个结点可能存在着多条路径，我们把路径长度最短的那条路径叫做多条路径，我们把路径长度最短的那条路径叫做最短路径最短路径，其路径长度叫做，其路径长度叫做最短最短路径路径长度或长度或最短最短距离距离.在一个带权图中，若从一个结点到另一个在一个带权图中，若从一个结点到另一个结点存在着一条路径，则称该路径上所经过边结点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的的权值之和为

19、该路径上的带权路径长度带权路径长度。带权。带权图中从一个结点到另一个结点可能存在着多条图中从一个结点到另一个结点可能存在着多条路径，我们把带权路径长度值最小的那条路径路径，我们把带权路径长度值最小的那条路径也叫做也叫做最短路径最短路径，其带权路径长度也叫做，其带权路径长度也叫做最短最短路径长度路径长度或或最短距离最短距离。从一个点到其余各结点的最点路径从一个点到其余各结点的最点路径 1 狄克斯特拉算法思想狄克斯特拉算法思想 狄克斯特拉算法狄克斯特拉算法是：设置两个结点的集合是：设置两个结点的集合S和和T，集合集合S中存放已找到最短路径的结点，集合中存放已找到最短路径的结点，集合T中存放当中存放

20、当前还未找到最短路径的结点。初始状态时，集合前还未找到最短路径的结点。初始状态时，集合S中只中只包含源点，设为包含源点，设为v0，然后从集合，然后从集合T中选择到源点中选择到源点v0路径路径长度最短的结点长度最短的结点u加入到集合加入到集合S中，集合中，集合S中每加入一个中每加入一个新的结点新的结点u都要修改源点都要修改源点v0到集合到集合T中剩余结点的当前中剩余结点的当前最短路径长度值，集合最短路径长度值，集合T中各结点的新的当前最短路径中各结点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过结长度值，为原来的当前最短路径长度值与从源点过结点点u到达该结点的路径长度中的较小者。

21、此过程不断重到达该结点的路径长度中的较小者。此过程不断重复，直到集合复，直到集合T中的结点全部加入到集合中的结点全部加入到集合S 中为止。中为止。Dijkstra算法shortestPath(s)Let V denote the set of vertices in the graph;Let T be a set that contains the vertices whose path to s have been found;Initially T contains source vertex s;while(size of T n)find v in V T with the smal

22、lest costsu+w(u,v)value among all u in T;add v to T;28Dijkstra Algorithm 29 u v T V-T s T contains vertices whose shortest path to s have been found V-T contains vertices whose shortest path to s have not been found 30EBFCDA8182301510745Dijkstra算法实现32TestShortestPathTestShortestPath AbstractGraph.Tr

23、ee WeightedGraph.ShortestPathTree-costs:int+ShortestPathTree(source:int,parent:int,searchOrder:List,costs:int)+getCost(v:int):int+printAllPaths():void costsv stores the cost for the path from the source to v.Constructs a shortest path tree with the specified source,parent array,and costs array.Retur

24、ns the cost for the path from the source to vertex v.Displays all paths from the soruce.Dijkstra算法实现33 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 0 0 1 2 3 4 5 6 parent -1 Dijkstra算法实现34 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 0 5 0 1 2 3 4 5 6 parent -1 1 Dijkstra

25、算法实现35 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 6 0 5 0 1 2 3 4 5 6 parent 2 -1 1 Dijkstra算法实现36 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 6 0 5 8 0 1 2 3 4 5 6 parent 2 -1 1 0 Dijkstra算法实现37 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 6 0 5 10 8 0 1

26、 2 3 4 5 6 parent 2 -1 1 1 0 Dijkstra算法实现38 5 5 10 1 8 9 2 4 7 8 8 5 1 2 3 4 5 6 0 0 1 2 3 4 5 6 costs 6 0 5 10 15 10 8 0 1 2 3 4 5 6 parent 2 -1 1 1 5 0 0 每每对结点之间的最短路径对结点之间的最短路径 弗洛伊德算法是：设矩阵弗洛伊德算法是：设矩阵cost用来存放带权有向图用来存放带权有向图G的权的权值，即矩阵元素值，即矩阵元素costij中存放着下标为中存放着下标为i的结点到下标为的结点到下标为j的结点之间的权值，可以通过递推构造一个矩阵序

27、列的结点之间的权值，可以通过递推构造一个矩阵序列A0,A1,A2,AN来求每对结点之间的最短路径。初始时有，来求每对结点之间的最短路径。初始时有，A0ij=costij。当已经求出。当已经求出Ak,要递推求解要递推求解Ak+1时，可分两种情时，可分两种情况来考虑：一种情况是该路径不经过下标为况来考虑：一种情况是该路径不经过下标为k+1的结点，此的结点，此时该路径长度与从结点时该路径长度与从结点vi到结点到结点vj的路径上所经过的结点下的路径上所经过的结点下标不大于标不大于k的最短路径长度相同；另一种情况是该路径经过的最短路径长度相同；另一种情况是该路径经过下标为下标为k+1的结点，此时该路径可

28、分为两段，一段是从结点的结点，此时该路径可分为两段，一段是从结点vi到结点到结点vk+1的最短路径，另一段是从结点的最短路径，另一段是从结点vk+1到结点到结点vj的最的最短路径，此时的最短路径长度等于这两段最短路径长度之和。短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者，就是要求的从结点这两种情况中的路径长度较小者，就是要求的从结点vi到结到结点点vj的路径上所经过的结点下标不大于的路径上所经过的结点下标不大于k+1的最短路径长度。的最短路径长度。弗洛伊德算法的算法思想可用如下递推公式描述：弗洛伊德算法的算法思想可用如下递推公式描述：A0ij=costij

29、 Ak+1ij=minAkij,Akik+1+Akk+1j（0kn-1）也就是说，初始时，也就是说，初始时，A0ij=costij，然后进行，然后进行递推，每递推一次，从结点递推，每递推一次，从结点vi到结点到结点vj的最短路径上的最短路径上就多考虑了一个经过的中间结点，这样，经过就多考虑了一个经过的中间结点，这样，经过n次递次递推后得到的推后得到的Anij就是考虑了经过图中所有结点情就是考虑了经过图中所有结点情况下的从结点况下的从结点vi到结点到结点vj的最短路径长度。的最短路径长度。例如：123ab643211(a)0 4 116 0 2 3 8 0(b)10404111104046633

30、738003737002606022605022A121233121233A(0)A(3)A(2)A(1)1ABABACABABABCABC3CACABCABCCACABCACAB2BABABCBABCABCBCPATH121233121233PATH(0)PATH(3)PATH(2)PATH(1)AC有向图的最短路径及其路径长度带权有向图(a)有向图 (b)邻接矩阵 The Weighted Nine Tail Problem The nine tail problem is to find the minimum number of the moves that lead to all c

31、oins face down.Each move flips a head coin and its neighbors.The weighted nine tail problem assigns the number of the flips as a weight on each move.For example,you can move from the coins in Figure 28(a)to Figure 28(b)by flipping the three coins.So the weight for this move is 3.42 H T T T H H H H H T H T T T H H H H WeightedNineTailModel学习要点 1熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。3.应用图的遍历算法求解各种简单路径问题。4.理解教科书中讨论的各种图的应用算法。