edited by
165 views
1 votes
1 votes

Let the node P be the starting vertex for Prim's Algorithm as given in the diagram below:

In order to construct the Minimum Spanning Tree, which of the following options represents the correct order of edges in which they are added to construct the tree?

  1. $4,2,1,7,10$
  2. $4,2,1,6,8$
  3. $4,1 ,2,8,10$
  4. $4,1,2,6,8$
edited by

1 Answer

Best answer
1 votes
1 votes
Using Prims algorithm we start from one vertex and find minimum weight edge vertex adjacent to it and mark it as visited and join them without creating any cycle.

Here starting from point P : adjacent edge weights are PQ(4), PH(5), PR(6).

minimum among them is PQ(4) therefore PQ will be joined so 4-----(1) all options

From point P :adjacent edge weights are PH(5), PR(6)

From point Q: adjacent edge weight are QU(2), QH(3)

minimum among them is QU(2) therefore QU will be joined so 2------(2) option A, B will be considered

From point P:adjacent edge weights are PH(5), PR(6)

From point Q: adjacent edge weight is QH(3)

From point U:adjacent edge weights are UH(1), UT(10)

minimum among them is UH(2) therefore UH will be joined so 1------(3) option A, B will be considered

From point P:adjacent edge weights are PH(5)-not taken as it will form cycle, PR(6)

From point Q: adjacent edge weight is QH(3)-not taken as it will form cycle

From point U:adjacent edge weights is UT(10)

From point H:adjacent edge weights are HR(7), HT(9)

minimum among them is PR(6) therefore PR will be joined so 6------(4) option  B will be considered

From point P:adjacent edge weights is PH(5)-not taken as it will form cycle

From point Q: adjacent edge weight is QH(3)-not taken as it will form cycle

From point U:adjacent edge weights is UT(10)

From point H:adjacent edge weights are HR(7)-not taken as it will form cycle, HT(9)

From point R:adjacent edge weights is RT(8)

minimum among them is RT(8) therefore RT will be joined so 8------(5) option  B will be considered

Finally option B is correct with sequence 4,2,1,6,8
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
464 views
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
343 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
456 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.