如何使拓扑排序成为线性时间？（代码注释良好）

Question

问题1：

对于良好实现的拓扑排序，正确的运行时间应该是多少。我看到了不同的观点：

Wikipedia says: O(log^2(n))

Geeksforgeeks says: O(V+E)

问题2：

我的实现在O（V*E）上运行。因为在最坏的情况下，我需要在图中循环E次，每次我都需要检查V项。如何将实现转换为线性时间。你知道吗

---

算法分步骤工作：

1. 以邻接表的形式生成图形

例如，这个图表

0 - - 2
    \
      1 -- 3

生成此邻接列表

{0: [], 1: [0], 2: [0], 3: [1, 2]}

0不依赖于任何东西，1依赖于0等等。。你知道吗

1. 遍历图并查找没有任何依赖关系的节点

---

def produce_graph(prerequisites):
    adj = {}
    for course in prerequisites:
        if course[0] in adj:
            # append prequisites
            adj[course[0]].append(course[1])
        else:
            adj[course[0]] = [course[1]]

        # ensure that prerequisites are also in the graph
        if course[1] not in adj:
            adj[course[1]] = []

    return adj

def toposort(graph):
    sorted_courses = []
    while graph:

        # we mark this as False
        # In acyclic graph, we should be able to resolve at least
        # one node in each cycle
        acyclic = False
        for node, predecessors in graph.items():
            # here, we check whether this node has predecessors
            # if a node has no predecessors, it is already resolved,
            # we can jump straight to adding the node into sorted
            # else, mark resolved as False
            resolved = len(predecessors) == 0
            for predecessor in predecessors:
                # this node has predecessor that is not yet resolved
                if predecessor in graph:
                    resolved = False
                    break
                else:
                    # this particular predecessor is resolved
                    resolved = True

            # all the predecessor of this node has been resolved
            # therefore this node is also resolved
            if resolved:
                # since we are able to resolve this node
                # We mark this to be acyclic
                acyclic = True
                del graph[node]
                sorted_courses.append(node)

        # if we go through the graph, and found that we could not resolve
        # any node. Then that means this graph is cyclic
        if not acyclic:
            # if not acyclic then there is no order
            # return empty list
            return []

    return sorted_courses

graph = produce_graph([[1,0],[2,0],[3,1],[3,2]])
print toposort(graph)

Answer 1

好的，这是个好问题。只要图是有向无环的，那么就可以使用深度优先搜索，并且深度优先搜索的顺序为O（n+m），如下所述：http://www.csd.uoc.gr/~hy583/reviewed_notes/dfs_dags.pdf 如果您很好奇，networkx有一个使用深度优先搜索的实现，它被称为拓扑排序，它的源代码可用于查看python实现。你知道吗