This blog will cover the basics of graphs and will mainly focus on what is topological Sorting in a graph. The necessary conditions for this sorting and everything revolving around it.
Let us walk over the concept of topological sorting in a graph.
What is a Graph?🤷♀️
A graph is a non-linear Data Structure comprising two non-empty sets, vertices, and edges.
The vertices are connected through edges. We use graphs to store hierarchical information, typically any information that is of non-linear form.
Before diving deep into the topic of topological sorting, we must know some terminologies that we will use to define topological sorting in a graph.
Cyclic Graph⭕
As the name suggests, cyclic graphs are simply those graphs that contain a cycle.
Acyclic Graph⭕
Graphs that do not contain any cycle are known as acyclic graphs.
Directed Graph⭕
A directed graph is a graph in which the edges have a particular direction.
Undirected Graph⭕
Graphs whose edges do not have any particular direction or are bidirectional are known as undirected graphs.
Directed Acyclic Graph⭕
A directed acyclic graph (DAG) is a graph consisting of vertices and edges such that the edges of the graph have direction, and if we traverse any of the paths in the direction of these edges, we would never end up in a loop.
Below is an example of a DAG-
In this graph, whichever path we may traverse using these directed edges, we will never get a loop.
Topological Sorting in a Graph✔
Topological sort is only possible when the graph is DAG( Directed Acyclic Graph).
Topological Sorting is a linear ordering of the vertices of a DAG such that for every vertex from a to b, a appears before b in the linear sequence. The topological sort of graph need not be unique. Another essential point to note is that the first vertex in the linear ordering always has an in-degree of 0.
Note-The topological sorting in a graph is not valid for cyclic graphs.
Algorithm to find Topological Sort of a DAG✍
There can be multiple approaches to find the topological sort of a graph. We will discuss one such simple approach here-
1️⃣Calculate the in-degree of every vertex.
2️⃣Start from the vertex having an in-degree of 0.
3️⃣Write that vertex in the answer.
4️⃣Remove that vertex and all the outgoing edges from it.
5️⃣Repeat steps 2-4 till all vertices are covered.
A situation of no node existing with in-degree 0 can occur in two cases-
1️⃣We have covered all the vertices (which will produce a valid topological ordering)
2️⃣Graph has a cycle (which will produce an invalid topological ordering)
We can also use the DFS Algorithm (Depth First Traversal) technique to find the topological sorting of a given DAG. While using the DFS approach we will maintain a temporary stack.
In this approach, we take a vertex specifically with an in-degree of 0 and call topological sorting recursively for all its adjacent vertices.
Once this is done, only then we push the vertex in the stack. That means a vertex will be pushed into the stack only when all of its adjacent vertices have been added to the stack.
We then finally print the contents of the stack to find the topological sorting in a graph.
The graph taken in the examples is as follows-
Code for Topological Sort in Graph in C++💻
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
/*No. of vertices*/
int V;
/*adjacency list of the graph*/
list<int>* adjacency;
void topologicalSortmain(int v, bool visitedarr[],
stack<int>& Stack);
public:
Graph(int V);
/*adds an edge to the graph*/
void add(int v, int w);
/*gives us the topological sort of the graph*/
void topologicalSort();
};
Graph::Graph(int V) /*making the graph*/
{
this->V = V;
adjacency = new list<int>[V];
}
void Graph::add(int v, int w)
{
adjacency[v].push_back(w);
}
/*function used by topological sort*/
void Graph::topologicalSortmain(int vertex, bool visitedarr[],
stack<int>& Stack)
{ /*we maintain a visited array for the vertices
whichever node we are at, we will mark that as visited*/
visitedarr[vertex] = true;
/*check for all vertices adjacent to this vertex*/
list<int>::iterator k;
for (k = adjacency[vertex].begin(); k != adjacency[vertex].end(); ++k)
if (!visitedarr[*k])
topologicalSortmain(*k, visitedarr, Stack);
/*after reaching to this point,
push the current vertex to stack*/
Stack.push(vertex);
}
void Graph::topologicalSort()
{
stack<int> Stack;
/*initially mark all vertices as unvisited*/
bool* visitedarr = new bool[V];
for (int i = 0; i < V; i++)
visitedarr[i] = false;
for (int i = 0; i < V; i++)
if (visitedarr[i] == false)
topologicalSortmain(i, visitedarr, Stack);
/*print stack contents*/
while (!Stack.empty()) {
cout << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
// Create a graph given in the above diagram
Graph g(6);
g.add(2, 1);
g.add(2, 0);
g.add(4, 0);
g.add(4, 5);
g.add(1, 3);
g.add(3, 5);
cout << "Topological sort of graph is\n";
g.topologicalSort();
return 0;
}
You can also try this code with Online C++ Compiler
import java.io.*;
import java.util.*;
/*directed graph using adjacency list */
class graph_ts {
/*vertices are represented as V */
private int V;
private ArrayList<ArrayList<Integer> > adj;
graph_ts(int v1)
{
V = v1;
adj = new ArrayList<ArrayList<Integer> >(v1);
for (int i = 0; i < v1; ++i)
adj.add(new ArrayList<Integer>());
}
/*adds an edge to the graph */
void add(int v1, int vertex) { adj.get(v1).add(vertex); }
//function used by topologicalSort
void topologicalSortmain(int v1, boolean visited[],
Stack<Integer> stack)
{
//we will mark the current node visited
visited[v1] = true;
Integer i;
/*we will repeat this for all the adjacent vertices*/
Iterator<Integer> j = adj.get(v1).iterator();
while (j.hasNext()) {
i = j.next();
if (!visited[i])
topologicalSortmain(i, visited, stack);
}
/*we will push the current vertex to the stack */
stack.push(Integer.valueOf(v1));
}
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();
/*initially all vertices are unvisited */
boolean visitedarr[] = new boolean[V];
for (int i = 0; i < V; i++)
visitedarr[i] = false;
for (int i = 0; i < V; i++)
if (visitedarr[i] == false)
topologicalSortmain(i, visitedarr, stack);
/*printing elements in the stack */
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[])
{
graph_ts g = new graph_ts(6);
g.add(5, 2);
g.add(5, 0);
g.add(4, 0);
g.add(4, 1);
g.add(2, 3);
g.add(3, 1);
System.out.println("Topological Sort of the graph is: ");
g.topologicalSort();
}
}
You can also try this code with Online Java Compiler
graph_ts g = new graph_ts(6);
g.add(5, 2);
g.add(5, 0);
g.add(4, 0);
g.add(4, 1);
g.add(2, 3);
g.add(3, 1);
Sample Output
Code for Topological Sorting in Graph in Python💻
from collections import defaultdict
#make a class for graph
class Graph:
def __init__(self, totalvertices):
self.g = defaultdict(list) #adjacency List
self.V = totalvertices # Total No. of vertices in graph
#add edge to graph
def add(self, u, vertex):
self.g[u].append(vertex)
def topologicalSortmain(self, vertex, visitedarr, stack):
#we will mark the current vertex as visited
visitedarr[vertex] = True
# for all adjacent vertices of current vertex
for k in self.g[vertex]:
if visitedarr[k] == False:
self.topologicalSortmain(k, visitedarr, stack)
#pushing result to stack
stack.append(vertex)
def topologicalSort(self):
#initially all vertices are unvisited
visitedarr = [False]*self.V
stack = []
for k in range(self.V):
if visitedarr[k] == False:
self.topologicalSortmain(k, visitedarr, stack)
# Print contents of the stack
print(stack[::-1])
g = Graph(6)
g.add(2, 1);
g.add(2, 0);
g.add(4, 0);
g.add(4, 5);
g.add(1, 3);
g.add(3, 5);
print ("Topological Sort of the given graph is :")
g.topologicalSort()
You can also try this code with Online Python Compiler
The time complexity of any algorithm gives us an idea about the execution time of the algorithm as a function of n, where n is the number of inputs.
The time complexity of this solution is that of the time complexity of DFS.
Time complexity- O(V+E)
Space Complexity
Space complexity is the total amount of extra space taken by the algorithm as a function of n.
Since we are using a temporary stack (for DFS) extra space will be used.
Hence, space complexity is O(V)
Applications of Topological Sort📃
After learning the concept of the topological sort, let us now ponder upon why we should really know about the topological sort.
📌We use topological sort for sentence ordering.
📌We use this for critical path analysis.
📌The topological sort is used for data serialization.
📌It is also used for the detection of deadlock in the operating system.
Frequently Asked Questions
Is topological sort done only by DFS?
We can also use the BFS(Breadth First Search) technique for finding the topological sort of a DAG.
What is the most common application of topological sorting in a graph?
The topological sort is mainly used to find cycles in a graph.
What is the time complexity for topological sorting in a graph using BFS?
The time and space complexity for both BFS and DFS techniques are the same i.e O(V+E) time complexity and O(V) space complexity.
What category of algorithms does topological sort belong to?
The topological sort belongs to greedy algorithms.
Does topological sort work when there are negative weights in a graph?
Yes, the topological sort works even when the negative weighted edges are present.
Conclusion
In this blog, we discussed the topological sort, its conditions, and examples. We have also learned about the basic terminologies required to get started for working on a topological sort of graph.