How do I make my topological sort to be linear time? (Code is well annotated)

Question

Question 1:

What should the correct running time be for a well implemented topological sort. I am seeing different opinions:

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

Geeksforgeeks says: O(V+E)

Question 2:

My implementation is running at O(V*E). Because at worst, I will need to loop through the graph E times and each time I will need to check V items. How do I make my implementation into linear time.

---

The algorithm works in steps:

1. Produce the graph in the form of an adjacency list

e.g. this graph

0 - - 2
    \
      1 -- 3

produces this adjacency list

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

0 depends on nothing, 1 depends on 0 etc..

2. Iterate through the graph and find nodes that does not have any dependencies

---

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

Ok this is a good question. So long as the graph is directed acyclic, then depth first search can be used and depth first search has order O(n+m) as is explained here: http://www.csd.uoc.gr/~hy583/reviewed_notes/dfs_dags.pdf If you are curious networkx has an implementation using depth first search and it is called topological_sort which has source code available for viewing a python implementation.