DEV Community

Cover image for Graph Algorithm - Topological Sorting
Rohith V
Rohith V

Posted on

Graph Algorithm - Topological Sorting

Directed acyclic graph

A directed acyclic graph or DAG is a directed graph with no directed cycles. It consists of vertices and edges, each edge directed from one vertex to another, such that those directions will never form a closed loop.

A directed graph is DAG only if topologically ordered.

What is Topological Sorting

Topological sorting for Directed Acyclic Graph is a linear ordering of vertices such that for every directed edge u->v, vertex u comes before v in the order. Topological Sorting for the graph is not possible if it is not a DAG.
There can be more than one topological sorting for a graph. The first vertex in topological sorting is always a vertex with an in-degree of zero.

DFS Algorithm to find Topological Sorting

Consider a Directed Acyclic Graph.

Example for DAG

  • Initialise an empty stack, visited boolean array.

  • Start dfs from a node. Pass the stack, visited array, and node into the recursive method.

dfs(node, stack, visited).

  • Inside the dfs recursive function, mark the node as visited.

  • Traverse through all the unvisited children of the node.

  • Do dfs on the unvisited child.

  • Finally, push the node into the stack if all the child gets visited.

  • After completing the dfs traversal, check if the size of the stack is equal to the number of the node.
    If not, the graph is not a DAG and does not have a topological order.
    Else pop all the elements from the stack and store them in a result array.

  • Return the result array.

TopoSort Walkthrough

Time and Space Complexity

  • We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.

  • We use a visited array, an extra stack and an adjacency list for the graph. So the space complexity will be O(V) + O(V) + O(V + E) + extra space for the recursion stack.

Code

Java Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Topological Sorting

Github Link

GitHub logo Rohithv07 / LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions




Discussion (0)