[Algo] Install Dependencies 安装依赖 - SegmentFault

[Algo] Install Dependencies 安装依赖 - SegmentFault

Install Dependencies

给定软件之间安装的依赖关系，用一个二维数组表示，第一维表示依赖的序号，第二维表示依赖关系，比如要先装deps[0][0]，才能装deps[0][1]。安装时，要尽可能先安装依赖个数少的软件。求安装顺序。

拓扑排序

复杂度

时间 O(1) 空间 O(1)

思路

本题和Course Schedule的解法一样，不会拓扑排序的可以参考那篇文章。区别在于我们拓扑排序后的访问顺序，本来我们是用一个Queue来进行BFS，这里为了让依赖少的先安装，我们将Queue换成PriorityQueue，并以依赖数排序。用优先队列遍历图，很像是Cost based search 或者greedy，a star这种算法。注意，由于可能出现两个软件有同样依赖数的情况，比如两个软件剩余依赖都是0的时候，应该先装哪个呢？这个就要和面试官讨论了，可以在软件的数据结构中加入timestamp或者总依赖数等变量，供我们在ProrityQueue中作为第二个、第三个条件来比较。

Read full article from [Algo] Install Dependencies 安装依赖 - SegmentFault