Ask
Login
0
3.8kviews
Define Minimum Spanning Tree. List the techniques to compute minimum spanning tree.
written 8.9 years ago by gravatar for teamques10 teamques10 ★ 70k •   modified 8.9 years ago

Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 2M

Year: Dec 2015
data structures and algorithms
ADD COMMENT EDIT
1 Answer
1
59views
written 8.9 years ago by gravatar for teamques10 teamques10 ★ 70k

Minimum Spanning Tree:

A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at lowest total cost. A minimum spanning tree exists if and only if G is connected. Below figure shows the graph which is minimum spanning tree:

enter image description here

Techniques for calculating the minimum spanning tree:

  1. Using Prim’s Algorithm
  2. Kruskal’s Algorithm
ADD COMMENT EDIT
Please log in to add an answer.