最优拓扑排序

Question

我找到了这个拓扑排序问题的解决方案，但这不是我在任何研究中遇到的解决方案，这让我相信它不是最理想的。问题（来自algoexpert）大致如下：“返回一个可能的图遍历，给定一个图，其中每个节点表示一个作业，每个边表示该作业的预请求。第一个参数是表示作业的数字列表，第二个参数是数组列表（大小2）其中，数组中的第一个数字表示作为第二个数字的作业的预请求。例如，输入（[1,2,3]，[1,3]，[2,1]，[2,3]）=>；[2,1,3]。注意：该图可能不是非循环的，算法应返回一个空数组。例如，输入（[1,2]，[1,2]，[2,1]]）=>；[]

一个流行的最佳解决方案对我来说有点困惑，因为我已经尝试过实现它，但是我的算法不断地检测到一个循环，短路返回一个空数组。这个算法以深度优先的方式“向后工作”，搜索图时“正在进行”和“访问”的节点都保存在内存中

我的算法最初发现没有prereq的图节点（因为这些节点可以立即添加到返回数组中），并从所有其他节点prereq中删除此节点。执行此删除操作时，如果此节点现在有0个prereq，则将其添加到堆栈中。当堆栈大小达到0时，如果返回数组的大小与第一个参数（作业列表）的大小匹配，则返回该数组，否则返回一个空数组，在本例中表示图中存在一个循环。以下是我的算法代码：

def topologicalSort(jobs, relations):
    rtn = []
    jobsHash = {}
    stackSet = set()
    for job in jobs:
        stackSet.add(job)
    for relation in relations:
        if relation[1] in stackSet:
            stackSet.remove(relation[1])
        if relation[0] not in jobsHash:
            jobsHash[relation[0]] = {"prereqs": set(), "depends": set()}
        jobsHash[relation[0]]["depends"].add(relation[1])
        if relation[1] not in jobsHash:
            jobsHash[relation[1]] = {"prereqs": set(), "depends": set()}
        jobsHash[relation[1]]["prereqs"].add(relation[0])
        if jobsHash[relation[0]]["prereqs"].__contains__(relation[1]):  # 2 node cycle shortcut
            return []
    stack = []
    for job in stackSet:
        stack.append(job)
    while len(stack):
        job = stack.pop()
        rtn.append(job)
        clearDepends(jobsHash, job, stack)
    if len(rtn) == len(jobs):
        return rtn
    else:
        return []


def clearDepends(jobsHash, job, stack):
    if job in jobsHash:
        for dependJob in jobsHash[job]["depends"]:
            jobsHash[dependJob]["prereqs"].remove(job)
            if not len(jobsHash[dependJob]["prereqs"]):
                stack.append(dependJob)
        jobsHash[job]["depends"] = set()


print(topologicalSort([1,2,3,4],[[1,2],[1,3],[3,2],[4,2],[4,3]]))

我发现该算法具有O（j+d）的时间复杂度和O（j+d）的空间复杂度，这与流行的算法属性是一致的。我的问题是，我找到了正确的复杂度，这是这个问题的最优解吗？谢谢！