In this article, you will learn to implement a Topological sort algorithm by using Depth-First Search and In-degree algorithms

Topological sort is an algorithm which takes a directed acyclic graph and returns a list of vertices in the linear ordering where each vertex has to precede all vertices it directs to

There are no topological orderings exist in a directed cyclic graph and more than one of them can exist in one directed acyclic graph

Let's get started

### Problem

• Given a directed graph G = (V, E)

• Write an algorithm to return a sorted vertex list in topological ordering

• Return an empty list if no topological orderings exist

### Example 1

• Input: Given a directed graph G = (V, E) with V = 4 and E = [[0, 1], [2, 0], [2, 1], [3, 2]] • Output: [3, 2, 0, 1]

• Explanation: [3, 2, 1, 0] is also a valid topological ordering

### Example 2

• Input: Given a directed graph G = (V, E) with V = 5 and E = [[0, 1], [1, 2], [2, 0], [1, 3], [2, 4]] • Output: []

• Explanation: No topological orderings exist as [0, 1], [1, 2], and [2, 0] form a cycle. Vertex 0 can not both precede and follow vertex 2

### Approach 1: DFS Iterative with Color

• Run DFS Iterative with Color to find a vertex with no outgoing edges (Black vertex) and add it to a stack S. Stop finding when found a cycle

Repeat for all other vertices in the graph

• Convert S to a list to get the final result

``````
``````

`GraphDirectedByAdjacencyList` is defined in Graph Data Structure Tutorial

• Output
``````There are no topological orderings as the input graph is cyclic
3 2 0 1
``````
• Time complexity: O(V+E)

• Space complexity: O(V)

### Approach 2: DFS Recursive with Color

• Run DFS Recursive with Color to find a vertex with no outgoing edges (Black vertex) and add it to a stack S. Stop finding when found a cycle

Repeat for all other vertices in the graph

• Convert S to a list to get the final result

``````
``````

`GraphDirectedByAdjacencyList` is defined in Graph Data Structure Tutorial

• Output
``````There are no topological orderings as the input graph is cyclic
3 2 0 1
``````
• Time complexity: O(V+E)

• Space complexity: O(V)

### Approach 3: In-degree

• Find a vertex with no incoming edges (in-degree = 0) and add it to a queue Q

Repeat for all other vertices in the graph

• Convert Q to a list to get the final result

``````
``````

`GraphDirectedByAdjacencyList` is defined in Graph Data Structure Tutorial

• Output
``````There are no topological orderings as the input graph is cyclic
3 2 0 1
``````
• Time complexity: O(V+E)

• Space complexity: O(V)