算法学习 7.图论.pdf

图论七月算法邹博2015年4月28日2/图的表述与搜索 图的表示 邻接矩阵 n*n的矩阵，有边是1，无边是0 邻接表 为每个点建立一个链表(数组)存放与之连接的点 搜索 BFS(Breadth-First-Search)广(宽)度优先 DFS(Depth-First-Search)深度优先3/主要内容树的遍历和搜索(隐式)图的搜索(连通性)重点8皇后最短路径单源图(Dijkstra)任意两点(floyd)有负边(bellman-ford)最小生成树(MST)PrimKrusal拓扑排序(topsort)4/广度优先搜索：Breadth First Search，BFS 最简单、直接的图搜索算法 从起点开始层层扩展 第一层是离起点距离为1的 第二层是离起点距离为2的.本质就是按层(距离)扩展，无回退5/BFS分析 给定某起点a，将a放入缓冲区，开始搜索；过程：假定某时刻缓冲区内结点为abc，则访问结点a的邻接点a1a2ax，同时，缓冲区变成bc a1a2ax，为下一次访问做准备；辅助数据结构：队列 先进先出 从队尾入队，从队首出队 只有队首元素可见146253103020452555405015356/BFS分析的两个要点 结点判重如果在扩展中发现某结点在前期已经访问过，则本次不再访问该结点；显然，第一次访问到该结点时，是访问次数最少的：最少、最短；路径记录一个结点可能扩展出多个结点：多后继a a1a2ax，但是任意一个结点最多只可能有1个前驱(起始结点没有前驱)：单前驱用和结点数目等长的数组pre0N-1：prei=j：第i个结点的前一个结点是j注：再次用到“存索引，不存数据本身”的思路。146253103020452555405015357/BFS算法框架 辅助数据结构队列q；结点是第几次被访问到的d0N-1：简称步数；结点的前驱pre0N-1；算法描述：起点start入队q记录步数dstart=0；记录start的前驱prestart=-1；如果队列q非空，则队首结点x出队，尝试扩展x找到x的邻接点集合y|(x,y)E 对每个新扩展结点y判重，如果y是新结点，则入队q；同时，记录步数dy=dx+1；前驱prey=x；1462531030204525 55405015358/BFS算法思考 对BFS的改进双向BFS 从起点和终点分别走，直到相遇；将树形搜索结构变成纺锤形；为什么这样更“快”？经典BFS中，树形搜索结构若树的高度非常高时，叶子非常多(树的宽度大)把一棵高度为h的树，用两个近似为h/2的树代替。宽度相对较小。9/单词变换问题Word ladder 给定字典和一个起点单词、一个终点单词，每次只能变换一个字母，问从起点单词是否可以到达终点单词？最短多少步？如：start=hit end=cog dict=hot,dot,dog,lot,log hit-hot-dot-dog-cog10/单词变换问题使用临界表，建立单词间的联系单词为图的结点，若能够变换，则两个单词存在无向边；若单词A和B只有1个字母不同，则(A-B)存在边；建图：预处理：对字典中的所有单词建立map、hash或者trie结构，利于后续的查找对于某单词w，单词中的第i位记为，则将替换为+1,Z，查找新的串nw是否在字典中。如果在，将(w-nw)添加到邻接表项w和nw中(无向边)循环处理第二步若使用map，串在字典中的查找认为是O(logN)的，那么，整体时间复杂度为O(N*len*13*logN)，即O(N*logN)。若使用hash或者trie，整体复杂度为O(N)从起始单词开始，广度优先搜索，看能否到达终点单词。若可以到达，则这条路径上的变化是最快的。11/思考 有趣的是：虽然从起点单词开始到终点单词的路径内的单词，必须在词典内，但起点和终点本身是无要求的。是否需要事先计算图本身？体会路径记录问题。12/Code13/Code(split)14/周围区域问题 给定二维平面，格点处要么是X，要么是O。求出所有由X围成的区域。找到这样的(多个)区域后，将所有的O翻转成X即可。15/分析 反向思索最简单：哪些O是应该保留的？从上下左右四个边界往里走，凡是能碰到的O，都是跟边界接壤的，应该保留。思路：对于每一个边界上的O作为起点，做若干次广度优先搜索，对于碰到的O，标记为其他某字符Y；最后遍历一遍整个地图，把所有的Y恢复成O，把所有现有的O都改成X。16/Code17/Code(split)18/思考与拓展 如果目标区域是三维的呢？19/深度优先搜索DFS 理念：不断深入，“走到头”回退。(回溯思想)一般所谓“暴力枚举”搜索都是指DFS 回忆数组章节中“N-Sum问题”的解法 实现 一般使用堆栈，或者递归 用途：DFS的过程中，能够获得的信息“时间戳”、“颜色”、父子关系、高度20/DFS 优点 不妨回忆一下Tarjan算法求解LCA问题 由于只保存了一条路径，空间重复利用 缺点 找到的解不一定是“最少”步数的 无论BFS，DFS找到解都和解的“位置”有关21/回文划分问题 给定一个字符串s，将s划分成若干子串，使得每一个子串都是回文串。计算s的所有可能的划分。如：s=“aab”，返回“aa”，“b”；“a”，“a”，“b”。22/问题分析 在每一步都可以判断中间结果是否为合法结果：回溯法如果某一次发现划分不合法，立刻对该分支限界。一个长度为n的字符串，有n-1个位置可以截断，每个位置可断可不断，因此时间复杂度为O(2n-1)。23/Code24/思考 与之类似的：给定仅包含数字的字符串，返回所有可能的有效IP地址组合。如：“25525511135”，返回“255.255.11.135”，“255.255.111.35”。该问题只插入3个分割位置。只有添加了第3个分割符后，才能判断当前划分是否合法。如：2.5.5.25511135，才能判断出是非法的。25/八皇后问题 在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种解法。26/思路分析 分析：显然任意一行有且仅有1个皇后，使用数组queen07表示第i行的皇后位于哪一列。对于“12345678”这个字符串，调用全排列问题的代码，并且加入分支限界的条件判断是否相互攻击即可；此外，也可以使用深度优先的想法，将第i个皇后放置在第j列上，如果当前位置与其他皇后相互攻击，则剪枝掉该结点。上述分析完全可以扩展到N皇后问题。27/Code28/数独Sudoku 解数独问题，初始化时的空位用.表示。每行、每列、每个九宫内，都是1-9这9个数字。29/数独Sudoku分析 若当前位置是空格，则尝试从1到9的所有数；如果对于1到9的某些数字，当前是合法的，则继续尝试下一个位置调用自身即可。30/Code31/非递归数独Sudoku32/再谈LCA：Tarjan算法 Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问(求一次LCA叫做一次询问)，然后并不一定按照原来的顺序处理这些询问，该算法的时间复杂度O(N*(N)+Q)，其中，(x)不大于4，N表示问题规模，Q表示询问次数。33/Tarjan概览Tarjan算法基于深度优先搜索，对于新搜索到的一个结点u，首先创建由这个结点u构成的集合setU，再对当前结点u的每一个子树subTree进行搜索，每搜索完一棵子树sub，则可确定子树sub内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树sub之外，这时把子树sub所形成的集合setSub与当前结点的集合setU合并成set，并将当前结点u设为这个集合set的祖先Ua。之后继续搜索下一棵子树subNext，直到当前结点u的所有子树搜索完。这时把当前结点u设为checked，同时可以处理有关当前结点u的LCA询问，如果有一个从当前结点u到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点u与v的最近公共祖先LCA一定是未checked，而这个最近公共祖先LCA包含v的子树subV一定已经搜索过了，那么LCA一定是v所在集合的祖先Va。34/Tarjan算法：深度优先(2,10)(10,7)(9,10)(10,8)35/Tarjan Code36/处理查询的方法-邻接表 遍历P中的查询(a,b)，将a插入到b的列表中，b插入到a的列表中；常见的空间检索方案。37/Edsger Wybe Dijkstra 提出“goto有害论”;提出信号量和PV原语;解决了“哲学家聚餐”问题;最短路径算法(SPF)和银行家算法的创造者;第一个Algol 60编译器的设计者和实现者;THE操作系统的设计者和开发者;还有提过的“荷兰国旗问题”。38/最短路径SPF：Shortest Path First(Dijkstra)对于从v0至w，且经过最后一个中间结点为u的最短路径，有：DIST(w)=DIST(u)+c(u,w)随着u的加入，DIST(w)调整为 DIST(w)=min(DIST(w),DIST(u)+c(u,w)39/最短路径示例40/最短路径示例 算法的执行在有n-1个结点加入到S中后终止，此时求出了v0至其它各结点的最短路径。问题：如何求出所有这些最短路径？记录前驱生成最短路径的贪心算法procedure SHORTEST-PATHS(v,COST,DIST,n)/G是一个n结点有向图，它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置从结点v到结点j的最短路径长度，这里1jn。特殊的，DIST(v)被置成零/boolean S(1:n);real COST(1:n,1:n),DIST(1:n)integer u,v,n,num,i,wfor i1 to n do/将集合S初始化为空/S(i)0;DIST(i)COST(v,i)/若v到i没有边，DIST(i)=/repeatS(v)1;DIST(v)0 /结点v计入S/for num2 to n-1 do/确定由结点v出发的n-1条路/选取结点u,它使得DIST(u)=S(u)1/结点u计入S/for 所有S(w)0的结点w do /修改DIST(w)/DIST(w)=min(DIST(w),DIST(u)+COST(u,w)repeatrepeatend SHORTEST-PATHS)(min0)(wDISTwS42/Floyd算法 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者罗伯特弗洛伊德命名。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。43/算法分析 记录mapi,j为结点i到结点j的最短路径的距离；则：mapi,j=min mapi,k+mapk,j,mapi,j k取所有结点 同时，mapn,n=0 i,j,k各自从0到N-1，所以时间复杂度为O(n3)此外，如果图中存在负的权值，算法也是适用的。思考：Dijkstra算法允许边存在负权吗？44/Floyd算法45/带负权的最短路径 计算图中最小的权值，若该权值大于0，按照Dijkstra算法正常计算；若小于0，则所有权值都加上该权值的绝对值+1，则修改后的图不再含有负权。使用Dijkstra算法计算最小路径。是否可行？46/带负权的最短路径：Bellman-ford算法 本质：动态规划 适用：单源结点到其他所有结点的最短路径 若u-v是有向边，则dv=du+dis(u,v)这个操作被成为松弛操作。优点：对边权无要求，可以发现负环。47/Bellman-ford算法48/Bellman-ford算法分析图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径。因为最短路径最多只包含|v|-1条边，所以，只需要循环|v|-1次。略做优化：如果第k次松弛操作后，最短路径没有得到更新，显然，后面仍然无法得到更新，可提前退出。并且，如果k8-0-3-7-1-5-6-9-4-11-10-1257/拓扑排序的方法 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；从网中删去该顶点，并且删去从该顶点发出的全部有向边；重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。58/拓扑排序说明 不断找入度为0的点 可以用队列(或者栈)保存入度为0的点，避免每次遍历所有点查找入度；可以发现圈 排序列表中的点需要更新与之连接的点的入度。入度减小1之后，如果为0，放入队列(或者栈)中；59/扩展：拓扑的几何含义 一种关系：如三维数据间的拓扑关系60/三维拓扑重建61/视角再次放大面面、面线的拓扑62/参考文献 余祥宣等，计算机算法基础M，华中科技大学出版社，2001 戴方勤,LeetCode 题解,2014 http:/ 更多算法面试题在http:/ 直播课程 问答社区 contact us：微博研究者July七月问答邹博_机器学习64/感谢大家！欢迎大家提出宝贵的意见！