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.

Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Topological Sorting

Github Link