Week 08 Tutorial Answers

Graphs (ii)

  1. 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?

    Answer:

    1. From vertex 0: 0, 1, 2, 3, 4, 5, 7, 8
    2. From vertex 1: 1
    3. From vertex 5: 1, 5
    4. From vertex 6: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

  2. 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).

    Answer:

    One solution would be to simply use breadth-first search or depth-first search, and add vertices to a set as you visit them. The set fulfils the role of the visited array, which is why we don't need a separate visited array.

    Set reachable(Graph g, Vertex src) {
	Set seen = SetNew();
	
	Queue q = QueueNew();
	QueueEnqueue(q, src);
	SetAdd(seen, src);
	
	while (!QueueIsEmpty(q)) {
		Vertex v = QueueDequeue(q);
		
		for (Vertex w = 0; w < g->nV; w++) {
			if (g->edges[v][w] && !SetContains(seen, w)) {
				QueueEnqueue(q, w);
				SetAdd(seen, w);
			}
		}
	}
	return seen;
}

    Another solution would be to use recursive depth-first search, which is convenient as it doesn't require a Stack or Queue.

    Set reachable(Graph g, Vertex src) {
	Set seen = SetNew();
	doReachable(g, src, seen);
	return seen;
}

static void doReachable(Graph g, Vertex v, Set seen) {
	SetAdd(seen, v);
	
	for (Vertex w = 0; w < g->nV; w++) {
		if (g->edges[v][w] && !SetContains(seen, w)) {
			doReachable(g, w, seen);
		}
	}
}

  3. 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.

    Answer:

    Initialisation:

    vSet = { 0, 1, 2, 3, 4, 5, 6, 7 }
dist = [  0,  ∞,  ∞,  ∞,  ∞,  ∞,  ∞,  ∞ ]
pred = [ -1, -1, -1, -1, -1, -1, -1, -1 ]

    The vertex in vSet with minimum dist[] is 0. Relaxation along the edges (0, 1, 5), (0, 2, 4) and (0, 3, 6) results in:

    vSet = { 1, 2, 3, 4, 5, 6, 7 }
dist = [  0,  5,  4,  6,  ∞,  ∞,  ∞,  ∞ ]
pred = [ -1,  0,  0,  0, -1, -1, -1, -1 ]

    Now the vertex in vSet with minimum dist[] is 2. Considering all edges from 2 to nodes still in vSet:

    • relaxation along (2, 1, 8) does not give us a shorter distance to node 1
    • relaxation along (2, 3, 1) yields a smaller value (4 + 1 = 5) for dist[3], and pred[3] is updated to 2
    • relaxation along (2, 4, 3) yields a smaller value (4 + 3 = 7) for dist[4], and pred[4] is updated to 2
    • relaxation along (2, 5, 7) yields a smaller value (4 + 7 = 11) for dist[5], and pred[5] is updated to 2

    vSet = { 1, 3, 4, 5, 6, 7 }
dist = [  0,  5,  4,  5,  7, 11,  ∞,  ∞ ]
pred = [ -1,  0,  0,  2,  2,  2, -1, -1 ]

    Next, we could choose either 1 or 3, since both vertices have minimum distance 5. Suppose we choose 1. Relaxation along (1, 5, 2) and (1, 6, 7) results in new values for nodes 5 and 6:

    vSet = { 3, 4, 5, 6, 7 }
dist = [  0,  5,  4,  5,  7,  7, 12,  ∞ ]
pred = [ -1,  0,  0,  2,  2,  1,  1, -1 ]

    Now we consider vertex 3. The only adjacent node still in vSet is 4, but there is no shorter path to 4 through 3. Hence no update to dist[] or pred[]:

    vSet = { 4, 5, 6, 7 }
dist = [  0,  5,  4,  5,  7,  7, 12,  ∞ ]
pred = [ -1,  0,  0,  2,  2,  1,  1, -1 ]

    Next we could choose either vertex 4 or 5. Suppose we choose 4. Edge (4, 7, 8) is the only one that leads to an update:

    vSet = { 5, 6, 7 }
dist = [  0,  5,  4,  5,  7,  7, 12, 15 ]
pred = [ -1,  0,  0,  2,  2,  1,  1,  4 ]

    Vertex 5 is next. Relaxation along edges (5, 6, 3) and (5, 7, 6) results in:

    vSet = { 6, 7 }
dist = [  0,  5,  4,  5,  7,  7, 10, 13 ]
pred = [ -1,  0,  0,  2,  2,  1,  5,  5 ]

    Of the two vertices left in vSet, 6 has the shorter distance. Edge (6, 7, 5) does not update the values for node 7 since dist[7] = 13 < dist[6] + 5 = 15. Hence:

    vSet = { 7 }
dist = [  0,  5,  4,  5,  7,  7, 10, 13 ]
pred = [ -1,  0,  0,  2,  2,  1,  5,  5 ]

    Processing the last remaining vertex in vSet will obviously not change anything. The values in pred[] determine shortest paths to all nodes as follows:

    0: distance =  0, shortest path: 0
1: distance =  5, shortest path: 0-1
2: distance =  4, shortest path: 0-2
3: distance =  5, shortest path: 0-2-3
4: distance =  7, shortest path: 0-2-4
5: distance =  7, shortest path: 0-1-5
6: distance = 10, shortest path: 0-1-5-6
7: distance = 13, shortest path: 0-1-5-7

  4. 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? Modify the graph above to force Kruskal's algorithm to the worst case.

    Answer:

    We start with no edges (non-existent edges are indicated by dotted lines):

    Below, we show the graph at the end of each iteration of the for loop. We do not show the intermediate state of the graph when have added an edge which turns out to produce a cycle.

    In the first iteration, we could choose either 1-4 or 6-7, since both edges have weight 1. Assume we choose 1-4. Since its inclusion produces no cycles, we add it to the MST:

    In the next iteration, we choose 6-7. Its inclusion produces no cycles, so we add it to the MST:

    In the next iteration, we could choose either 1-2 or 3-4, since both edges have weight 2. Assume we choose 1-2. Since its inclusion produces no cycles, we add it to the MST:

    In the next iteration, we choose 3-4. Its inclusion produces no cycles, so we add it to the MST:

    In the next iteration, we would first consider the lowest-cost unused edge. This is 2-4, but its inclusion would produce a cycle, so we ignore it. We then consider 1-3 and 4-7 which both have weight 4. If we choose 1-3, that produces a cycle so we ignore that edge. If we add 4-7 to the MST, there is no cycle and so we include it:

    In the next iteration, we would first consider the lowest-cost unused edge. This is 3-6, but its inclusion would produce a cycle, so we ignore it. We then consider 5-7. If we add 5-7 to the MST, there is no cycle and so we include it:

    At this stage, all vertices are connected and we have a MST.

    For this graph, we considered 9 of the 12 possible edges in determining the MST. For a graph \( G(V, E) \), the best case would be when the first \( V - 1 \) edges we consider are the lowest cost edges and none of these edges leads to a cycle. The worst case would be when we had to consider all \( E \) edges.

    To force Kruskal's algorithm to the worst case, we could remove edges 4-5 and 5-7, which would cause the algorithm to consider all edges before completing the MST, as the only edge that would connect vertex 5 to the rest of the graph would be the edge with the highest cost. We could also add a vertex 8 to the graph, and connect it to any existing vertex with an edge with weight 11 (or any cost larger than all the other edge costs in the graph).

  5. 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
      • incident on a vertex s already in MST
      • incident on a vertex t not already in MST
      • with minimal weight of all such edges
    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.

    Answer:

    Initially:

    • The MST contains just the starting vertex: V = {A}, E = {}

    Iteration 1:

    • Choices: AB, AC, AD ... AB is cheapest
    • Updated MST: V = {A, B}, E = {AB}

    Iteration 2:

    • Choices: AC, AD, BD, BE ... AD is cheapest
    • Updated MST: V = {A, B, D}, E = {AB, AD}

    Iteration 3:

    • Choices: AC, BE, DC, DF, DG ... DF is cheapest
    • Updated MST: V = {A, B, D, F}, E = {AB, AD, DF}

    Iteration 4:

    • Choices: AC, BE, DC, DG, FE, FG ... DG is cheapest
    • Updated MST: V = {A, B, D, F, G}, E = {AB, AD, DF, DG}

    Iteration 5:

    • Choices: AC, BE, DC, FE, GC, GE ... GE is cheapest
    • Updated MST: V = {A, B, D, E, F, G}, E = {AB, AD, DF, DG, GE}

    Iteration 6:

    • Choices: AC, DC, GC ... AC is cheapest
    • Updated MST: V = {A, B, C, D, E, F, G}, E = {AB, AD, DF, DG, GE, AC}

    All vertices are now included, so we have the MST: