Week 08 Tutorial Questions

Graphs (ii)

In the following graph:
1. Which vertices are reachable from vertex 0?
2. Which vertices are reachable from vertex 1?
3. Which vertices are reachable from vertex 5?
4. Which vertices are reachable from vertex 6?
Write a C function that takes a Graph and a starting Vertex and returns a set containing all of the vertices that can be reached by following a path from the starting point. Use the function template:
```
Set reachable(Graph g, Vertex src) { ... }
```
You may use any of the standard ADTs from the slides (e.g. Sets, Lists, Stacks, Queues).
Trace the execution of Dijkstra's algorithm on the following graph to compute the minimum distances from source node 0 to all other vertices:

Show the values of vSet, dist[] and pred[] after each iteration.

A helpful resource you can use to check your answer and visualise Dijkstra's algorithm (as well as BFS and DFS) is Graph visualiser by Jonah.
Kruskal's algorithm for finding a minimum spanning tree of a graph can be expressed as follows:
```
typedef Graph MSTree;

MSTree kruskalFindMST(Graph g) {
	MSTree mst = GraphNew(g->nV); // MST initially empty
	Edge eList[g->nE]; // sorted array of edges
	edges(eList, g->nE, g);
	sortEdgeList(eList, g->nE);
	for (int i = 0; mst->nE < g->nV - 1; i++) {
		Edge e = eList[i];
		GraphAddEdge(mst, e);
		if (GraphHasCycle(mst)) GraphRemoveEdge(mst, e);
	}
	return mst;
}
```
This algorithm effectively constructs the MST by gradually joining together the connected graphs in a forest that starts with each subgraph being a single node. On each iteration, it add a new edge to the forest, and reduces the number of subgraphs by one. Show how it would construct the MST for the graph below:

How many edges did we have to consider? For a graph \( G(V, E) \), what is the least number of edges we might need to consider? What is the most number of edges we might have to consider? Add another edge to the above graph to force Kruskal's algorithm to the worst case.
Prim's algorithm for finding a MST of a graph can be expressed abstractly as follows:
1. Start from any vertex v and empty MST
2. Choose edge not already in MST, satisfying
3. Add chosen edge to MST
4. Repeat until MST covers all vertices
Show how Prim's algorithm produces an MST on the following graph:

Start at vertex A.