In this assignment, you will be implementing the Prim's algorithm to find a minimum spanning tree and its total weight. It should also compute π value for each node and key value for each node (show π and key array content.). You will also need to implement a Heap data structure.
The example input graph is the following:
9
Helium Fluorine/5 Calcium/6
Aluminum Dysprosium/21
Calcium Fluorine/2 Dysprosium/12 Helium/6
Iodine Barium/24 Europium/14
Dysprosium Calcium/12 Aluminum/21 Europium/28
Europium Dysprosium/28 Fluorine/29 Iodine/14
Fluorine Calcium/2 Helium/5 Europium/29
Gallium Barium/17
Barium Iodine/24 Gallium/17
where the first number is the number of nodes/vertices followed by a blank line, then each line after that is a vertex name followed by other vertices reachable with a cost; line 3 indicates from Helium there is an edge to Fluorine (weight 5), and to Calcium (weight 6).
Note: all edges are directed and that edges may appear more than once: Aluminum to Dysprosium, Dysprosium to Aluminum. You might see a line with a vertex name without any other vertices following. That means that there is no edge coming from the vertex.
Input will end with a blank line (after node and edge information, a user hits return)
1. Using the given input, store this information as an adjacency list or an adjacency matrix. You should store them in alphabetical order.
2. Define a priority queue using a heap. A heap will be an array and its size will be same as the number of nodes in the graph. You will also need to define functions, build-heap(), decrease-key(), and extract-min(). You can add additional functions if necessary, but points are allocated to define these three functions.
3. Create arrays π and key.
4. Using the same data set, calculate a minimum spanning tree using Prim's algorithm by creating MST-Prim function
and print the minimum spanning tree as follows, and also display the total tree weight, the final π array content, and final key array content:
The minimum spanning tree produced by the Prim's algorithm consists of the following edges:
Aluminum -> Dysprosium with key 21
Dysprosium -> Calcium with key 12
Calcium -> Fluorine with key 2
Fluorine -> Helium with key 5
Dysprosium -> Europium with key 28
Europium -> Iodine with key 14
Iodine -> Barium with key 24
Barium -> Gallium with key 17
The total tree weight is 123
The array pi content:
pi[Aluminum]= none
pi[Barium]= Iodine
pi[Calcium]= Dysprosium
pi[Dysprosium]= Aluminum
pi[Europium]= Dysprosium
pi[Fluorine]= Calcium
pi[Gallium]= Barium
pi[Helium]= Fluorine
pi[Iodine]= Europium
The array key content:
key[Aluminum]=0
key[Barium]=24
key[Calcium]=12
key[Dysprosium]=21
key[Europium]=28
key[Fluorine]=2
key[Gallium]=17
key[Helium]=5
key[Iodine]=14
Print all vertex pairs (edges) with their weight in the order that they were added to the tree, and the total tree weight.