# Topological Sorting Using modified DFS

*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/.*

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

*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

## Leave a Reply