Graph problems

BFS(G)
Breadth First search, will give the shortest path from the root, assuming all the edges are of same weight. You need additional datastructure like queue to implement it.

DFS(G)
Depth First Search, calculates the discovery and finished time of each node. These will help in classifying the edges into forward or tree, backward, cross edge.
The finishing time can be used in many ways.

Topological Sort
Do a DFS of the graph, now sort the nodes based on their dicreasing order of their finishing times. This will yield you the topologically sorted graph.

DFS of a graph is very useful tool. Refer to algorithms

Leave a Reply

Your email address will not be published. Required fields are marked *