The Heap Space

  What is Prim's Algorithm? Like Kruskal's Algorithm, Prim's Algorithm is also a Greedy Algorithm and is used to find the Minimum Spanning Tree of a graph. In Prim's Algorithm, we will start from a source and then keep on selecting the next vertex which has minimum distance. Also, we avoid going into a cycle by marking the node which we have already processed as 'visited'. What is the difference between Prim's Algorithm and Kruskal's Algorithm? In Kruskal's Algorithm, our focus was on edges. But in Prim's algorithm, our focus will be on vertices/nodes of the graph. Prim's Algorithm [Time Complexity: O(ElogV), Spave Complexity: O(V)] 1. Take any vertex/node of the graph as starting vertex/node and mark its distance as 0. Also, mark the distance of all other nodes as infinity. 2. Push all the vertices in a min-heap. 3. Do till min-heap is not empty:          4. Extract min from minheap and mark that extracted node as visited.        ...

  What is Minimum Spanning Tree (MST)? A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected and weighted graph. Thus MST is a tree . MST connects all the vertices/nodes of the graph together.  MST does not contain any cycles . MST finds minimum edge weight . MST contains ( V-1) edges , where V is the number of vertices/nodes in the graph.  No. of Spanning Trees possible for a graph (caution: Here I am not talking about Minimum Spanning Tree, but Spanning Tree in general): [ |E|C|V-1| ] - [no. of cycles]       ( here C is Combination of pnc)  Kruskal's Algorithm uses a Disjoint Set Data Structure to find Minimum Spanning Tree. Kruskal's Algorithm is a greedy algorithm.   Kruskal's Algorithm 1. for each node perform makeSet() operation of disjoint set 2. sort each edge of the graph in non-decreasing order by weight  3. for each edge (u,v):          4. if findSet(u) != findSet(v)...