Create account

DEV Community

Rohith V

Posted on Apr 18, 2022

Graph Algorithm - Topological Sorting

#java #datastructure #leetcode #algorithms

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.

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.

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.