## Topological sort:

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.For example, in following Directed graph , the first black vertex or in which vertex DFS find finish time should place in the last of the output. Here , DFS start traverse from Shirt, but first finished time is jacket . So it goes to the last position of stack or link list.

Topological sort |

#### Here is the algorithm of Topological sort:

TOPOLOGICAL-SORT(V, E)

1.Call DFS(V, E) to compute finishing times f[v] for each vertex v

2.When each vertex is finished, insert it onto the front of a linked list

3.Return the linked list of vertices

Running time: Q(V + E)

#### Here is the Code of Topological sort of directed graph in java :

Happy Coding...

## Post a Comment