## DEV Community is a community of 877,885 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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.

• 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.

## Practice Problem

Topological Sorting