# C++ Prim's Algorithm Implementation

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.