# 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.

**Source:**Any node that has*no incoming edge*and has*only outgoing edges*is called a**source**.**Sink:**Any node that has*only incoming edges*and*no outgoing edge*is called a**sink**.- Topological ordering
*starts*with one of the**sources**and*ends*at one of the**sinks**. - 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.