Register

please explain also..

764 views

2 Answers

1 1 vote

FIRST APPROACH: DRAW MST AND CHECK

SECOND APPROACH:

A-B,A-D,B-E ARE SELECTED USING KRUSKAL SO EDGES B-D AND D-E CANT BE SELECTED AS THEY WILL LEAD TO CYCLE. WE HAVE REMAINING 2 EDGES TO FULFILL MST CONDITION.

WE CAN SELECT 2 EDGES FROM BC,EF,CF,EC. SO 4C2 WAYS=6

BUT CHOOSING EDGES BC AND EC CAN LEAD TO CYCLE. SO TOTAL MST=6-1=5

Voting & Accepting an answer helps improve the community
← Previous · GATEBOOK_CN_3#9Next → · Self doubt C program...
← Previous in category · why do we need O(n),...Next in category → · Minimum spanning tre...
Position:
Show:

Related questions

2 2 votes
0 0 answers
1.2k
1.2k views
sandip_1999 asked May 11, 2022
1,191 views
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you won't find the most optimal solution? So how can Kruskal be able to find the minimum spanning tree while also being greedy?
Please can anyone tell me though Prim’s and Kruskal’s algorithms are greedy algorithms. Greedy algorithms always give local optimum solutions but how Prim’s and Kruskal’s...
1 1 vote
1 1 answer
2.3k
2.3k views
Mak Indus asked Nov 6, 2018
2,272 views
Please Explain also..
. Assume an array A[1….n] has n-elements, and every element of an array is less than or equal to n. An element is said to be majority element, if it occurred in more than...
0 0 votes
0 0 answers
327
327 views
Miku221 asked Sep 3, 2024
327 views
Minimum of maximum all node-weights in path.
Given a connected graph has $N$ vertices and $M$ edges. Each node $i$ has the weight value $w_i$. Define the strength of a path from $s$ to $t$ is the maximum weight of a...
1 1 vote
1 answers 1 answer
1.3k
1.3k views
Debargha Mitra Roy asked Aug 25, 2024
1,270 views
Question - 2 | DPP | Greedy Method
Which of the statement is/are correct?(a) First edge added by Kruskal’s algorithm can be the last edge added by prim’s algorithm(b) In a graph, if one raises the length o...