Exercise 7 – Breadth First Search

Exercise 7 – Breadth First Search
Due by the end of your Week‐11 laboratory class. (2 marks)
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. Your program should
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.
$ submit -u login -c CSCI203 –a ex7 filename
where ‘login' is your UNIX login ID and ‘filename’ is the name of your file.
If you are unable to attend your lab class and demonstrate your work on time due to circumstances
beyond your control (e.g. sickness), contact your lecturer to request an extension.