5. Prim’s Algorithm #

Created Saturday 25 April 2020

• This algorithm is used for finding MST
• Greedy algorithm: We select the myopically best option.
• As it is a greedy algorithm, it is easy to implement.
• We have a table with three columns, (vertex, parent, weight(from parent to weight)).
• We also need two lists **visited and unvisited. **Better to keep an array. Space O(V). Initially unvisited has all the vertex and visited has none. Meaning of visited: The vertex where we have went and explored its neighbours. Vertex which are encountered as a result of the exploration are still unvisited.

Implementation:

1. Keep a 2 tuple array with i as the vector. (i.e we store parent and weight). Initially parent of start is -1, (no parent) and it’s weight is zero. All other parents are blank and weight is INT_MAX(infinity).
2. Keep two lists,**visited **and unvisited. Intially visited is empty and the other is equal to V.
3. Select a minimum weight vertex from the unvisted vertex from the table and visit it’s unvisited neighbours. If a neighbour has a lesser value than already update the weight and parent(to the current node). Add the current to the visited array. Remove it from the unvisited one. Continue until |unvisited|==0.
4. We have the MST starting from the selected weight.
5. We need to find the minimum explicitly, as we may have some ‘old’ seen minimum which is not our neighbour now. Our algo explicitly states that we run on the minimum from the table.

T.C with matrix: O(V^2^) For an adjacency list with my method: T.C ~ O(Ek) ~ O(E log V) Optimizations:

1. Using Priority Queue - not required, we did not even have a findMIn.
2. Using adjacency list improves the search for neighbours.

T.C: (E+V)log(V) = E log V