问题一：如何确定代码源文件的编译依赖关系？一个完整的项目会包含很多代码源文件。编译器在编译整个项目时，需要按照依赖关系，依次编译每个源文件。那编译器该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？
解题思路：这个问题可以抽象成一个拓扑排序的问题。我们可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。依赖关系不仅要是有向的，而且不能出现循环依赖，这也正好符合拓扑排序本身的特点，就是基于有向无环图的一个算法。
实现方式：拓扑排序的两种实现方式，一种是Kahn算法，另一种是DFS算法。
Kahn算法：统计每个顶点的入度，先把入度=0的顶点放入队列中。然后遍历队列，让入度=0的顶点A出队列。再遍历顶点A指向的顶点，并且使指向的顶点的入度都减一，如果满足入度=0，则把其也加入队列中。整个过程就是先计算入度=0的顶点，然后把入度=0的顶点所指向的顶点的入度-1，然后再次计算入度=0的顶点，从而就确定了一个依赖的先后关系。
DFS算法：通过邻接表构造逆邻接表。然后递归处理每个顶点，并先把它依赖的所有顶点输出了，然后再输出自己。实现代码如下：
问题二：像Google地图，百度地图，高德地图这样的软件。如果你想从家开车到公司，你输入起始，结束地址，地图就会给你规划一个最优出行路线。比如：最短路线，最少用时路线，最少红绿灯路线等等，作为一名软件工程师，你是否思考过地图软件的最优路线是如何计算出来的？底层依赖了什么算法呢？
解题思路：先解决最简单的，最短路线。把问题抽象成数据结构，显然地图抽象成图最合适不过了。把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就再两个顶点间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。提到最短路径算法，最出名的莫过于Dijkstra算法了。
实现方式：Dijkstra算法的代码实现如下图所示：
关于最少红绿灯的出行方案，我们只需要把每条边的权值改为1即可，算法还是不变，可以继续使用前面讲的Dijkstra算法。不过，边的权值为1，也就相当于无权图了，我们还可以使用广度优先搜索算法。
网友评论