Prim’s algorithm

please open the pdf file to see the requirement

CS210
Fall 2023
CS210 FALL 2023
Programming Assignment 3
Points Possible: 100 + 10 Extra Credit
This assignment implements Prim’s algorithm to find the minimum spanning tree.
Given the Adjacency Matrix (2D Array) of a Graph, find its minimum spanning tree using Prim’s
algorithm.
You are required to follow the logical method we use in solving the algorithm in class. It does not have
to be an exact method; a modification is also accepted. Refer to the lecture and slide before
beginning.
What is needed?
1. Given G[I][j], this is your graph. All vertex names are integers from 0-N. You must hardcode
your graph into the program. A sample is given for testing.
2. Maintain 2 Lists (Array / LinkedList) to keep track of Visited and Unvisited vertices (Temporary
& Permanent in the lecture example)
3. Pick an arbitrary start vertex set it to visited and check all the edges connected to it. Pick the
lowest cost edge, add the destination vertex to the visited array and remove from unvisited
array.
4. Add all the edges connected to the newly added visited vertex in the mix to compare for
which is the next minimum edge. If the minimum most edge has both visited vertices, remove
it from the mix and check the next minimum edge.
5. You may choose to maintain a Priority Queue for all the discovered edges to pick the
minimum edge every time. A solution without a Priority Queue will also be accepted.
6. When all vertices are visited and the unvisited List becomes empty, the program ends.
7. Extra Credit (10 Points) – Implementing a Binary Heap Priority Queue within the program to
maintain the discovered edges.
Graph for sample output: Coded into the program
int G[i][j] = {{0, 3, 65, 0, 0},
{3, 0, 85, 20, 45},
{65, 85, 0, 41, 77},
{0, 20, 41, 0, 51},
{0, 52, 77, 51, 0}};
Output: Printed by your program
Prim’s MST is Edge -> Cost
0 – 1 -> 3
1 – 3 -> 20
1
CS210
Fall 2023
3 – 2 -> 41
1 – 4 -> 45
Files to be submitted:
Submit a ZIP file (ZIP file must have your First and Last Name) containing the following:
1. C++ File
2. ReadMe.pdf
•
•
Author Name
Answer the following questions :
o Explain what a Minimum Spanning Tree is in your own words
o What could be the real-world applications of an MST?
o Hardcode a difference Graph Matrix in your program
o Does the sample graph hardcoded in your program have a unique Minimum Spanning
Tree? What parameters point towards a unique MST?
2