Bissoy.com
Doctors Medicines MCQs Q&A

Consider the graph given below:   Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is?

Consider the graph given below:   Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is? Correct Answer GC, AD, GB, GA, BF, AE

Concept:

Krushkal Algorithm

1. First Sort All Edges in non Decreasing order. ( Generally Uses Min Heap ) 

2. Delete Minimum Edge from Min heap.

3. Add it to MST if does not create a cycle else ignore it.

Repeat 2,3 until there are (V-1) edges in MST. 

Explanation:

Given:

[ alt="F1 Shraddha Harshita 04.01.2022 D 1" src="//storage.googleapis.com/tb-img/production/22/01/F1_Shraddha_Harshita_04.01.2022_D%201.png" style=" width: 275px; height: 103px;">
Non-Decreasing Order will be {AD, GC, AG, GB, EA, DG, BC, BF, ED, CF}

[ alt="F1 Shiv Sahu 5.3.21 Pallavi D1" src="//storage.googleapis.com/tb-img/production/21/04/F1_Shiv%20Sahu_5.3.21_Pallavi_D1.png" style="width: 254px; height: 140px;">

So correct Sequence will be  AD, GC, GB, GA, BF, AE

Note:

1. Sequence of Equal Weight Edges can be interchanged.

2. We Assumed that BD's edge weight is greater than all the other edges in the graph. as BD's edge weights not given and considering '1' as edge weight of BD not possible with the given options.

Related Questions

Consider the following statements. S1. Kruskal’s algorithm might produce a non-minimal spanning tree. S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
Let ‘m’ and ‘n’ be the number of edges and vertices in a graph G, respectively. Which of the following is the time complexity of the Kruskal’s algorithm to find minimum spanning tree of G?
Given below are some famous algorithms and some algorithm design paradigms Algorithms Design Paradigm  1. Dijkstra's shortest path algorithms  (a) Greedy design  2. Floyd-Warshall's all-pair-shortest path algorithms  (b) Divide and conquer  3. Kruskal's minimum spanning tree algorithm  (c) Dynamic programming  4. Merge Sort algorithm     Which of the following correspondence is correct?
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
For the next cyclone if it is the turn of an Indian name to be chosen, then what will be that name?
Read the passage carefully and choose the best answer to each question out of the four alternatives.
Eight north Indian Ocean countries, namely, Bangladesh, India, the Maldives, Myanmar, Oman, Pakistan, Sri Lanka and Thailand, were asked to contribute names so that a combined list could be compiled. Each country gave eight names and a combined list of 64 names was prepared. This list is currently in use, and all cyclones arising in the north Indian Ocean are named from this list, with one name from each country being used in turn. Almost 38 or 39 names from the list have been used up, but since many cyclones dissipate long before they hit land, their names rarely figure in the papers or other media. The names that people do know about, and remember are, naturally, those that were most destructive ones, or very recent. Aila, in 2009 is remembered with a shudder for the enormous destruction it caused in West Bengal and Bangladesh; Phaillin, also for the damage it caused when it hit the Odisha coast in 2013. Two harmless cyclones, which also might remain in peoples memory, are the more recent ones of 2014 — Hudhud, which threatened the east coast of India and Nilofar, which was expected to, but did not, devastate the western coast. The names in the cyclone list are usually words one associates with storms; words which mean water or wind or lightning in various national languages. Sometimes they are names of other things — birds or flowers or precious stones. The name Aila, contributed by the Maldives means fire, the name Phaillin from Thailand means sapphire, the name Hudhud from Oman is the name of a bird, probably the hoopoe, and the name Nilofar, given by Pakistan, is the Urdu name of the lotus or water lily. The eight names suggested by India, and which are in the list of 64, are Agni, Akaash, Bijli, Jal, Leher, Megh, Sagar and Vayu, meaning in that order, fire, sky, lightning, water, wave, cloud, sea and wind. Five of these names (that is, up to Leher) have been used so far.
Which country did not contribute to the list of the cyclone names?
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Consider the given graph. What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only