MA214 Algorithms and Data Structures
2023/24
Exercises 9
(Kruskal’s algorithm, Dijkstra’s algorithm)
Exercise 9.1. Kruskal’s algorithm 5 pts
Implement Kruskal’s minimum spanning tree algorithm in Python. The pseudocode for the algorithm is given in the course textbook. Differently from Prim’s algorithm, Kruskal’s algorithm returns the set of the edges of a minimum spanning tree. There-fore, will not use the predecessor links to capture the tree. The implementation of a graph data structure, Graph .py, is given on the course Moodle page. Import that file without changing the contents. Your submissions will be used together with a local copy of that file.
In this implementation, you will need to represent each edge as a triple (u, v, w), where (u, v) is the edge and w = w (u, v) is the weight of that edge. You may refresh on the use of tuples in Python at the following link: Tuples. You may also find sorting lists of tuples acording to a particular tuple entry useful. The examples at the following link show how to do that: Sorting.
A template file for you to complete is provided on Moodle. Please submit a single file MSTKruskal .py atthe submission link for this question.
Exercise 9.2. Dijkstra’s algorithm 5 pts
(a) Run Dijkstra’s algorithm on the directed graph below, first using vertex s as the source and then using vertex z as the source. Use the examples from the lecture as a template.
(b) Suppose we change line 11 of Dijkstra’s algorithm to the following:
11 while len ( Q ) > 1
This change causes the while loop to execute |V| − 1 = n − 1 times instead of |V| times. Is this proposed algorithm correct?
Submit your solutions to this question as a PDF-file at the submission link for this question.