Topological Sort in C++

In this tutorial, we will learn about topological sort and its implementation in C++. Before that let’s first understand what is directed acyclic graph.

Directed Acyclic Graph (DAG): is a directed graph that doesn’t contain cycles. This means it is impossible to traverse the entire graph starting from one edge.

Topological Sorting: is a linear ordering of vertices such that for every directed edge A->B, vertex A comes before B in the ordering. This sorting can be implemented on the Directed Acyclic Graph (DAG). A graph can have more than one valid topological ordering of vertices.




Example: 

Topological Sort in C++

In the above graph, as there is an edge between vertex ‘0’ and vertex ‘1’. Vertex ‘0’ will come before vertex ‘1’. Likewise, vertex ‘0’ will come before vertex ‘2’, vertex ‘1’ will come before vertex ‘2’, vertex ‘1’ will come before vertex ‘3’, vertex ‘2’ will come before vertex ‘3’.

Considering all the above conditions, the resultant topological order will be: 0 -> 1 -> 2 -> 3.

(*Note: It is possible to have more than one topological sorting for a graph.)

Program to implement Topological Sort in C++

#include<iostream> 
#include<stack>
#include<list>  
using namespace std; 
  
class graph
{ 
    int no_of_vertices;
    list<int>* l1;  
  
  public:
    graph(int n) 
  { 
    	no_of_vertices=n; 
    	l1=new list<int>[n]; 
  } 
  
  	/* push_back function is used to add new element at the end of the list container */
    void add_edge(int x, int y)
  {
     l1[x].push_back(y);
  } 
  void topological(int, int [], stack<int>& );
    void topological_sort(); 
}; 
  
void graph::topological(int vertex_no, int visited[], stack<int>& s) 
{ 
  /* Marking vertex visited */
    visited[vertex_no]=1; 
  
  	/* we cannot iterate through list using normal integer. Hence we use iterator */
    list<int>::iterator i; 
    for (i = l1[vertex_no].begin(); i != l1[vertex_no].end(); i++)
  { 
        if (visited[*i]==0)
    { 
            topological(*i,visited,s);
    }
  }
  
    /* push current vertex on stack */
    s.push(vertex_no); 
} 
  
void graph::topological_sort() 
{ 
    stack<int> s; 
    int i,visited[no_of_vertices];
    
  /* '0' means not visited and '1' means visited. here, we are marking all the vertices not-visited */ 
    for (i=0; i<no_of_vertices;i++)
  {
    visited[i]=0; 
  } 

  /* calling topological for each vertex */
    for (i=0; i<no_of_vertices;i++)
  {
    if (visited[i]==0)
    {
      topological(i,visited,s); 
    } 
  } 
  
  /* display stack content */
    while(!s.empty()) 
  {
    int k=s.top(); 
        cout<<k<<" "; 
        s.pop(); 
    } 
} 
  
int main() 
{ 
    graph p(4);	// 4: no of vertices
    p.add_edge(0, 1); 
    p.add_edge(0, 2); 
    p.add_edge(1, 2); 
    p.add_edge(1, 3); 
    p.add_edge(2, 3); 
    /* This graph is shown in above figure */ 
  
    cout <<"\nTopological order of the vertices of the graph: "; 
    p.topological_sort(); 
  
    return 0; 
}

Output:

Topological order of the vertices of the graph: 0 1 2 3

Time Complexity

O(V+E), where V is no. of vertices and E is no. of edges in the graph.

 

You may also read:

  1. Kruskal’s algorithm in C++
  2. How to create a CSV file in C++

 


Leave a Reply

Your email address will not be published. Required fields are marked *