All Topological Sort in Directed Acyclic Graph
In the realm of directed acyclic graphs (DAGs), finding and understanding all possible topological sorts is a fascinating problem. Topological sorting is a linear ordering of the vertices such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This post delves into the concept of finding all topological sorts in a directed acyclic graph.
Problem Statement
Given a directed acyclic graph, the task is to generate and display all possible topological sorts.
Description with Example
Consider a DAG with six vertices labeled from 0 to 5. The graph's edges are defined as follows:

- Vertex 1 is connected to vertices 0, 4, and 5.
- Vertex 2 is connected to vertices 0, 4, and 5.
- Vertex 3 is connected to vertices 4 and 5.
- Vertex 5 is connected to vertex 4.
The goal is to find all the possible linear orderings of the vertices that satisfy the topological ordering condition.
Idea to Solve
To generate all topological sorts in a DAG, you can use a backtracking approach. Start by initializing arrays to keep track of visited vertices, indegrees (number of incoming edges) for each vertex, and a result array to store the current topological ordering. Recursively explore all vertices with indegree 0, mark them as visited, update indegrees, and backtrack when necessary.
Pseudocode
function findTopologicalSorts(graph, indegree, visited, result, index):
if index == graph.size:
print result
return
for each vertex in graph:
if indegree[vertex] == 0 and not visited[vertex]:
visited[vertex] = true
result[index] = vertex
update indegrees after removing vertex
findTopologicalSorts(graph, updated indegree, visited, result, index + 1)
backtrack: restore visited and indegree for vertex
visited[vertex] = false
function generateTopologicalSorts(graph):
initialize arrays
findTopologicalSorts(graph, indegree, visited, result, 0)
Algorithm Explanation
-
The
findTopologicalSorts
function generates all topological sorts recursively. If the index reaches the graph size, a valid topological ordering is found, and it's printed. -
For each vertex, check if its indegree is 0 and it's not visited. If both conditions are met, mark the vertex as visited, add it to the result, update the indegrees after removing the vertex, and make a recursive call with the updated state.
-
Backtrack by restoring visited and indegree for the vertex to explore different possibilities.
-
The
generateTopologicalSorts
function initializes arrays and callsfindTopologicalSorts
.
Code Solution
-
1) All topological sorts of a directed acyclic graph in java
2) All topological sorts of a directed acyclic graph in c++
3) All topological sorts of a directed acyclic graph in c
4) All topological sorts of a directed acyclic graph in c#
5) All topological sorts of a directed acyclic graph in vb.net
6) All topological sorts of a directed acyclic graph in php
7) All topological sorts of a directed acyclic graph in python
8) All topological sorts of a directed acyclic graph in ruby
9) All topological sorts of a directed acyclic graph in scala
10) All topological sorts of a directed acyclic graph in swift
11) All topological sorts of a directed acyclic graph in kotlin
12) All topological sorts of a directed acyclic graph in golang
13) All topological sorts of a directed acyclic graph in node js
Time Complexity
The time complexity of this solution depends on the number of possible topological orders. In the worst case, it could be exponential, as each vertex can be in or out of the topological order. The precise complexity is challenging to express formally.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment