Topological sort without Kahn’s algorithm

Malay Gain
Last Updated: May 16, 2022
Difficulty Level :
EASY

Introduction

Topological sorting is a linear ordering of vertices of a directed acyclic graph. If there is an edge from vertex u to vertex v, u will appear before v in that ordering.

 

Let’s visualize this ordering through an example.

 

 

 

Topological sorting of the above graph is 15,14,12,13,11,10. But this is not the only one. There can be multiple such topological sorts of the same graph.

 

Algorithm

In this algorithm, we use DFS(depth-first search) for topological sort. But we implement it using a modified version of the standard DFS algorithm. Instead of printing the node just after visiting, we store it in a temporary stack after visiting all of its adjacent nodes recursively.

 

  • Call the DFS for all of the nodes of the graph.

 

  • DFS will mark a node as visited and recursively call itself for its adjacent nodes and push them into a temporary stack. So, a node is pushed into the stack only after its adjacent nodes are pushed.

 

  • When there is no node left unvisited(i.e., all are visited), we will print the content of the stack in order after popping.

 

This ordering will be the required topological sort of the graph. As we push one node after its adjacent nodes are pushed, the node will appear before its adjacent nodes in that ordering.

 

Code

 

// C++ program  for Topological Sort


#include<bits/stdc++.h>
using namespace std;

// Class to represent a graph
class Graph {
// no. of nodes
int n;

// pointer to an array containing adjacency list representation of the graph
vector<int>* adj;

//DFS used for Topological Sort
void topoDFS(int v, bool visited[],stack<int>& Stack);

public:
// Constructor
Graph(int n);

// function to add an edge to the graph
void addEdge(int u, int v);

// function to Topological Sort
void topologicalSort();
};

Graph::Graph(int n)
{
this->n = n;
adj = new vector<int>[n]; //allocating memory for adjacency list
}

void Graph::addEdge(int u, int v)
{
// adding an edge from u to v
adj[u].push_back(v);
}

// DFS used by topologicalSort
void Graph::topoDFS(int v, bool visited[],stack<int>& Stack)
{
// mark the current node as visited.
visited[v] = true;


// recursively calls  itself for its adjacent nodes 
//and push them into a temporary stack

    for( auto child:adj[v])
    {
     if(!visited[child])
     {
     topoDFS(child,visited,Stack);
}
}

// push current node into the stack

Stack.push(v);
}


//actual function to print Topological Sort
void Graph::topologicalSort()
{
stack<int> Stack;

// mark all the vertices as not visited
bool* visited = new bool[n];
for (int i = 0; i < n; i++)
visited[i] = false;

//Call the DFS for all of the nodes of the graph if it is not visited
for (int i = 0; i < n; i++)
if (visited[i] == false)
topoDFS(i, visited, Stack);

// printing  contents of stack after popping
while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
}

// Driver Code
int main()
{
// creating a graph with 6 nodes
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

cout << "Topological Sort of the given graph :\n";

// Function Call
g.topologicalSort();

return 0;
}

Output

Topological Sort of the given graph :
5 4 2 3 1 0

Complexity Analysis

  • Time Complexity: In this algorithm, we have only used DFS. So,  its complexity is the same as DFS, O (n+e), where n is the number of vertices and e is the number of edges in the graph.

 

  • Space Complexity: Here, an extra stack of size n is used to maintain the topological ordering of the vertices, and in the worst-case recursion, stack size can become n.So, space complexity is O(n)+O(n) i.e, O(n).

 

This video gives a detailed tutorial on the “Topological Sort Algorithm”, so you can watch this video to understand it better.

FAQs

  1. What is Topological Sort?
    It is a linear ordering of vertices of a directed acyclic graph, such that if there is an edge from vertex u to vertex v, u will appear before v in that ordering.
     
  2. What is the application of Topological Sort?
    (i)Scheduling jobs according to given dependencies among the jobs.
    (ii)Resolving symbol and data serialization in linkers.
    (iii)Detecting cycle in a graph.
    (iv)Topological Sort detects deadlock in the operating system.
     
  3. What is the main difference between the above algorithm and Khan’s Algorithm?
    The main difference between the above algorithm and Khan’s Algorithm is for the above algorithm, we have used DFS(depth-first search), but  Khan’s Algorithm is implemented using the BFS(breadth-first search) algorithm.
     
  4. What is an acyclic graph?
    If there is no cycle present in a graph, the graph is classified as an acyclic graph.
     
  5. What is a directed graph?
    If directed edges connect vertices of a graph, the graph is said to be directed graph or digraph.

 

Key Takeaways

This article discussed the concept of Topological sort, implementation of  Topological sort on an acyclic directed graph. The blog also tried to provide a better understanding of the time complexity for such sorting on a graph.

 

To learn more, head over right now to CodeStudio to practice important graph-related problems and crack your interviews like a Ninja!

 

 

Happy learning!

 

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think