Task 1:

Kruskal's Algorithm (Minimum Spanning Tree Algorithm)

(1a)

[30 %]

The following figure shows the (partially completed) first stage of Kruskal's algorithm to

find the minimum spanning tree of the graph. It uses the format of two columns: a list of

edges (with an indication of a selected edge in the frame), and an Illustration.

BC

1

A list of edges

(Selected edges are shown in frame)

5

B

6

Illustration

1

3

D

4

2

Complete the figure to show all the intermediate and the final stages of the algorithm.

(1b)

[30 %]

Run (existing) Python code of Kruskal's Algorithm to the same weighted graph above.

Compare the output of the code and the manually generated result above to see whether

they are equivalent.

6

For instance, one of the lab instructions contains information on NetworkX, a Python language

software package for the creation, manipulation, and study of the structure, dynamics, and

function of complex networks.

E