Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Data Structures and Algorithms > Old Questions > 2066

Data Structures and Algorithms - Old Questions

Syllabus Notes Old Questions Unit Wise Questions Question Bank

9. Differentiate between tree and graph. What are spanning forest and spanning tree. Explain MST (Minimum cost Spanning Tree) problem.

5 marks | Asked in 2066

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 Trees

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.