# 3i Infotech Placement: Sample Questions 336 - 336 of 1245

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

## Question 336

### Describe in Detail

Essay▾

Convert the given graph with weighted edges to minimal spanning tree, the equivalent minimal spanning tree is:

### Explanation

• Red edges indicate minimal spanning tree.

## Kruskal՚s Algorithm

• Kruskal ′ s algorithm is easiest to understand and best for solving problems by hand.

Kruskal՚s algorithm:

sort the edges of G in increasing order by length

keep a subgraph S of G, initially empty

for each edge e in sorted order

if the endpoints of e are disconnected in S

return S

• An edge (u, v) when added is always the smallest one connecting the part of S reachable from u with the rest of G, so it must be part of the MST.
• This algorithm is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to S.

Other research on finding the minimum spanning tree

• When edges of the graph have weights or lengths- weight of a tree is the sum of weights of its edges. Different spanning trees have different edge length and hence weights. The problem is to find the minimum length spanning tree.
• A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, “A randomized linear-time algorithm to find minimum spanning trees” , J. ACM, vol. 42,1995, pp. 321 - 328.]
• Solved in linear worst-case time if the weights are small integers. [Fredman and Willard, “Trans-dichotomous algorithms for minimum spanning trees and shortest paths” , 31st IEEE Symp. Foundations of Comp. Sci. , 1990, pp. 719 - 725.]

Developed by: