Description
This exercise is to be done before or during your week 11 laboratory class. When you complete the
exercise show your work to your lab tutor to have your work marked. The marking is based mainly
on correct implementation and code readability. You should implement your code in one file (e.g.
ex6.cpp, ex6.c, ex6.java). Make sure your program has a header comment block containing the name
of the exercise, your name and your student login (e.g. jfk01). You may implement your solution in C,
C++, Java or Python.
For this exercise, you are to implement the breadth first search algorithm.
As usual, your program will prompt for the name of an input file and the read and process the data
contained in this file.
The file contains the following data:
A single integer representing the number of vertices in the graph, N.
A number of pairs of integers. Each pair represents the two vertices at each end of an edge
in the graph.
Note: The graph is undirected. The nodes are numbered from 0 to N‐1.
Your program should traverse the graph breadth‐first, starting at node 0 and output all of the nodes
reachable from this node. Your output should consist of the spanning tree obtained from the
algorithm. It should be printed as an ordered list of the edges in the tree. The vertices in each edge
should be listed in the order of traversal.
E.g. for the following input:
4
0 2
2 3
1 3
0 3
Your output should be
0 2
0 3
3 1
When you are finished, test your program using the provided text file named “Ex7.txt” and show
your code and the output to your lab tutor to receive your mark.
