Algorithms Graph Algorithms & Traversal

Question 1

Which graph traversal algorithm uses a queue as its primary data structure?

Accepted Answer

Breadth-First Search

Answer

Breadth-First Search (BFS) uses a queue to explore all neighbors at the current depth level before moving deeper.

Question 2

What does Dijkstra's algorithm compute for a weighted graph?

Accepted Answer

Shortest path from a single source

Answer

Dijkstra's algorithm finds the shortest (minimum-weight) path from a single source vertex to all other vertices in a non-negative-weight graph.

Question 3

Which algorithm can detect negative-weight cycles in a graph?

Accepted Answer

Bellman-Ford Algorithm

Answer

The Bellman-Ford algorithm detects negative-weight cycles by checking whether any edge can still be relaxed after n−1 iterations.

Question 4

What is the time complexity of BFS on a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

BFS visits each vertex and each edge at most once, giving O(V + E) time complexity.

Question 5

Which algorithm is used to find the Minimum Spanning Tree of a graph by adding the cheapest edge that doesn't form a cycle?

Accepted Answer

Kruskal's Algorithm

Answer

Kruskal's algorithm builds the MST by sorting all edges by weight and adding the smallest edge that connects two different components.

Algorithms Practice Test