Topological sort without Kahn’s algorithm

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

You can also try this code with Online C++ Compiler

Run Code

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.

Refer to know about :  Topological sort

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.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

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

Happy learning!