Data Structures and Algorithms - Old Questions

Difference between tree and graph

Spanning Tree

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

Spanning Forest

Spanning forest is a forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two vertices.

--> Spanning forest is a forest of spanning tree in the sub-graph of G.

MST (Minimum cost Spanning Tree) problem

A minimum spanning tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.

There are three different algorithms to construct the minimum spanning tree:

•     Prim’s algorithm: Grows the tree in stages. Selects an edge with lowest cost that can be added to the tree without forming cycle.
•     Kruskal’s algorithm: In each stage select the edge in non-decreasing order of cost.
•     Sollin’s algorithm: Select several edges at each stage.