Algorithms Graph Algorithms & Traversal 1 — Questions and Answers
Question 1: Which graph traversal algorithm uses a queue as its primary data structure?
- Depth-First Search
- Dijkstra's Algorithm
- Breadth-First Search (Correct answer)
- Prim's Algorithm
Correct answer: Breadth-First Search
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?
- Minimum spanning tree
- Shortest path from a single source (Correct answer)
- All-pairs shortest paths
- Topological order
Correct answer: Shortest path from a single source
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?
- Dijkstra's Algorithm
- Prim's Algorithm
- Bellman-Ford Algorithm (Correct answer)
- Kruskal's Algorithm
Correct answer: Bellman-Ford Algorithm
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?
- O(V²)
- O(V + E) (Correct answer)
- O(E log V)
- O(V log V)
Correct answer: O(V + E)
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?
- Dijkstra's Algorithm
- Prim's Algorithm
- Bellman-Ford Algorithm
- Kruskal's Algorithm (Correct answer)
Correct answer: Kruskal's Algorithm
Kruskal's algorithm builds the MST by sorting all edges by weight and adding the smallest edge that connects two different components.
Question 6: In a directed graph, what is a topological sort?
- Sorting vertices by degree
- Ordering vertices so every edge points from earlier to later (Correct answer)
- Finding the shortest path
- Identifying strongly connected components
Correct answer: Ordering vertices so every edge points from earlier to later
A topological sort orders vertices such that for every directed edge u→v, u appears before v in the ordering.
Algorithms Graph Algorithms & Traversal 1
Which graph traversal algorithm uses a queue as its primary data structure?