43拓扑排序:如何确定代码源文件的编译依赖关系?.pdf
《43拓扑排序:如何确定代码源文件的编译依赖关系?.pdf》由会员分享,可在线阅读,更多相关《43拓扑排序:如何确定代码源文件的编译依赖关系?.pdf(8页珍藏版)》请在三一文库上搜索。
1、43|拓扑排序:如何确定代码源文件的编译依赖关系? file:/F/temp/geektime/数据结构与算法之美/43拓扑排序:如何确定代码源文件的编译依赖关系?.html2019/1/15 15:36:34 43|拓扑排序:如何确定代码源文件的编译依赖关系? 从今天开始,我们就进入了专栏的高级篇。相对基础篇,高级篇涉及的知识点,都比较零散,不是太系统。所以,我会围绕一个实际软件开发的问题,在阐述具 体解决方法的过程中,将涉及的知识点给你详细讲解出来。 所以,相较于基础篇“开篇问题-知识讲解-回答开篇-总结-课后思考”这样的文章结构,高级篇我稍作了些改变,大致分为这样几个部分:“问题阐述-算
2、法解析-总结 引申-课后思考”。 好了,现在,我们就进入高级篇的第一节,如何确定代码源文件的编译依赖关系? 我们知道,一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候,需要按照依赖关系,依次编译每个源文件。比如,A.cpp依赖B.cpp,那在 编译的时候,编译器需要先编译B.cpp,才能编译A.cpp。 编译器通过分析源文件或者程序员事先写好的编译配置文件(比如Makefile文件),来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依 赖关系,确定一个全局的编译顺序呢? 算法解析 “”“” 43|拓扑排序:如何确定代码源文件的编译依赖关系? file:/F/
3、temp/geektime/数据结构与算法之美/43拓扑排序:如何确定代码源文件的编译依赖关系?.html2019/1/15 15:36:34 这个问题的解决思路与 图 这种数据结构的一个经典算法 拓扑排序算法 有关。那什么是拓扑排序呢?这个概念很好理解,我们先来看一个生活中的拓扑排序的例 子。 我们在穿衣服的时候都有一定的顺序,我们可以把这种顺序想成,衣服与衣服之间有一定的依赖关系。比如说,你必须先穿袜子才能穿鞋,先穿内裤才能穿秋 裤。假设我们现在有八件衣服要穿,它们之间的两两依赖关系我们已经很清楚了,那如何安排一个穿衣序列,能够满足所有的两两之间的依赖关系? 这就是个拓扑排序问题。从这个例
4、子中,你应该能想到,在很多时候,拓扑排序的序列并不是唯一的。你可以看我画的这幅图,我找到了好几种满足这些局部先 后关系的穿衣序列。 43|拓扑排序:如何确定代码源文件的编译依赖关系? file:/F/temp/geektime/数据结构与算法之美/43拓扑排序:如何确定代码源文件的编译依赖关系?.html2019/1/15 15:36:34 弄懂了这个生活中的例子,开篇的关于编译顺序的问题,你应该也有思路了。开篇问题跟这个问题的模型是一样的,也可以抽象成一个拓扑排序问题。 拓扑排序的原理非常简单,我们的重点应该放到拓扑排序的实现上面。 我前面多次讲过,算法是构建在具体的数据结构之上的。针对这个
5、问题,我们先来看下,如何将问题背景抽象成具体的数据结构? 我们可以把源文件与源文件之间的依赖关系,抽象成一个有向图。每个源文件对应图中的一个顶点,源文件之间的依赖关系就是顶点之间的边。 如果a先于b执行,也就是说b依赖于a,那么就在顶点a和顶点b之间,构建一条从a指向b的边。而且,这个图不仅要是有向图,还要是一个有向无环图,也就是不能 存在像a-b-c-a这样的循环依赖关系。因为图中一旦出现环,拓扑排序就无法工作了。实际上,拓扑排序本身就是基于有向无环图的一个算法。 public class Graph private int v; / 顶点的个数 private LinkedList adj
6、; / 邻接表 public Graph(int v) this.v = v; adj = new LinkedListv; for (int i=0; i(); public void addEdge(int s, int t) / s先于t,边s-t adjs.add(t); 数据结构定义好了,现在,我们来看,如何在这个有向无环图上,实现拓扑排序? 拓扑排序有两种实现方法,都不难理解。它们分别是Kahn算法和DFS深度优先搜索算法。我们依次来看下它们都是怎么工作的。 1.Kahn算法 Kahn算法实际上用的是贪心算法思想,思路非常简单、好懂。 定义数据结构的时候,如果s需要先于t执行,那就
7、添加一条s指向t的边。所以,如果某个顶点入度为0, 也就表示,没有任何顶点必须先于这个顶点执行,那么这 个顶点就可以执行了。 我们先从图中,找出一个入度为0的顶点,将其输出到拓扑排序的结果序列中(对应代码中就是把它打印出来),并且把这个顶点从图中删除(也就是把这个顶点 可达的顶点的入度都减1)。我们循环执行上面的过程,直到所有的顶点都被输出。最后输出的序列,就是满足局部依赖关系的拓扑排序。 我把Kahn算法用代码实现了一下,你可以结合着文字描述一块看下。不过,你应该能发现,这段代码实现更有技巧一些,并没有真正删除顶点的操作。代码中有 详细的注释,你自己来看,我就不多解释了。 public vo
8、id topoSortByKahn() int inDegree = new intv; / 统计每个顶点的入度 for (int i = 0; i w inDegreew+; LinkedList queue = new LinkedListi boolean visited = new booleanv; for (int i = 0; i inverseAdj, boolean visited) for (int i = 0; i “ + vertex); 这个算法包含两个关键部分。 第一部分是通过邻接表构造逆邻接表。邻接表中,边s-t表示s先于t执行,也就是t要依赖s。在逆邻接表中,边
9、s-t表示s依赖于t,s后于t执行。为什么这么转化呢? 这个跟我们这个算法的实现思想有关。 第二部分是这个算法的核心,也就是递归处理每个顶点。对于顶点vertex来说,我们先输出它可达的所有顶点,也就是说,先把它依赖的所有的顶点输出了,然后 43|拓扑排序:如何确定代码源文件的编译依赖关系? file:/F/temp/geektime/数据结构与算法之美/43拓扑排序:如何确定代码源文件的编译依赖关系?.html2019/1/15 15:36:34 再输出自己。 到这里,用Kahn算法和DFS算法求拓扑排序的原理和代码实现都讲完了。我们来看下,这两个算法的时间复杂度分别是多少呢? 从Kahn代
10、码中可以看出来,每个顶点被访问了一次,每个边也都被访问了一次,所以,Kahn算法的时间复杂度就是O(V+E)(V表示顶点个数,E表示边的个 数)。 DFS算法的时间复杂度我们之前分析过。每个顶点被访问两次,每条边都被访问一次,所以时间复杂度也是O(V+E)。 注意,这里的图可能不是连通的,有可能是有好几个不连通的子图构成,所以,E并不一定大于V,两者的大小关系不确定。所以,在表示时间复杂度的时 候,V、E都要考虑在内。 总结引申 在基础篇中,关于“图”,我们讲了图的定义和存储、图的广度和深度优先搜索。今天,我们又讲了一个关于图的算法,拓扑排序。 拓扑排序应用非常广泛,解决的问题的模型也非常一致
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 43 拓扑 排序 如何 确定 代码 源文件 编译 依赖 关系
链接地址:https://www.31doc.com/p-5529999.html