为以下问题提出线性时间解决方案

Question

有n个包，编号为1到n。一组 K 对 (i, j) 定义了一个依赖项列表，这样就无法在不安装包 i 的情况下安装包 j。

想出一个线性时间算法，该算法采用列表 K，并生成安装包 1 所需的所有包的列表。

这是我的尝试：

function algortihm(n,K)
    radix sort K(i,j) on key j
    dependencies <- arr size n   //declare array           
    currPackage <- 1
    tempArr <- K
    function func(currPackage, K) 
        dependencies.append(currPackage)
        count <- -1
        for (i,j) in K:
            if j not in dependencies:
                count <- count + 1
                if j == currPackage:
                    tempArr.remove(count)
                    func(i, tempArr)
                endif
            endif
            if j > currPackage:
                break
            endif
        endfor
    endfunction
    return dependencies
endfunction

使用此输入 K = (1, 2) (3, 2) (3, 4) (4, 1) (5, 1) (5, 4) (6, 8) (8, 3) (7, 6)

基数排序的复杂度为 O(n) 并且会减少迭代列表的次数，因为如果我们按依赖项（键 j）排序，那么我们知道一旦 j 超过了我们知道的包的大小没有更多的依赖项列表，可以打破 for 循环。

排序后的列表：(4, 1) (5, 1) (1, 2) (3, 2) (8, 3) (3, 4) (5, 4) (7, 6) ( 6、8)

此外，每次找到依赖项时，都会将其从临时数组中删除，然后递归传递给函数。如果已经记录了依赖关系，它还确保不会进行调用或 iteration/comparison。

这算出大约进行了 37 次比较，但我知道这不是线性时间。我只是无法发现什么会比我已经得到的更快，很难分析我提出的算法的复杂性，但我认为它是 O(n^2/b)

Answer 1

使用排序不适合这个问题。您将能够对所有节点进行排序，但很难确定在给定包之前需要安装的最少包集。

更好的方法是将依赖关系视为图中的边，并以相反的方向表示它们。也就是说，如果存在依赖项 (i, j)（意味着 i 应该在 j 之前安装），请在图中添加从 j 到 i 的边。现在已经定义了这个图，需要在 package x 之前安装的包列表正是在如此定义的图中从 x 可以到达的那些包。要查找哪些是您可以使用的节点和图形搜索算法，例如广度优先搜索或深度优先搜索。

为以下问题提出线性时间解决方案

Coming up with a linear time solution for the following problem

sorting

algorithm

complexity-theory

time-complexity