algorithm - 针对以下问题提出线性时间解决方案

有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），并且将减少列表被迭代的次数，因为如果按依赖关系排序（key j），那么我们知道一旦j超过包的大小，我们就知道没有更多的依赖列表，并且for循环可以被打破。
排序后的列表：（4，1）（5，1）（1，2）（3，2）（8，3）（3，4）（5，4）（7，6）（6，8）
此外，每次找到依赖项时，都会将其从临时数组中移除，然后递归地将其传递到函数中。
它还确保，如果依赖项已被记录，则不会进行调用或迭代/比较。
这可以算出大约37个比较，但我知道这不是线性时间。我无法发现什么比我已经得到的要快，很难分析我提出的算法的复杂性，但我认为它是O（n ^ 2／b）。

最佳答案

使用排序不适合此问题。您将能够对所有节点进行排序，但在给定的包将变得困难之前，需要确定安装的最小包集。
一种更好的方法是将依赖关系视为图中的边，并以相反的方向表示它们也就是说，如果存在依赖项(i, j)（即i应在j之前安装），请在图形中添加从j到i的边。现在已经定义了这个图，需要在packagex之前安装的包的列表正是那些可以从这样定义的图中的x访问的包要查找可以使用的节点和图形搜索算法，例如广度优先搜索或深度优先搜索。

关于algorithm - 针对以下问题提出线性时间解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53186046/