Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction⭕
2.
What is a Graph?🤷‍♀️
3.
Some Basic Terminologies‼
3.1.
Cyclic Graph⭕
3.2.
Acyclic Graph⭕
3.3.
Directed Graph⭕
3.4.
Undirected Graph⭕
3.5.
Directed Acyclic Graph⭕
4.
Topological Sorting in a Graph✔
5.
Algorithm to find Topological Sort of a DAG✍
6.
Code for Topological Sort in Graph in C++💻
6.1.
Sample Input
6.2.
Output
7.
Code for Topological Sort in Graph in Java💻
7.1.
Sample Input
7.2.
Sample Output
8.
Code for Topological Sorting in Graph in Python💻
8.1.
Sample Input
8.2.
Output
9.
Complexity Analysis🎯
10.
Applications of Topological Sort📃
11.
Frequently Asked Questions
11.1.
Is topological sort done only by DFS?
11.2.
What is the most common application of topological sorting in a graph?
11.3.
What is the time complexity for topological sorting in a graph using BFS?
11.4.
What category of algorithms does topological sort belong to?
11.5.
Does topological sort work when there are negative weights in a graph?
12.
Conclusion
Last Updated: Mar 27, 2024
Medium

Topological Sorting in a Graph

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

Introduction

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.

topological sort

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.

Read also Application of graph data structure

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

Some Basic Terminologies‼

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.

cyclic

Acyclic Graph

Graphs that do not contain any cycle are known as acyclic graphs.

acyclic graph

Directed Graph

A directed graph is a graph in which the edges have a particular direction.

directed graph

Undirected Graph

Graphs whose edges do not have any particular direction or are bidirectional are known as undirected graphs.

undirected graph

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-

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

algorithm

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-

example graph

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;
}

Sample Input

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);

Output

output1

Code for Topological Sort in Graph in Java💻

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();
    }
}

Sample Input

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

output2

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()

Sample Input

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);

Output

output python

Complexity Analysis🎯

Time Complexity

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. 

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.

Recommended Problems - 


You can refer to other similar articles as well

Happy learning Ninja!! 🥷

Previous article
Transitive Closure Of a Graph Using Recursion
Next article
Single Source Shortest Path
Live masterclass