Algorithms Graph Algorithms & Traversal 2 — Questions and Answers
Question 1: Which algorithm finds all strongly connected components in a directed graph in O(V + E) time?
- Floyd-Warshall
- Dijkstra's
- Kosaraju's (Correct answer)
- Prim's
Correct answer: Kosaraju's
Kosaraju's algorithm performs two DFS passes — one on the original graph and one on its transpose — to identify all strongly connected components.
Question 2: What data structure does Depth-First Search (DFS) use implicitly through recursion?
- Queue
- Heap
- Stack (Correct answer)
- Hash Table
Correct answer: Stack
DFS uses a stack (via the call stack in recursive implementations) to track the path of exploration and backtrack when needed.
Question 3: Floyd-Warshall algorithm solves which graph problem?
- Single-source shortest path
- All-pairs shortest path (Correct answer)
- Minimum spanning tree
- Topological sort
Correct answer: All-pairs shortest path
Floyd-Warshall computes shortest paths between every pair of vertices using dynamic programming, running in O(V³) time.
Question 4: In graph theory, what does it mean for a graph to be bipartite?
- It has exactly two connected components
- Its vertices can be split into two sets with edges only between sets (Correct answer)
- Every vertex has degree 2
- It contains no cycles
Correct answer: Its vertices can be split into two sets with edges only between sets
A bipartite graph can have its vertices colored with two colors such that no two adjacent vertices share the same color.
Question 5: What is the primary advantage of using an adjacency list over an adjacency matrix for sparse graphs?
- Faster edge lookup
- Less memory usage (Correct answer)
- Simpler implementation
- Better cache performance
Correct answer: Less memory usage
Adjacency lists use O(V + E) space compared to O(V²) for a matrix, making them far more efficient for sparse graphs where E << V².
Question 6: Which graph algorithm uses a priority queue and is suitable for finding shortest paths in graphs with non-negative weights?
- Bellman-Ford
- BFS
- Dijkstra's (Correct answer)
- DFS
Correct answer: Dijkstra's
Dijkstra's algorithm uses a min-priority queue to always expand the closest unvisited vertex, ensuring correctness with non-negative weights.
Algorithms Graph Algorithms & Traversal 2
Which algorithm finds all strongly connected components in a directed graph in O(V + E) time?