Grokking Graph Algorithms for Coding Interviews

0% completed

​

Introduction to Topological Sort

What is Topological Sorting?

Topological sorting is a method used to order the vertices of a directed graph such that for every directed edge u \rightarrow v, vertex (u) comes before (v) in the ordering. This concept is crucial in scenarios where there is a dependency between tasks or elements.

For instance, in task scheduling, some tasks must be completed before others, making topological sorting a useful technique.

Topological Sorting in Directed Acyclic Graphs (DAGs)

Topological sorting is applicable exclusively to Directed Acyclic Graphs (DAGs)

.....

.....

.....

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

· a year 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

· a year ago

The DFS implementation here does not detect cycles.

An example that does would be helpful.