Implementation 2

Implementation 2

The Idea: Begin with two hash tables. One to represent the graph, and a second one to represent the inverse of a graph. This just creates a separate graph with the edges swapped.The reason for this will become clear later on. Next, we instantiate a queue. This queue is always going to contain nodes that currently have no prerequisites. Instantiate the queue with all node(s) that have no dependances in the original graph g. Next initiate a BFS. The front of the queue is always going to contain a node that has no prerequisites, so append it to the solution array. Following that, the associated prerequisites must be removed. Previously, implementation 1 iterated through the entirety of the graph, and so this scaled the complexity of our model by n. Instead, iterate through all the associated edges of the removed node. This can be found within the inverse graph. As the elements become removed, we know that they also our only option for a potentially new independent node because initially the array was scanned for nodes without prerequisites and were placed into the queue. An acyclic graph will always reveal a topological ordering, so we can expect that our solution vector to contain the number of orderings as the original number number of nodes n.

Complexity: O(|V|+|E|) time and O(|V|) space

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices.

import queue
import collections

class Solution:
    def top_sort(self, n, dependencies):
        """
        :type n: int
        :type dependencies: List[List[int]]
        :rtype: List[int]
        """

        # build graph and its inverse
        g = {i:set() for i in range(0, n)}
        g_inv = collections.defaultdict(set)
        for i, j in dependencies:
            g[i].add(j)
            g_inv[j].add(i)

        # find all empty dependencies
        q = queue.Queue()
        for course in g:
            if not g[course]:
                q.put(course)

        # begin topological sort algorithm
        topo_sort = []
        while not q.empty():
            # get next independent node
            front = q.get()
            topo_sort.append(front)

            # remove all associated edges
            for elm in g_inv[front]:
                g[elm].remove(front)
                # check if is empty
                if not g[elm]:
                    q.put(elm)

        # make sure all elements are included
        # otherwise the graph does not have any topological ordering
        return topo_sort if len(topo_sort) == n else []


obj = Solution()
print(obj.top_sort(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print(obj.top_sort(2, [[0, 1], [1, 0]]))
print(obj.top_sort(2, [[1, 0]]))