Which of the following algorithms are based on Breadth First Search (BFS)?
A. Prim's algorithm
B. Kruskal's algorithm
C. Dijkstra's algorithm
D. Greedy algorithms
E. Dynamic Programming
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. A & C only
Explanation
Prim's and Dijkstra's algorithms grow a tree outward from a source vertex level by level, like BFS with a priority queue instead of a FIFO queue. Kruskal's works on sorted edges, and greedy/DP are general strategies.More Data Structures and Algorithms questions
- Which of the following is the solution of the recurrence relation T(n) = T(2n/3) + 1?
- Which of the following description(s) is/are true? A. Red-Black Tree – guarantees worst case O(log n) time for search, insert & delete. B.…
- Match List I with List IIList I List II A. Insertion Sort I. O(log n) B. Binary Search II. O(n²) C. Quick Sort III. O(n) D. Selection Sort…
- Arrange the following recurrence relations in increasing order of their time complexity: (A) T(n) = T(n/2) + 1 (B) T(n) = 2T(n/2) + n (C) T…
- Select the sorting algorithms that are stable. (A) Quick Sort (B) Bubble Sort (C) Insertion Sort (D) Merge Sort (E) Shell Sort Choose the c…
- ______ is a self-balancing binary search tree where the path from the root to the farthest leaf is no more than twice as long as the path f…