DSA Visualizations | Hello Interview

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 graph (left) and its topological sort (right)

In more formal terms, a topological sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

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.

The indegree is shown next to each 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]

Note that we can output the indegrees as an array because the nodes are numbered from 0 to n - 1. (We can look up the indegree of node i at index i in the array.) If the nodes were numbered differently, we would need a dictionary to map each node to its indegree.

def indegree(n, edges): 
    indegree = [0] * n
    for u, v in edges:
        indegree[v] += 1
    return 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] * n
    for u in adj_list:
        # increment the indegree of each neighbor of u
        for 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:
1. Dequeue the first node from the queue and add it to the topological order.
2. 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.

The indegree is shown next to 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.

enqueue nodes with indegree 0

0 / 1

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.

dequeue and add node 0 to topological sort

0 / 1

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.

decrement indegree of neighbors

0 / 8

Step 4: Return the topological order.

dequeue and add node 5 to topological sort

0 / 1

Solution

from collections import deque

def topological_sort(adj_list, n):

  # calculate indegree of each node
  indegree = [0] * n
  for u in adj_list:
      for v in adj_list[u]:
          indegree[v] += 1

  # enqueue nodes with indegree 0
  queue = 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 neighbor
          indegree[v] -= 1

          # if neighbor's indegree is 0, enqueue it
          if 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.

Next: Course Schedule

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Backtracking: Combination Sum

Course Schedule

Topological Sort

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

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 graph (left) and its topological sort (right)

In more formal terms, a topological sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

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.

The indegree is shown next to each 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] * n
    for u, v in edges:
        indegree[v] += 1
    return 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.

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] * n
    for u in adj_list:
        # increment the indegree of each neighbor of u
        for 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:
1. Dequeue the first node from the queue and add it to the topological order.
2. 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.

The indegree is shown next to 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.

enqueue nodes with indegree 0

0 / 1

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.

dequeue and add node 0 to topological sort

0 / 1

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.

decrement indegree of neighbors

0 / 8

Step 4: Return the topological order.

dequeue and add node 5 to topological sort

0 / 1

Solution

from collections import deque

def topological_sort(adj_list, n):

  # calculate indegree of each node
  indegree = [0] * n
  for u in adj_list:
      for v in adj_list[u]:
          indegree[v] += 1

  # enqueue nodes with indegree 0
  queue = 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 neighbor
          indegree[v] -= 1

          # if neighbor's indegree is 0, enqueue it
          if indegree[v] == 0:
              queue.append(v)
              
  return order

Complexity Analysis

The complexity of this algorithm is the same of BFS.

Next: Course Schedule

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103