Do you think IIT Guwahati certified course can help you in your career?
Introduction🧑🏻🎓
A graph is any non-linear Data Structuremade 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).
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.
Directed Acyclic Graph (DAG)🤔
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.
A 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 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-
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.
Select the next vertex with zero incoming edges, 5 in this case, push it inside the container and delete the outgoing edges.
The container looks like this [4 5 ].
Similarly, repeat the following until only one vertice is left
Container: [4 5 0]
Container: [4 5 0 2]
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;
}
You can also try this code with Online C++ Compiler
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();
}
}
You can also try this code with Online Java Compiler
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)
You can also try this code with Online Python Compiler
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.🤗
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 1, Introduction to Graphs, Learn Graphs 2, and Advanced Graphs for CP or a deeper understanding of graphs.
84+ registered