NTA-UGC-NET 2021 Dec & 2022 June Paper-2
October 14, 2023Software-Engineering
October 14, 2023Digital-Logic-Design
| Question 490 |
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?
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?
| AD, AE, AG, GC, GB, BF | |
| GC, GB, BF, GA, AD, AE | |
| GC, AD, GB, GA, BF, AE | |
| AD, AG, GC, AE, GB, BF |
Question 490 Explanation:
Kruskal’s algorithm will sort all edge weight first and according to spanning tree rules it construct Minimum cost spanning tree.
Here, some edges have same weight. This situation, we can get many number of spanning trees.
We have to connect strictly below order.
Note: DB not given edge weight. GC, AD, BG, AE, BF
Edge weight 2= AD or GC
Edge weight 3= AG or GB
Edge weight 4= AE or DG or BC or BF
Edge weight 5= ED or CF
Edge weight 6: AC
Here, some edges have same weight. This situation, we can get many number of spanning trees.
We have to connect strictly below order.
Note: DB not given edge weight. GC, AD, BG, AE, BF
Edge weight 2= AD or GC
Edge weight 3= AG or GB
Edge weight 4= AE or DG or BC or BF
Edge weight 5= ED or CF
Edge weight 6: AC
Correct Answer: C
Question 490 Explanation:
Kruskal’s algorithm will sort all edge weight first and according to spanning tree rules it construct Minimum cost spanning tree.
Here, some edges have same weight. This situation, we can get many number of spanning trees.
We have to connect strictly below order.
Note: DB not given edge weight. GC, AD, BG, AE, BF
Edge weight 2= AD or GC
Edge weight 3= AG or GB
Edge weight 4= AE or DG or BC or BF
Edge weight 5= ED or CF
Edge weight 6: AC
Here, some edges have same weight. This situation, we can get many number of spanning trees.
We have to connect strictly below order.
Note: DB not given edge weight. GC, AD, BG, AE, BF
Edge weight 2= AD or GC
Edge weight 3= AG or GB
Edge weight 4= AE or DG or BC or BF
Edge weight 5= ED or CF
Edge weight 6: AC
Subscribe
Login
0 Comments