《第12讲加权图课件.ppt》由会员分享，可在线阅读，更多相关《第12讲加权图课件.ppt（43页珍藏版）》请在三一办公上搜索。
1、第12讲 加权图及其应用,1,内容提要,使用连接矩阵和优先队列来表示加权边设计加权图设计实现最小生成树Prim算法设计实现最小生成树Kruskal算法设计实现单源最短路径Dijkstra算法设计实现单源最短路径Floyd算法,2,加权图的表示,3,加权边的表示：边数组加权邻接矩阵优先邻接链表,加权边的表示：边数组,4,int 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;,带权图及其邻接矩阵,加权邻接矩阵,6,优先邻接链表,7,8,Graph,TestWeigh
2、tedGraph,AbstractGraph,WeightedGraph,TestWeightedGraph,最小生成树,最小生成树的基本概念 一个有n个结点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个结点，并且有保持图连通的最少的边。如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小代价生成树，简称最小生成树。,无向图和它的不同的生成树,最小生成树,11,从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树,必须满足以下三条：（1）构造的最小生成树必须包括n个结点；（2）构造的最小生成树中有且只有n-1条边；
3、（3）构造的最小生成树中不存在回路。构造最小生成树的方法有许多种，典型的构造方法有两种，一种称作普里姆（Prim）算法，另一种称作克鲁斯卡尔（Kruskal）算法。,普里姆算法假设G=(V,E)为一个带权图，其中V为带权图中结点的集合，E为带权图中边的权值集合。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树的权值的集合。普里姆算法思想是：令集合U的初值为U=u0（即假设构造最小生成树时从结点u0开始），集合T的初值为T=。从所有结点uU和结点vV-U的带权边中选出具有最小权值的边(u,v)，将结点v加入集合U中，将边(u,v)加入集合T中
4、。如此不断重复，当U=V时则最小生成树构造完毕。此时集合U中存放着最小生成树结点的集合，集合T中存放着最小生成树边的权值集合。,Prim Algorithm,minimumSpanningTree()Let V denote the set of vertices in the graph;Let T be a set 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 w
5、eight on the edge(u,v),as shown in Figure 28.4;add v to T;,14,Prim Algorithm,15,1,普里姆算法构造最小生成树的过程,Prim算法实现,18,时间复杂度,19,对于每个顶点，程序都会为它创建一个邻接边的优先队列。将一条边插入优先队列（或者从优先队列删除一条边）的时间复杂度为 O(log|V|)，|V|代表顶点的个数。所以，程序的总体时间复杂度为 O(|E|log|V|),|E|代表边的条数。,Test MST,20,TestMinimumSpanningTree,TestMinimumSpanningTree,普里姆
6、算法实现采用邻接矩阵方法,克鲁斯卡尔算法 克鲁斯卡尔算法是：设无向连通带权图G=(V,E)，其中V为结点的集合，E为边的集合。设带权图G的最小生成树T由结点集合和边的集合构成，其初值为T=(V,)，即初始时最小生成树T只由带权图G中的结点集合组成，各结点之间没有一条边。这样，最小生成树T中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中的边集合E中的各条边。若被考察的边的两个结点属于T的两个不同的连通分量，则将此边加入到最小生成树T，同时把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，
7、T中的该连通分量即为带权图G的一棵最小生成树。,克鲁斯卡尔算法构造最小生成树的过程,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,最小生成树两种算法的比较,最短路径,在一个图中，若从一个结点到另一个结点存在着路径，定义路径长度为一条路径上所经过的边的数目。图中从一个结点到另一个结点可能存在着多条路径，我们把路径长度最短的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离.,在一个带权图中，若从一个结点到另一个结点存在着一条路径，则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中从一个结点到另一个结点可能存在着多条路
8、径，我们把带权路径长度值最小的那条路径也叫做最短路径，其带权路径长度也叫做最短路径长度或最短距离。,从一个点到其余各结点的最点路径 1 狄克斯特拉算法思想 狄克斯特拉算法是：设置两个结点的集合S和T，集合S中存放已找到最短路径的结点，集合T中存放当前还未找到最短路径的结点。初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点v0路径长度最短的结点u加入到集合S中，集合S中每加入一个新的结点u都要修改源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各结点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过结点u到达该结点的路径长度中的较小者。此过程不断重复，直到集
9、合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 smallest costsu+w(u,v)value among all u in T;add v to T;
10、,28,Dijkstra Algorithm,29,30,E,B,F,C,D,A,8,18,2,30,15,10,7,4,5,Dijkstra算法实现,32,TestShortestPath,TestShortestPath,Dijkstra算法实现,33,Dijkstra算法实现,34,Dijkstra算法实现,35,Dijkstra算法实现,36,Dijkstra算法实现,37,Dijkstra算法实现,38,每对结点之间的最短路径 弗洛伊德算法是：设矩阵cost用来存放带权有向图G的权值，即矩阵元素costij中存放着下标为i的结点到下标为j的结点之间的权值，可以通过递推构造一个矩阵序列
11、A0,A1,A2,AN来求每对结点之间的最短路径。初始时有，A0ij=costij。当已经求出Ak,要递推求解Ak+1时，可分两种情况来考虑：一种情况是该路径不经过下标为k+1的结点，此时该路径长度与从结点vi到结点vj的路径上所经过的结点下标不大于k的最短路径长度相同；另一种情况是该路径经过下标为k+1的结点，此时该路径可分为两段，一段是从结点vi到结点vk+1的最短路径，另一段是从结点vk+1到结点vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况中的路径长度较小者，就是要求的从结点vi到结点vj的路径上所经过的结点下标不大于k+1的最短路径长度。,弗洛伊德算法的算法
12、思想可用如下递推公式描述：A0ij=costij Ak+1ij=minAkij,Akik+1+Akk+1j（0kn-1）也就是说，初始时，A0ij=costij，然后进行递推，每递推一次，从结点vi到结点vj的最短路径上就多考虑了一个经过的中间结点，这样，经过n次递推后得到的Anij就是考虑了经过图中所有结点情况下的从结点vi到结点vj的最短路径长度。,例如：,有向图的最短路径及其路径长度,带权有向图(a)有向图(b)邻接矩阵,The Weighted Nine Tail Problem,The nine tail problem is to find the minimum number o
13、f the moves that lead to all coins 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,WeightedNineTailModel,学习要点,1熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。3.应用图的遍历算法求解各种简单路径问题。4.理解教科书中讨论的各种图的应用算法。,
