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

Describe in Detail

Essay▾

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

Graph of the Minimal Spanning Tree

Explanation

Minimal Spanning Tree in Graph
  • 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.
The Kruskal՚s Algorithm

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: