Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction🧑🏻‍🎓
2.
Definition🧐
3.
Directed Acyclic Graph (DAG)🤔
4.
Need for Topological Ordering🕵🏻‍♂️
5.
Problem Statement👩‍🏫
5.1.
Example☝🏼
6.
Algorithm👨‍🎓
7.
Dry Run✏️
8.
Implementation🙎🏼
8.1.
 C++
8.2.
 Java
8.3.
Python
9.
Frequently Asked Questions
9.1.
What is a graph?
9.2.
What are some ways of representing a graph?  
9.3.
Explain DFS in a graph data structure.
9.4.
Explain BFS in a graph data structure.
9.5.
What are some real-world problems where graphs are utilized?
10.
Conclusion
Last Updated: Mar 27, 2024
Hard

All Topological Sorts of a Directed Acyclic Graph

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction🧑🏻‍🎓

A graph is any non-linear Data Structure made up of vertices and edges. In a graph, the edges are the lines that link any two nodes, while the vertices are occasionally also referred to as nodes. A graph in a more formal sense is made up of a collection of vertices (V) and a set of edges ( E ). The graph is represented as (E,  V).

OG image

The following article will find all topological sorts of a directed acyclic graph. Let’s go! 🫡

Definition🧐

For a directed acyclic graph, G(u,v), topological sorting is a linear ordering of the vertices where u occurs before v for every directed edge. If a graph is not a DAG, topological sorting for that graph is not possible.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Directed Acyclic Graph (DAG)🤔

DAG image

A collection of vertices connected by edges is referred to as a graph. Each edge in a directed graph has a direction from a start vertex to an end vertex. There are no directed cycles if we traverse the edges' direction and discover that no path forms any closed loops. It is a directed acyclic graph that has been created.

DAG is topologically ordered, meaning that the start vertex of each edge appears sooner in the sequence than the ending vertex of each edge for each edge in the graph.

Topological sorting is a linear arrangement of the vertices along each directed edge where u comes before v(where u and v are the starting and ending vertex of an edge, respectively). Topological sorting is not possible for a graph if it is not a DAG.

The above-given diagram can be considered an ideal example of a DAG.

Need for Topological Ordering🕵🏻‍♂️

Many times, vertices in a directed acyclic network might be ordered differently since they are unconnected. These various topological sortings are crucial in many situations. For instance, if there is a relative weight between the vertices that must be minimized, we must consider both their relative ordering and weight, necessitating a thorough examination of every topological ordering option.

Problem Statement👩‍🏫

For a given DAG, print all the possible topological sorts.

Example☝🏼

Sample input - 

Sample input

Sample output -

All possible Topological sorts

4 5 0 2 3 1 

4 5 2 0 3 1 

4 5 2 3 0 1 

4 5 2 3 1 0 

5 2 3 4 0 1 

5 2 3 4 1 0 

5 2 4 0 3 1 

5 2 4 3 0 1 

5 2 4 3 1 0 

5 4 0 2 3 1 

5 4 2 0 3 1 

5 4 2 3 0 1 

5 4 2 3 1 0 

Algorithm👨‍🎓

Through backtracking, we can explore every potential ordering. The algorithm steps are as follows:

 

  • Make every vertex start as unvisited.
  • Select a vertex that hasn't been visited and a zero indegree, then reduce all of those vertices' indegrees by 1 (removing edges), add that vertex to the result, and then call the recursive method once more.
  • Reset visited result and indegree values after leaving the function to allow for the enumeration of further alternatives.

Dry Run✏️

Let us consider the sample input for dry running our code-

Dry Run image 1

 

1)We select the vertices with no incoming edges, 4 or 5 in the sample input. Let us select 4 as our starting vertex and push it inside a suitable container.

Our container looks like this:[4]

2)Delete the outgoing edges, from 4.

Dry Run image 2

Select the next vertex with zero incoming edges, 5 in this case, push it inside the container and delete the outgoing edges.

Dry Run image 3

The container looks like this [4 5 ].

Similarly, repeat the following until only one vertice is left

Dry Run image 4

Container: [4 5 0]

Dry Run image 5

Container: [4 5 0 2]

Dry Run image 6

Container: [4 5 0 2 3]

Now only 1 is left with no incoming edge, hence we add it to our container.

Container: [4 5 0 2 3 1 ]

 We print the following result and then backtrack to output all the other properties.

Implementation🙎🏼

 C++

#include <bits/stdc++.h>
using namespace std;
class Graph
{
   int vertices;   /* No. of vertices
   Pointer to the array containing an adjacency list*/
   list<int> *adjc;
   /* A vector to store indegree of vertices*/
   vector<int> indeg;
   /* A function used by alltopologicalSort*/
   void alltopoSortUtil(vector<int>& result,
                               bool visited[]);
public:
   Graph(int vertices);   /*Constructor
    The function to add an edge*/
   void addEdge(int se, int ee);
   /* This function prints all Topological Sorts*/
   void alltopoSort();
};
/*Constructor of graph*/
Graph::Graph(int vertices)
{
   this->vertices = vertices;
   adjc = new list<int>[vertices];
   /* Initialise all indegree with 0*/
   for (int i = 0; i < vertices; i++)
       indeg.push_back(0);
}
/* Utility function to add edge*/
void Graph::addEdge(int se, int ee)
{
   adjc[se].push_back(ee); /* Add se to ee's list.*/
   /*increasing inner degree of w by 1*/
   indeg[ee]++;
}
/*The Main recursive function for printing all possible
 topological sorts*/
void Graph::alltopoSortUtil(vector<int>& result,
                                  bool visited[])
{
   /* For indicating whether all topological are present
    or not*/
   bool flag = false;
   for (int i = 0; i < vertices; i++)
   {
       /*If indegree is zero and not yet visited, then
         only choose that vertex*/
       if (indeg[i] == 0 && !visited[i])
       {
           /*reducing the indegree of the adjacent vertices*/
           list<int>:: iterator j;
           for (j = adjc[i].begin(); j != adjc[i].end(); j++)
               indeg[*j]--;
           /*  including in result*/
           result.push_back(i);
           visited[i] = true;
           alltopoSortUtil(result, visited);
           /* resetting visited, res and indegree for
           backtracking*/
           visited[i] = false;
           result.erase(result.end() - 1);
           for (j = adjc[i].begin(); j != adjc[i].end(); j++)
               indeg[*j]++;
           flag = true;
       }
   }
   /* We reach here if all vertices are visited.
     So we print the solution here*/
   if (!flag)
   {
       for (int i = 0; i < result.size(); i++)
           cout << result[i] << " ";
       cout << endl;
   }
}
/*The function does all Topological Sort.
 It uses recursive alltopologicalSortUtil()*/
void Graph::alltopoSort()
{
   /*Mark all the vertices as not visited*/
   bool *visited = new bool[vertices];
   for (int i = 0; i < vertices; i++)
       visited[i] = false;
   vector<int> result;
   alltopoSortUtil(result, visited);
}
/*Driver program to test the above functions*/
int main()
{
   /* Creating a graph given in the below diagram*/
   Graph A(6);
   A.addEdge(5, 2);
   A.addEdge(5, 0);
   A.addEdge(4, 0);
   A.addEdge(4, 1);
   A.addEdge(2, 3);
   A.addEdge(3, 1);
   cout << "All possible Topological sorts\n";
   A.alltopoSort();
   return 0;
}

Output-

4 5 0 2 3 1 

4 5 2 0 3 1 

4 5 2 3 0 1 

4 5 2 3 1 0 

5 2 3 4 0 1 

5 2 3 4 1 0 

5 2 4 0 3 1 

5 2 4 3 0 1 

5 2 4 3 1 0 

5 4 0 2 3 1 

5 4 2 0 3 1 

5 4 2 3 0 1 

5 4 2 3 1 0 

 Java

import java.util.*;
 
class Graph {
    int vertices; /*Number of vertices*/
 
    List<Integer> adjcListArray[];
 
    public Graph(int vertices) {
 
        this.vertices = vertices;
 
        @SuppressWarnings("unchecked")
        List<Integer> adjcListArray[] = new LinkedList[vertices];
 
        this.adjcListArray = adjcListArray;
 
        for (int i = 0; i < vertices; i++) {
            adjcListArray[i] = new LinkedList<>();
        }
    }
    /*Utility function to add edge*/
    public void addEdge(int src, int dest) {
 
        this.adjcListArray[src].add(dest);
 
    }
     
    /*Main recursive function to print all 
    topological sorts*/
    private void allTopoSortsUtil(boolean[] alreadyVis,
                        int[] indeg, ArrayList<Integer> stack) {
        /*for indicating whether all topological are found*/
        boolean redflag = false;
 
        for (int i = 0; i < this.vertices; i++) {
            /* If indegree is 0 and not yet visited then
             only choose that vertex*/
            if (!alreadyVis[i] && indeg[i] == 0) {
                 
                /*including in result*/
                alreadyVis[i] = true;
                stack.add(i);
                for (int adjacent : this.adjcListArray[i]) {
                    indeg[adjacent]--;
                }
                allTopoSortsUtil(alreadyVis, indeg, stack);
                 
                /*resetting already visited, result and indegree for
                 backtracking*/
                alreadyVis[i] = false;
                stack.remove(stack.size() - 1);
                for (int adjacent : this.adjcListArray[i]) {
                    indeg[adjacent]++;
                }
 
                redflag = true;
            }
        }
        /* We reach here if all vertices are already visited.
         So we print the solution here*/
        if (!redflag) {
            stack.forEach(i -> System.out.print(i + " "));
            System.out.println();
        }
 
    }
     
    /*Function does all Topological Sort.
     It uses recursive alltopologicalSortUtil()*/
    public void allTopoSorts() {
        /*Mark all the vertices as not already visited*/
        boolean[] alreadyVis = new boolean[this.vertices];
 
        int[] indeg = new int[this.vertices];
 
        for (int i = 0; i < this.vertices; i++) {
 
            for (int var : this.adjcListArray[i]) {
                indeg[var]++;
            }
        }
 
        ArrayList<Integer> stack = new ArrayList<>();
 
        allTopoSortsUtil(alreadyVis, indeg, stack);
    }
     
    /* The Driver code*/
    public static void main(String[] args) {
 
        /*Creating the graph given in the diagram*/
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
 
        System.out.println("All Topological sorts");
        graph.allTopoSorts();
    }
}

Output-

4 5 0 2 3 1 

4 5 2 0 3 1 

4 5 2 3 0 1 

4 5 2 3 1 0 

5 2 3 4 0 1 

5 2 3 4 1 0 

5 2 4 0 3 1 

5 2 4 3 0 1 

5 2 4 3 1 0 

5 4 0 2 3 1 

5 4 2 0 3 1 

5 4 2 3 0 1 

5 4 2 3 1 0 

Python

class Graph:
    # Constructor
    def __init__(self, all_edges, N):
 
        # A List of Lists to represent an adjacency list
        self.adjcList = [[] for _ in range(N)]
 
        # stores in-degree of a vertex
        # initialize in-degree of each vertex by 0
        self.indegree = [0] * N
 
        # add all_edges to the undirected graph
        for (src, dest) in all_edges:
 
            # add an edge from source to destination
            self.adjcList[src].append(dest)
 
            # increment in-degree of destination vertex by 1
            self.indegree[dest] = self.indegree[dest] + 1
 
 
# Recursive function to find
# all topological orderings of a given DAG
def findAllTopo(graph, path, disc, N):
 
    # do for every vertex
    for v in range(N):
 
        # proceed only if in-degree of current node is 0 and
        # current node is not processed yet
        if graph.indegree[v] == 0 and not disc[v]:
 
            # for every adjacent vertex u of v,
            # reduce in-degree of u by 1
            for u in graph.adjcList[v]:
                graph.indegree[u] = graph.indegree[u] - 1
 
            # include current node in the path
            # and mark it as disc
            path.append(v)
            disc[v] = True
 
            # recur
            findAllTopo(graph, path, disc, N)
 
            # backtrack: reset in-degree
            # information for the current node
            for u in graph.adjcList[v]:
                graph.indegree[u] = graph.indegree[u] + 1
 
            # backtrack: remove current node from the path and
            # mark it as undisc
            path.pop()
            disc[v] = False
 
    # print the topological order if
    # all vertices are included in the path
    if len(path) == N:
        print(path)
 
 
# Print all topological orderings of a given DAG
def printAllTopo(graph):
 
    # get number of nodes in the graph
    N = len(graph.adjcList)
 
    # create an auxiliary space to keep track of whether vertex is discovered
    disc = [False] * N
 
    # list to store the topological order
    path = []
 
    # find all topological ordering and print them
    findAllTopo(graph, path, disc, N)
 
# Driver code
if __name__ == '__main__':
 
    # List of graph all_edges as per above diagram
    all_edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
 
    print("All Topological sorts")
 
    # Number of nodes in the graph
    N = 6
 
    # create a graph from all_edges
    graph = Graph(all_edges, N)
 
    # print all topological ordering of the graph
    printAllTopo(graph)

Output-

4 5 0 2 3 1 

4 5 2 0 3 1 

4 5 2 3 0 1 

4 5 2 3 1 0 

5 2 3 4 0 1 

5 2 3 4 1 0 

5 2 4 0 3 1 

5 2 4 3 0 1 

5 2 4 3 1 0 

5 4 0 2 3 1 

5 4 2 0 3 1 

5 4 2 3 0 1 

5 4 2 3 1 0 

Time Complexity: The algorithm mentioned above is just DFS Algorithm with an additional stack. Therefore, the time complexity is equal to DFS, which is-

O(V+E), where V and E are vertices and edges, respectively.

Space Complexity: Since the stack needs space, the space complexity is O(V).

We hope you understood everything about topological sorting in a graph.🤗

Refer to know about :  Topological sort

Frequently Asked Questions

What is a graph?

A graph is a famous data structure comprising a limited number of nodes (also known as vertices) and a limited number of connected edges. An edge is a pair (x,y) that indicates that the x vertex is connected to the y vertex.

What are some ways of representing a graph?  

Edge lists, adjacency matrices, and adjacency lists are some ways we can represent a graph.

Explain DFS in a graph data structure.

An algorithm for navigating or searching through tree or graph data structures is called depth-first search. The algorithm begins at an arbitrarily selected root node and proceeds to investigate each branch as possible before turning around.

Explain BFS in a graph data structure.

When a dead end occurs during any iteration, the Breadth First Search (BFS) method employs a queue to track where to retrieve the next vertex to begin a search.

What are some real-world problems where graphs are utilized?

Data structures called graphs are used to solve problems in the real world by simulating the problem area as a network, similar to social networks, telephone networks, and circuit networks.

Conclusion

This article taught us how to find all topological sorts of a directed acyclic graph to remain a directed acyclic graph. We began with a brief introduction to the graphs, followed by an algorithm and detailed code example. After reading about all topological sorts of a directed acyclic graph, refer to Learn Graphs 1Introduction to GraphsLearn Graphs 2, and Advanced Graphs for CP or a deeper understanding of graphs.

Recommended Problems - 


Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Previous article
Topological Sort of a Graph Using Departure Time of Vertex
Next article
Find Maximum Shortest Distance in Each Component of a Graph
Live masterclass