图基本算法.ppt
《图基本算法.ppt》由会员分享,可在线阅读,更多相关《图基本算法.ppt(55页珍藏版)》请在三一文库上搜索。
1、图的基本算法,目录,1.图的基本概念 2.最小生成树算法 3.最短路问题 4.拓扑排序 5.浅析SPFA的优化 栈 6.时间允许的情况下,讲tarjan算法,图的基本概念,图:二元组 称为图(graph)。 V为结点(node)点(vertex)集。 E为图中结点之间的边的集合。 简单图 环:端点重合为一点的边。 重边:两条边连接同一对顶点。 简单图:没有环和重边的图。 无向图和有向图 如果边都是双向的,则这个图叫做无向图。 如果边都是单向的,则这个图叫做有向图。,图的基本概念,子图: 连通性 无向图中,如果两个顶点之间存在一条路经,就称这两个顶点是连通的。 有向图中,如果两个顶点之间相互都存
2、在一条路,则称它们是强连通的。 如果一个图的任意两个顶点都是连通的,就称这个图是连通的。 顶点的度 无向图中,一个顶点相连的边数称为该顶点的度。 有向图中,从一个顶点出发的边数称为该顶点得出度;到达该顶点的边数称为它的入度。 顶点的最大度数称为图的度数。 路和回路 一个连接两个顶点的,顶点与边交替的序列称为路。 除了起始与终止顶点,其他顶点都不相同,这样的路称为简单路径。起始与终止顶点相同的简单路径称为圈。,图的基本概念,完全图、稠密图和稀疏图 任何两个顶点之间都有边(弧)相连称为完全图 边(弧)很少的图称为稀疏图反之为稠密图,图的表示方法,邻接矩阵 邻接表,邻接矩阵,邻接表,邻接表表示法 常
3、用于稀疏图 需要记录的信息:结点首指针,边的权值和下一条边的指针,邻接表的实现,Struct Edge int vertex;/记录结点编号 int val;/边的权值 Edge* next;/记录链表的下一个元素 ; Edge *edge=new Edgen; for(int i=0;iuvw)/ (u,v)表示一条边,w表示权值 L=new Edge; L-vertex=v; L-val=w; L-next=edgeu; edgeu=L; /将(u,v)插入到以u起点的链表中 遍历与u相邻的节点: L=edgeu; while(L!=NULL) L=L-next; ,最小生成树问题,生成树
4、:由G的n-1条边构成的无环的子图,这些边的集合成为生成树。 最小生成树:所有生成树中权值最小的一个边集T为最小生成树,确定树T的问题成为最小生成树问题。 prim算法 kruskal算法,prim算法的基本思想,任取一个顶点加入生成树; 在那些一个端点在生成树里,另一个端点不在生成树里的边中,取权最小的边,将它和另一个端点加进生成树。 重复上一步骤,直到所有的顶点都进入了生成树为止。,int prim(int s)/s为初始加入的点 int i,j,sum=0; for(i=1;i=n;i+) closesti=10000000; for(i=1;i=n;i+) closesti=mapsi
5、; closests=0; int now; for(i=1;in;i+) int min=INT_MAX; for(j=1;j=n;j+) if(closestj ,时间复杂度为O(n2)。 (用堆维护最小优先级队列可以达到 O(vlogv+elogv),有兴趣的同学可以自己实现),kruskal算法的基本思想,对所有边从小到大排序; 依次试探将边和它的端点加入生成树,如果加入此边后不产生圈,则将边和它的端点加入生成树;否则,将它删去; 直到生成树中有了n-1条边,即告终止。 算法的时间复杂度O(eloge),kruskal算法实现的数据结构,一维数组,将所有边按从小到大的顺序存在数组里面
6、并查集 先把每一个对象看作是一个单元素集合,然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。 对于并查集来说,每个集合用一棵树表示。 它支持以下操作: Union (Root1, Root2) /合并两个集合; Findset(x) /搜索操作(搜索编号为x所在树的根)。 树的每一个结点有一个指向其父结点的指针。,并查集的处理过程,MAKE-SET(x) 1 px x 2 rankx 0 UNION(x, y) 1 LINK(FIND-SET(x), FIND-SET(y) LINK(x, y) 1 if rankx ranky 2 then py x 3 els
7、e px y 4 if rankx = ranky 5 then ranky ranky + 1 The FIND-SET procedure with path compression is quite simple. FIND-SET(x) 1 if x px 2 then px FIND-SET(px) 3 return px,MST-KRUSKAL(G,w) 1. A 2. for 每个结点vVG 3. do MAKE-SET(v) 4. 根据权w的非递减顺序对E的边进行排序 5. for 每条边(u,v)E,按权的非递减次序 6. do if FIND-SET(u)FIND-SET(
8、v) 7. then AA(u,v) 8. UNION(u,v) 9. return A 复杂度E*logE,例题 POJ3522,题目大意:给出一个由n个点m条边构成的无向图,找出一棵生成树,使得这个生成树上的最大边与最小边权值之差最小,思路:,用Kruskal! 由于kruskal算法是将边排序后从最小权值边开始不断地加入不形成环的边,我们可以由小到大枚举每次形成的生成树中的最小边来求的若干棵生成树。每次更新一下差值。求得最优解。,练习,Prim POJ 1258 POJ 2485 Kruskal POJ1861,最短路问题,单源最短路径 bellman-ford算法 spfa算法 dij
9、kstra算法 每对顶点的最短路径 floyd-washall算法,单源最短路径,已知图G=(V,E),我们希望找出从某给定源顶点sV到每个顶点vV的最短路径。 在单源最短路径问题的某些实例中,可能存在着权值为负的边,如果图不包含从s可达的负权回路,则对所有的vV,最短路径的权的定义依然正确。如果存在一条从s可达的负权回路,则最短路径的定义就不成立了。 易知,一条最短路径不能包含回路。,松弛技术,bellman-ford,spfa,dijkstra算法都使用了松弛技术,对每个顶点vV,都设置一个属性dv,用来描述从源点s到v的最短路径上权值的上界。 伪代码: 初始化: Init(G,s) fo
10、r each vertex vVG do dv=; ds=0; 松弛: Relax(u,v,w) if(dvdu+w(u,v) dv=du+w(u,v),Bellman-Ford算法,Bellman-Ford(G,w,s) Init(G,s) For i 1 to |VG|-1 Do For 每条边(u,v) EG Do Relax(u,v,w) For每条边(u,v) EG Do If dv du + w(u, v) Then Return FALSE Return TRUE /时间复杂度为O(V*E); Bellman-Ford算法能在一般的情况(存在负边权的情况)下解决单源最短路径问题,
11、对于给定的带权有向图G=(V,E),其源点为s,对该图运行Bellman-Ford算法后可以返回一个bool值表明图中是否存在着一个从源点可达的权为负的回路,若存在这样的回路的话,算法说明该问题无解,若不存在这样的回路,算法将产生最短路径及其权值。,对bellman-ford算法的说明: 如果没有负权回路,运行一次bellmanford算法,将得到源点到任意点的最短路: 由于源点到任意一点至多n-1条边,我们经过n-1次循环,每重循环对所有的边进行松弛,能保证每次至少得到一个di,其值为源点到i点的最短路,最终n-1次循环之后就能求得所有的di。 如果包含负权回路,那么n-1次循环之后还会存在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 算法
链接地址:https://www.31doc.com/p-3195340.html