Prim's Algo results in a MST

In Prim's you maintain a list of visited vertices.

Start with the smallest edge. say AB

now pick the next smallest edge connecting to either A or B.

Similarly, keep repeating till all the vertices are covered but making usre no cycles are formed.

That's it!!

Time Complexity depends on the data structure you use:

Adjacency Matrix, Searching: O($$V ^ 2$$)

Binary Heap and Adjacency List: O(V log V + E log V)

Prim's Algo

results matching ""