Chapter quiz · Graphs

Test what you learned.

8 questions on Graphs. Pass 70% to clear the chapter.

← Review chapter lessons

Quiz

Graphs — Chapter Quiz

Eight questions on graph representations, BFS shortest path, topo sort, Dijkstra, Bellman-Ford, MST, and union-find.

0/ 9
  1. Question 1
    1

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

  2. Question 2
    2

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

  3. Question 3
    3

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

  4. Question 4
    4

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

  5. Question 5
    5

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

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

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

  8. Question 8
    8

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

    Select all that apply.

Pick an answer — instant feedback as you go.