# Basic CS [3i Infotech Placement]: Sample Questions 60 - 60 of 243

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

## Question 60

Basic CS

### 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

add e to 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” , 31
^{st}IEEE Symp. Foundations of Comp. Sci. , 1990, pp. 719 - 725.]