## Topological Sort

**Pre-Requisite**: Depth-First Search, Breadth-First Search

When working with graphs, make sure you first practice using Depth-First Search (DFS) and Breadth-First Search (BFS) to solve coding interview questions, as they are the most common graph algorithms you'll encounter.

This section covers **Topological Sort**, an important but less common graph algorithm.

Topological sort takes a directed acyclic graph (DAG) and turns it into a linear ordering of nodes such that the directed edges only point forward, from left-to-right:

A given graph may have more than one valid topological sorts. We'll look at one algorithm for finding a topological sort - **Kahn's Algorithm**, which uses the concept of **indegrees**.

### Indegrees

Each node in a graph has an **indegree**, which is the number of incoming edges to that node.

##### Calculate Indegrees

**List of Edges**

If our graph is given to us as list of edges, we can calculate the indegree of each node by iterating through the edges and incrementing the indegree of the destination node.

###### DESCRIPTION

You are given a graph with n nodes, where each node has an integer value from 0 to n - 1.

The graph is represent by a list of edges, where edges[i] = [u, v] is a directed edge from node u to node v. Write a function to calculate the indegree of each node in the graph.

**Example**
Input:
edges = [(0, 1), (1, 2), (1, 3), (3, 2), (3, 4)]
n = 5

Output: [0, 1, 2, 1, 1]

def indegree(n, edges):indegree = [0] * nfor u, v in edges:indegree[v] += 1return indegree

**Adjacency List**

If our graph is given to us as an adjacency list, we can calculate the indegree of each node by iterating through the neighbors of each node and incrementing their indegree.

###### DESCRIPTION

You are given a graph with n nodes, where each node has an integer value from 0 to n - 1.

The graph is represent by an adjacency list, where each node i is mapped to a list of nodes that have a directed edge from node i to them. Write a function to calculate the indegree of each node in the graph.

**Example**

`Input: edges = {0: [1], 1: [2, 3], 2: [], 3: [2, 4], 4: []} n = 5`

Output: [0, 1, 2, 1, 1]

def indegree(adj_list, n):indegree = [0] * nfor u in adj_list:# increment the indegree of each neighbor of ufor v in adj_list[u]:indegree[v] += 1

### Kahn's Algorithm

Kahn's algorithm is a form of Breadth-First Search in which nodes with lower indegrees are placed on the queue before nodes with higher indegrees.

The algorithm is as follows:

- Calculate the indegree of each node.
- Add all nodes with an indegree of 0 to a queue.
- While the queue is not empty:
- Dequeue the first node from the queue and add it to the topological order.
- For each neighbor of the node, decrement its indegree by 1. If the neighbor's indegree is now 0, add it to the queue.

- Return the topological order.

### Walkthrough

We'll walkthrough how the algorithm works for the graph given by the adjacency list below:

adjList = {0: [1, 3],1: [2],2: [],3: [1, 4, 5],4: [5],5: []}

**Step 1:**
Calculate the indegree of each node.

**Step 2:**
Add all nodes with an indegree of 0 to the queue.

**Step 3:**

While the queue is not empty:

- Deque the first node from the queue and add it to the topological sort.

- Decrement the indegree of each neighbor of the node. If this results in a neighbor having an indegree of 0, add it to the queue.

- We have fully processed node 1, so now repeat the process of dequeuing and decrementing indegrees for the next node in the queue until the queue is empty.

**Step 4:**
Return the topological order.

#### Solution

from collections import dequedef topological_sort(adj_list, n):# calculate indegree of each nodeindegree = [0] * nfor u in adj_list:for v in adj_list[u]:indegree[v] += 1# enqueue nodes with indegree 0queue = deque([u for u in range(n) if indegree[u] == 0])order = []while queue:u = queue.popleft()order.append(u)for v in adj_list[u]:# decrement indegree of each neighborindegree[v] -= 1# if neighbor's indegree is 0, enqueue itif indegree[v] == 0:queue.append(v)return order

### Complexity Analysis

The complexity of this algorithm is the same of BFS.

**Time Complexity:**
The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we visit each vertex and edge once.

**Space Complexity:**
The space complexity of this algorithm is O(V), where V is the number of vertices in the graph. This is due to both the data structure we use to store the indegrees of each vertice, and the queue we use to store the vertices with an indegree of 0, both of which store up to V elements.

Loading comments...