I've been trying to learn about minimum span trees and the algorithms associated with it, namely Prim's, Kruskal's and Dijkstra's algorithms.
I understand how these algorithms work and have seen them in action but there is only one thing I don't understand about Prim's algorithm, which is an array that I don't understand what it is it's intention and how does it work.
So here is the situation:
I have to do an exercise wherein I am given an adjacency table and I have to run Prim's algorithm to create a minimum span tree.
The table looks like this:
0 |1|2| 3| 4| 5|
0| 0 73 4 64 40 74
1| 73 0 46 26 30 70
2| 4 46 0 77 86 14
3| 64 26 77 0 20 85
4| 40 30 86 20 0 22
5| 74 70 14 85 22 0
The numbers separated by the "|" are the vertices and the numbers in the table are the edges. Simple, I run the algorithm ( in this website for example: http://www.jakebakermaths.org.uk/maths/primsalgorithmsolverv10.html ) or just jot it down on paper and and draw the minimum span tree and I get the tree with the minimal cost of 86 and the edges that have been used are 4, 26, 20, 22 and 14.
Now here comes the problem, apparently just solving it wasn't enough. I need to find the values of an array called closest[0,...,5]. I know it is used in the algorithm but I don't know it's purpose and what I should do with it or how to get it's values.
I have searched the internet for it and found this link about Prim's algorithm: http://lcm.csa.iisc.ernet.in/dsa/node183.html
Which defines the array "closest" as "For i in V - U, closest[i] gives the vertex in U that is closest to i".
I still don't understand what it is, what it is used for and what the values inside of them are.
All I know the answer to my exercise is
closest[1] = 3
closest[2] = 0
closest[3] = 4
closest[4] = 5
closest[5] = 2
Thank you in advance.
When doing a MST with Prim's algorithm, it is important to keep track of four things: the vertex, has it been visited, minimal distance to vertex, and what precedes this vertex (this is what you are looking for).
You start at vertex 0, and you see that the closest vertex to 0 is 2. At the same time, you could have visited all other nodes, but with bigger distances. Nevertheless, the closest node to 0 is 2, so thus 2 becomes visited and its parent is set to vertex 0. All the other nodes are not visited yet, but its parent as of now is set to 0, with its respective distance. You now need to set the smallest distance vertex to visited, and now consider this node as the node to be considered.
Vertex | Visited | Distance | Parent
0 | T | - | -
1 | F | 73 | 0
2 | T | 4 | 0
3 | F | 64 | 0
4 | F | 40 | 0
5 | F | 74 | 0
We then check all the distances of nodes from 2. We compare the new distances from 2 to the other nodes to the distance from the other nodes from its previous distance, and if it needs to be updated, it gets updated. We now see that the distance from 2 to 5 is shorter than 0 to 5, and vertex 5 now becomes becomes visited, with its parent now equal to vertex 2.
Vertex | Visited | Distance | Parent
0 | T | - | -
1 | F | 46 | 2
2 | T | 4 | 0
3 | F | 64 | 0
4 | F | 40 | 0
5 | T | 14 | 2
Now we visit 5. One thing to note is that if a node is visited, we do not consider it in our distance calculations. I have simulated the rest, and hopefully you can see how you get the answer you're looking for.
Vertex | Visited | Distance | Parent
0 | T | - | -
1 | F | 46 | 2
2 | T | 4 | 0
3 | F | 64 | 0
4 | T | 22 | 5
5 | T | 14 | 2
Now visit 4
Vertex | Visited | Distance | Parent
0 | T | - | -
1 | F | 46 | 2
2 | T | 4 | 0
3 | T | 20 | 4
4 | T | 22 | 5
5 | T | 14 | 2
And now visit 3
Vertex | Visited | Distance | Parent
0 | T | - | -
1 | T | 26 | 3
2 | T | 4 | 0
3 | T | 20 | 4
4 | T | 22 | 5
5 | T | 14 | 2