Question 3 (11 marks)
Consider the following undirected graph, which has three connected components ({0,1,2,3} and {4,5,6} and {7,8}):
In the q3 directory is a simple Graph ADT and a small driver which reads a graph, prints information about the graph, and then computes and prints the number of connected components. To get a better idea of how this program is supposed to work, look at the testing examples in the q3/tests directory. Note that 5.in corresponds to the above graph.
The nComponents() function, which computes the number of connected components, is incomplete. Your task for this question is to complete the nComponents() function in the file Graph.c. You may introduce any global variables or extra functions that you think are necessary, but you must maintain the current nComponents() interface. Your functions must release any memory that they allocate once it is no longer needed (i.e. no memory leaks).
Hint: a reminder of the overall strategy for solving this problem:
CountComponents:
initialise global ComponentOf[] array to all unassigned
while (not all vertices have been assigned to a component) {
find an unassigned vertex V
count a new component
do a depth first search of the graph starting from V
}
DepthFirstSearch:
assign current vertex to component
for each unassigned neighbour N of current vertex
do a depth first search of the graph on N
Once you are satisfied with your program, submit it using the command:
submit q3
This will make a copy of the Graph.c file from the q3 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that your final submission compiles without any errors or warnings. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using inputs which are different to the examples in the q3/tests directory.
If, at some stage, you need to "re-install" the files (although you should not need to), you can copy all of the original files into the q3 directory by running the command:
re-start q3
Beware: this will overwrite all of your existing files for this question, so only do it if you seriously mess things up.