Graphs — Chapter Quiz · Data Structures & Algorithms

Question 1

1

Which graph representation is most space-efficient for a sparse graph (few edges relative to vertices)?

AAdjacency matrixBAdjacency listCEdge list sorted by source vertexDIncidence matrix

An adjacency matrix costs O(V²) space regardless of edge count. An adjacency list costs O(V + E), which is much smaller for sparse graphs where E ≪ V².

Question 2

2

BFS on an unweighted graph gives the shortest path (in terms of edge count) because:

AIt visits nodes in alphabetical orderBIt explores nodes level by level — all distance-d nodes are fully explored before any distance-(d+1) node is visitedCIt uses a priority queue to order nodes by distanceDIt backtracks and tries all possible paths

BFS expands outward in waves of increasing distance. The first time a node is dequeued, it has been reached via the shortest path. This guarantee breaks when edges have different weights.

Question 3

3

Kahn's algorithm for topological sort uses which data structure to track vertices with in-degree zero?

AMin-heap ordered by vertex labelBQueue (or stack) of in-degree-zero verticesCDFS recursion stackDUnion-find structure

Kahn's algorithm starts by enqueuing all vertices with in-degree zero. After processing each vertex its outgoing edges are removed, decrementing neighbour in-degrees — newly zero-in-degree vertices join the queue. O(V + E) overall.

Question 4

4

Why can't Dijkstra's algorithm handle negative edge weights correctly?

AIt only works on directed graphsBOnce a node is finalized (popped from the priority queue) Dijkstra assumes its shortest distance is settled — a negative edge could later offer a shorter pathCDijkstra uses BFS internally which ignores weightsDNegative weights cause an integer overflow

Dijkstra's greedy relaxation relies on the invariant that the smallest unvisited distance is already optimal. A negative edge can violate this, requiring a node to be re-processed. Use Bellman-Ford for graphs with negative edges.

Question 5

5

What is the time complexity of the Bellman-Ford algorithm for a graph with V vertices and E edges?

AO((V + E) log V)BO(V · E)CO(E log E)DO(V²)

Bellman-Ford relaxes all E edges V-1 times (V-1 rounds guarantee shortest paths for graphs without negative cycles), totalling O(V · E). A V-th round that still relaxes an edge indicates a negative cycle.

Question 6

6

Prim's and Kruskal's algorithms both find a Minimum Spanning Tree (MST) but use different strategies — Prim's grows the tree vertex by vertex, while Kruskal's adds the cheapest safe edge globally.

TTrueFFalse

Prim's is greedy on vertices (like Dijkstra but for MST); Kruskal's is greedy on edges, sorting all edges by weight and using union-find to skip those that would form a cycle. Both produce a valid MST of total weight Σ minimum edge weights.

Question 7

7

Union-Find (Disjoint Set Union) with path compression and union by rank performs each operation in nearly O(1) amortized time, specifically O(α(n)) where α is the ___ function.

α(n) is the inverse Ackermann function — effectively ≤ 4 for any realistic input size. Path compression flattens the tree on each find; union by rank keeps trees shallow, together achieving this near-constant amortized cost.

Question 8

8

Which of the following correctly describe BFS vs DFS trade-offs for graphs? (Select all that apply)

Select all that apply.

ABFS finds shortest paths (edge count) in unweighted graphs; DFS does not guarantee shortest pathsBDFS uses O(V) stack space (implicit call stack or explicit); BFS uses O(V) queue spaceCDFS is always faster than BFS on large graphsDDFS is used for cycle detection, topological sort, and SCC algorithms; BFS is used for shortest path and level-by-level problems

Both BFS and DFS are O(V + E) in time. Neither is inherently faster — the right choice depends on the problem. BFS shines for shortest path; DFS for topology, cycles, and SCCs.

Test what you learned.