Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?(a) Graph M has no minimum spanning tree(b) Graph M has a unique minimum spanning trees of cost 2(c) Graph M has 3 distinct minimum spanning trees, each of cost 2(d) Graph M has 3 spanning trees of different costsThe question was asked in an interview for internship.My question comes from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Consider the graph M with 3 vertices. Its adjacency matrix is shown be

1.	Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?(a) Graph M has no minimum spanning tree(b) Graph M has a unique minimum spanning trees of cost 2(c) Graph M has 3 distinct minimum spanning trees, each of cost 2(d) Graph M has 3 spanning trees of different costsThe question was asked in an interview for internship.My question comes from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II
Answer» The CORRECT option is (c) Graph M has 3 DISTINCT MINIMUM spanning trees, each of cost 2 The best explanation: Here all non-diagonal elements in the adjacency MATRIX are 1. So, EVERY vertex is connected every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.

Discussion

No Comment Found

Related InterviewSolutions

Which of the following is false about Prim’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It never accepts cycles in the MST(d) It can be implemented using the Fibonacci heapThe question was posed to me in an interview for internship.I want to ask this question from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.(a) d-ary heap(b) linear search(c) fibonacci heap(d) binary searchThis question was posed to me during an online exam.Query is from Minimum Spanning Tree topic in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is also known as __________(a) Dijkstra–Scholten algorithm(b) Borůvka’s algorithm(c) Floyd–Warshall algorithm(d) DJP AlgorithmThe question was posed to me during an interview for a job.My doubt stems from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.(a) True(b) FalseThe question was posed to me at a job interview.Asked question is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm resemblesDijkstra’s algorithm.(a) True(b) FalseI had been asked this question in quiz.Question is from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is a ______(a) Divide and conquer algorithm(b) Greedy algorithm(c) Dynamic Programming(d) Approximation algorithmI got this question in class test.My question is taken from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?(a) O(log V)(b) O(V^2)(c) O(E^2)(d) O(V log E)I had been asked this question during an interview.Query is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is true?(a) Prim’s algorithm initialises with a vertex(b) Prim’s algorithm initialises with a edge(c) Prim’s algorithm initialises with a vertex which has smallest edge(d) Prim’s algorithm initialises with a forestThis question was addressed to me in examination.Origin of the question is Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.(a) True(b) FalseI have been asked this question by my college professor while I was bunking the class.Question is from Minimum Spanning Tree in section Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is false about the Kruskal’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It can accept cycles in the MST(d) It uses union-find data structureThe question was posed to me in unit test.Question is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment