Algorithms Graph Algorithms & Traversal 2

Question 1

Which algorithm finds all strongly connected components in a directed graph in O(V + E) time?

Accepted Answer

Kosaraju's

Answer

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?

Accepted Answer

Stack

Answer

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?

Accepted Answer

All-pairs shortest path

Answer

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?

Accepted Answer

Its vertices can be split into two sets with edges only between sets

Answer

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?

Accepted Answer

Less memory usage

Answer

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².

Algorithms Practice Test