A topological sort of a directed acyclic graph (in short DAG) is a linear ordering of vertices such that if DAG contains a directed edge (u,v), then u appears always before v in the ordering. In article posted at http://wikistack.com/topological-sorting/ , we have discussed Kahn’s algorithm for topological sorting. The topological sorting can be done by modifying recursive version of depth first search algorithm. For more details about recursive depth first approach follow the link http://wikistack.com/a-recursive-implementation-of-dfs/.

Topological Sorting Using modified DFS

For example one of  possible topological sorting of above directed acyclic graph is 4 0 1 2 3 5 .

Topological Sorting Using modified DFS

Modifying DFS for topological sorting

Let us look at original DFS approach.
1. void DFS(graph,vertex):
2.  mark v as visited
4.      print v
5 .    for all edges from v to u in graph.adjacentEdges(v) do
6.         if vertex u is not visited then
7.            call DFS(graph,u)

Instead of printing v at 4, append the vertex v in a list L, when v finished 

 void DFS(graph,vertex):
2      mark v as visited
4      //print v
5      for all edges from v to u in graph.adjacentEdges(v) do
6          if vertex u is not visited then
7              call DFS(graph,u)
8          appendVinList(v)
After the DFS traversal of graph, Print the list in reverse order.

Here is sample implementation in c++ for topological sorting of above graph.

#include<iostream>
#include<stdio.h>
#include <cstdlib>
#include <cstring>
using namespace std;
int count = 0;
int order[6];

void dfs (int u, bool visited[], bool graph[][6])
{

visited[u] = true;
for (int v = 0; v < 6; v++)
if (!visited[v] && graph[u][v])
dfs (v, visited, graph);

order[count++] = u;
}

int main ()
{
bool visited[6];
memset(visited,false,sizeof(visited));

//0 1 2 3 4 5
bool graph[6][6] = {{0, 1, 1, 0, 0, 0}, //0
{0, 0, 1, 1, 0, 0}, //1
{0, 0, 0, 1, 0, 0}, //2
{0, 0, 0, 0, 0, 1}, //3
{0, 0, 1, 0, 0, 0}, //4
{0, 0, 0, 0, 0, 0}};//5

for (int v = 0; v < 6; v++)
if (!visited[v])
dfs (v, visited, graph);

// print topological order
for (int v = 0; v < 6; v++)
cout << order[5 - v] << " ";

cout<<endl;

return 0;
}

OutPut:
4 0 1 2 3 5



Related Contents to follow