Topological sorting in Graph data structure

Topological sorting in directed graph is linear ordering of vertices, such that for every directed edge from u to v, vertex u will come before vertex v.

Applications

1. Executing task based on dependency, like our build system.
2. Scheduling tasks.

Topological sort will only work on directed acyclic graphs.

Algorithm

1. Pick one vertex, mark it visited and look for its adjacent vertices.
2. Push just found adjacent vertex into the main stack, and then look for its adjacent vertices  ( DFS of graph ).
3. Once no more adjacent vertex is found for the current vertex, pop it out from the main stack and push it into another stack (result stack).
4. Now, pick other vertex which is not visited yet and repeat steps 1, 2 and 3.

Consider this example

Let's say you are given 6 vertices with 6 edges :-
5, 0, 5, 2, 2, 3, 3, 1, 4, 1, 4, 0

These are 6 pairs, where integer u,v represents edge from u to v.

Topological order for the same will be 5, 4, 2, 3, 1, 0

Remember, there can be multiple topological sort order of a graph.

We will use Dictionary ( HashMap ) to store adjacent vertices and boolean array to keep track of visited vertices.

To find adjacent vertices of any given vertex.

Perform toplogical sort. You can then pop out resultStack values, to get topological sort order.

Closures in Javascript

Depth First Search in Graph

DFS involves following a path from source vertex to adjacent vertices until there are no other vertex is left to visit.

Objective

• Start with source vertex, push it into stack, mark it visited and display it
• Now peek the stack and look for adjacent vertices.
• If found push it into stack, mark it visited and display it.
• If not, then pop up from stack and again repeat step 2.
• Repeat till stack is empty.

Basics of Graph data structure

• Graph consist of vertices and edges.
• They are used to model many realworld examples ( likes cities, network…)

Graph

Implementing a graph with 4 vertices (A,B,C,D) and 4 edges.