**Topological Sort**: A **topological sort** or **topological ordering** of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Source: wiki

**Example**:

As in the image above, the topological order is 7 6 5 4 3 2 1 0. There can be one or more topological order in any graph. Like in the example above 7 5 6 4 2 3 1 0 is also a topological order.

**Approach:**

**Shall we use Depth First Search?**

The DFS of the example above will be ‘7 6 4 3 1 0 5 2’ but in topological sort 2 should appear before 1 and 5 should appear before 4. So it might look like that we can use DFS but we cannot use DFS as it is but yes we can modify DFS to get the topological sort.

Read about DFS if you need to brush up about it.

**Modified DFS: **

- Use temporary stack to store the vertex.
- Maintain a visited [] to keep track of already visited vertices.
- In DFS we print the vertex and make recursive call to the adjacent vertices but here we will make the recursive call to the adjacent vertices and then push the vertex to stack.
- Observe closely the previous step, it will ensure that vertex will be pushed to stack only when all of its adjacent vertices (descendants) are pushed into stack.
- Finally print the stack.
- For disconnected graph, Iterate through all the vertices, during iteration, at a time consider each vertex as source (if not already visited).

**Time Complexity**: O(V+E)

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.LinkedList; | |

import java.util.Stack; | |

public class TopologicalSort { | |

static class Graph { | |

int vertices; | |

LinkedList<Integer>[] adjList; | |

Graph(int vertices) { | |

this.vertices = vertices; | |

adjList = new LinkedList[vertices]; | |

for (int i = 0; i < vertices; i++) { | |

adjList[i] = new LinkedList<>(); | |

} | |

} | |

public void addEgde(int source, int destination) { | |

adjList[source].addFirst(destination); | |

} | |

public void topologicalSorting() { | |

boolean[] visited = new boolean[vertices]; | |

Stack<Integer> stack = new Stack<>(); | |

//visit from each node if not already visited | |

for (int i = 0; i < vertices; i++) { | |

if (!visited[i]) { | |

topologicalSortUtil(i, visited, stack); | |

} | |

} | |

System.out.println("Topological Sort: "); | |

int size = stack.size(); | |

for (int i = 0; i <size ; i++) { | |

System.out.print(stack.pop() + " "); | |

} | |

} | |

public void topologicalSortUtil(int start, boolean[] visited, Stack<Integer> stack) { | |

visited[start] = true; | |

for (int i = 0; i < adjList[start].size(); i++) { | |

int vertex = adjList[start].get(i); | |

if (!visited[vertex]) | |

topologicalSortUtil(vertex, visited, stack); | |

} | |

stack.push(start); | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 8; | |

Graph graph = new Graph(vertices); | |

graph.addEgde(7, 6); | |

graph.addEgde(7, 5); | |

graph.addEgde(6, 4); | |

graph.addEgde(6, 3); | |

graph.addEgde(5, 4); | |

graph.addEgde(5, 2); | |

graph.addEgde(3, 1); | |

graph.addEgde(2, 1); | |

graph.addEgde(1, 0); | |

graph.topologicalSorting(); | |

} | |

} |

**Output:**

Topological Sort: 7 6 5 4 3 2 1 0