Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Topological Sort

You are given a list of courses and their prerequisites. Produce an order in which every course can be taken after the ones it depends on.

3 needs 2 and 1        a valid order is 0, 1, 2, 3
2 needs 1
1 needs 0

A plain graph traversal does not answer this. Breadth First Search visits everything reachable, in some order. Nothing in it says "wait until every prerequisite of this node is done".

The missing idea is small. A node is ready when it has no unfinished prerequisites left. Count how many each node has. Take any node whose count is zero

.....

.....

.....

Like the course? Get enrolled and start learning!
M

makarand.h

· 2 years ago

In the below example given in the text, 6 needs to come after both 2, and 0 because it depends on both. But in Order 1 and Order 3, 6 comes before 0.

Text Snippet:

Consider the following Directed Acyclic Graph (DAG):

    5        7
   / \      / \
  2   0    3   4
   \ /    /     \
    6    1       8

In this graph, there are several possible topological sorts:

  1. Order 1: 7, 5, 2, 6, 3, 1, 0, 4, 8
  2. Order 2: 7, 5, 2, 3, 1, 0, 4, 6, 8
  3. Order 3: 5, 7, 3, 2, 1, 6, 0, 4, 8
HaoPo Yang

HaoPo Yang

· 2 years ago

as title

Manuel

Manuel

· 2 years ago

If you have a graph like this 5->2

The result will show a topological with all numbers from in the range 0 to 6, Including vertices that don't exist.

Hayden van Reyswoud

Hayden van Reyswoud

· 2 years ago

The DFS implementation here does not detect cycles.

An example that does would be helpful.