Question 9 (6 marks)
Consider the following weighted, undirected graph:
Answer the following questions using this graph:
Show the order in which vertices would be visited if we carried out a breadth-first search
- starting from vertex a
- visiting all vertices once
- selecting neighbours based on descending vertex order
(i.e. using reverse alphabetical order (highest to lowest)) - ignoring weights
Show the order in which vertices would be visited if we carried out a breadth-first search
- starting from vertex a
- visiting all vertices once
- selecting neighbours in edge-weight order
(i.e. using lowest-to-highest costs on the edges)
Show your working by giving the intermediate states of the vertex queue and "visited" set in both cases.
Bonus question (1 mark) (the mark is in addition to the full 65 marks available for the rest of the exam)
What is the name of the former CSE Professor who was renowned for teaching his Operating Systems course using the Unix source code?
Type the answer to this question into the file called q9.txt and submit it using the command:
submit q9