Whats the intuition/basic logic behind prims and kruskal algorithm?


#1

I know the algorithms and how do they work but whats the basic intuition behind these algorithms and how do i prove that they indeed gives you the MST ,whats the proof of their correctness?


#2

In computer science,Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

Also a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree.

Also A graph is connected when there is a path between every pair of vertices.

The prims algorithm starts by choosing a arbitrary vertex A and then from all the edges connecting to A it chooses the one with minimum weight,so while prims algorithm is developing there are 2 set of vertex,one which are added via prims algorithm and other vertex ehich are still undiscovered.

Now after step 1 we have two vertex say A and B ,now prims algorithm will check edges length of all the vertices connecting to A and connecting to B,and once again it will select the edge with minimum length,so this way the algorithm proceeds till we do not find any more vertex connecting to the tree which is formed by prims.

The proof of coorectness comes from thr fact at every stage we are choosing edge length of minimum weight so there cant exist other edge which could have been included instead the one we added until it is also of the same length and then we have to decide arbitrary.

Bonus: Does MST(Minimum Spannig Tree) is unique when all edge lengths are distinct?
Does MST is unique when we have atleast two edges with same edge length?

Similarly you can try understanding Kruskal.