(a) Find a minimum spanning tree (MST) of the graph G in Figure 1 using Kruskal's...

 

Transcribed Image Text:

(a) Find a minimum spanning tree (MST) of the graph G in Figure 1 using Kruskal's algo- rithm. You only need to write down all the edges considered, in the correct order they are considered, and whether they are added to the MST or not. [3 marks] (b) Starting with the min-heap H in Figure 1, the following operations are applied successively to the heap. Show the contents of the heap (i.e., draw a tree representation of it) after each step. Insert 8; delete minimum; insert 4. [5 marks] (c) You are given a directed graph G where all edge weights are positive. Given two vertices s and t in G, we want to find the "best" path from s to t, where "best" means the primary objective is to minimise the total weight of all edges along the path; if there are multiple paths with the same minimum weight, we prefer the one with the fewest edges. i. Write down the pseudocode of an efficient algorithm for this problem. You only need to compute the total weight and the number of edges of the best path, and need not recover the path itself. [6 marks] ii. Demonstrate how your algorithm works with the graph G in Figure 1. You should show the contents of any data structure used after each step. [6 marks] 2 b 14 9 11 13 G d e 3 H 2 5 Figure 1: G for Q3(a); H for Q3(b); G for Q3(c). 10 12 2 (a) Find a minimum spanning tree (MST) of the graph G in Figure 1 using Kruskal's algo- rithm. You only need to write down all the edges considered, in the correct order they are considered, and whether they are added to the MST or not. [3 marks] (b) Starting with the min-heap H in Figure 1, the following operations are applied successively to the heap. Show the contents of the heap (i.e., draw a tree representation of it) after each step. Insert 8; delete minimum; insert 4. [5 marks] (c) You are given a directed graph G where all edge weights are positive. Given two vertices s and t in G, we want to find the "best" path from s to t, where "best" means the primary objective is to minimise the total weight of all edges along the path; if there are multiple paths with the same minimum weight, we prefer the one with the fewest edges. i. Write down the pseudocode of an efficient algorithm for this problem. You only need to compute the total weight and the number of edges of the best path, and need not recover the path itself. [6 marks] ii. Demonstrate how your algorithm works with the graph G in Figure 1. You should show the contents of any data structure used after each step. [6 marks] 2 b 14 9 11 13 G d e 3 H 2 5 Figure 1: G for Q3(a); H for Q3(b); G for Q3(c). 10 12 2