The objective of this assignment is to implement Breadth First Search (BFS) to solve single-source shortest path problem on directed graphs and to implement Depth First Search (DFS) to do topological sorting of a Directed Acyclic Graph (DAG).
Inputs
Your program should accept an input file and an integer as command-line arguments. A typical execution of your program will be ./a.out sample.graph 25
The input file represents a directed graph. Every node (vertex) in the graph is uniquely labelled with a non-negative integer. Every line in the input file is of the form x y, which represents a directed edge from node x to node y. No directed edge is repeated in the input file. Since topological sorting makes sense only for DAGs, it is guaranteed that the input graph is a DAG.
The second command-line argument is an integer, which represents the label of a vertex in the given graph, which is the source from which the shortest distance of every vertex has to be calculated using BFS. Note that this argument is irrelevant for doing topological sorting and can be ignored for the same.
Your program may create an adjacency list of the input graph which can be used for both Task 1 and Task 2.
Task 1
Implement BFS and use it to find the shortest distance of every vertex from the source vertex (second command-line argument). The output file should be named as ‘sd.txt’. Every line in the output file should be of the form <vertex-label <shortest-distance-from-source. For example, if the shortest distance of vertex with label 35 from the source vertex is 10, then there is a line in the output file which has ‘35 10’. The vertex-distance pair in the output file can be ordered in any fashion. If there is no directed path from the source to a vertex, then the corresponding distance should be denoted by -1.
Task 2
Implement DFS and use it to do a topological sorting of the input DAG. The output file should be named as ‘ts.txt’. The output file must contain the vertices - one vertex per line - which represents a topological sorting of the input DAG.
