## 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 the 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 the 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