In this assignment, you will implement Breadth First Search (BFS). The input to your program is a graph in the adjacency list format.
Your program must initiate a BFS from vertex 2 of the graph. If the graph is connected, the program must output a spanning tree starting at vertex 2. If the graph is disconnected, your program must output "Graph is not connected". Your program should read from an input file: data2.txt and write to the output file: out2.txt.
Please follow all instructions for Assignment 1 for submission of your source file and readme file via canvas (note that the programs must run on CSE machines). You can choose any reasonable output format for your program. (This needs to be explained in your readme file.)
Your program should be written in C or C++. You can use STL for a queue but not for a graph.
Input Example
1 3 4
2 4
3 1 4
4 2 1 3
1 2 4
2 1 3
3 2 4
4 1 3
1 2
2 1
3 4
4 3