Coding Patterns: Topological Sort (Graph)

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort, In-place Reversal of a Linked List, Breadth First Search (BFS), Depth First Search (DFS), Two Heaps, Subsets, Modified Binary Search, Top K Numbers, K-way Merge and 0/1 Knapsack patterns and today, we will introduce Topological Sort pattern which is very useful for finding a linear ordering of elements that have dependencies on each other.

Problem: Course Schedule

LeetCode 207 - Course Schedule [medium]

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0, 1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1, 0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1, 0], [0, 1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 
             you should also have finished course 1. So it is impossible.

Note:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.

Topological Sort Solution

The aim of topological sort is to provide a partial ordering among the vertices of the graph such that if there is an edge from U to V then U <= V, which means, U comes before V in the ordering.

1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
3. Topological ordering starts with one of the sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in a Breadth First Search (BFS) way.

a. Initialization

We will store the graph in Adjacency Lists, which means each parent vertex will have a list containing all of its children. We will do this using a Hash Table where the key will be the parent vertex number and the value will be a List containing children vertices.

To find the sources, we will keep a Hash Table to count the in-degrees (count of incoming edges of each vertex). Any vertex with 0 in-degree will be a source.

b. Build the graph and find in-degrees of all vertices

We will build the graph from the input and populate the in-degrees Hash Table.

c. Find all sources

All vertices with 0 in-degrees will be our sources and we will store them in a Queue.

d. Sort

For each source:

• Add it to the sorted list.
• Get all of its children from the graph.
• Decrement the in-degree of each child by 1.
• If a child’s in-degree becomes 0, add it to the sources Queue.

Repeat these steps, until the source Queue is empty.

from collections import deque
from typing import List


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        sorted_list = []

        if numCourses <= 0:
            return False

        # a. Initialization
        graph = {i: [] for i in range(numCourses)}  # adjacency list graph
        in_degree = {i: 0 for i in range(numCourses)}  # count of incoming edges

        # b. Build the graph
        for prerequisite in prerequisites:
            parent, child = prerequisite[0], prerequisite[1]
            graph[parent].append(child)  # put the child into it's parent's list
            in_degree[child] += 1

        # c. Find all sources
        sources = deque()
        for key in in_degree:
            if in_degree[key] == 0:
                sources.append(key)

        # d. Sort
        while sources:
            vertex = sources.popleft()
            sorted_list.append(vertex)
            for child in graph[vertex]:  # get the node's children to decrement their in-degrees
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    sources.append(child)

        # if sorted_list does not contain all the courses, there is a cyclic dependency between courses
        # scheduling is not possible if there is a cyclic dependency
        return len(sorted_list) == numCourses

Time Complexity: O(V + E) where V is the total number of courses and E is the total number of prerequisites.

Space Complexity: O(V + E) since we are storing all of the prerequisites for each course in an adjacency list.

How to identify?

Topological Sort pattern is very useful for finding a linear ordering of elements that have dependencies on each other.

Scheduling or grouping problems which have dependencies between items are good examples to the problems that can be solved with using this technique.

Similar LeetCode Problems

• LeetCode 210 - Course Schedule II [medium]
• LeetCode 269 - Alien Dictionary [hard] [premium]
• LeetCode 310 - Minimum Height Trees [medium]