Data Structures u0026 Algorithms: Graph Algorithms and Structures Quiz

Challenge your knowledge of core graph data structures and advanced algorithms with these thought-provoking questions designed for experienced learners.

1. Adjacency Matrix vs. List Efficiency

   Given a sparse undirected graph with 10,000 vertices and 15,000 edges, which representation consumes less space and offers faster iteration over neighbors of a vertex?

   1. Adjacency Matrix is more space-efficient but slower for neighbor queries.
   2. Adjacency Matrix is better in both space and iteration speed.
   3. Adjacency List is always slower than the Adjacency Matrix.
   4. Adjacency List provides less space usage and faster neighbor iteration.
   5. Adjacency Matrix and Adjacency List use equivalent space.

2. BFS Level Order Traversal

   If you perform a Breadth-First Search (BFS) traversal starting from node A in an unweighted graph, what property holds for the nodes first discovered at each level?

   1. They are at equal minimal path distance from A.
   2. They are visited in strictly decreasing order of degree.
   3. They always form a cycle with A.
   4. They are on the same connected component only if the graph is directed.
   5. They are visited in topological order.

3. DFS Application - Cycle Detection

   In a directed graph, how can Depth-First Search (DFS) be used to detect cycles, and what must be tracked for correct detection?

   1. Apply BFS instead for cycle detection.
   2. Track only the visited nodes globally.
   3. Monitor successors in a queue to find cycles.
   4. Track the recursion stack to detect a back edge during DFS.
   5. Use only degree counts to identify cycles.

4. Topological Sort Prerequisites

   Which property must hold true for a directed graph in order for a topological ordering to exist, for example in task scheduling scenarios?

   1. The graph must be Eulerian.
   2. The graph must be connected and undirected.
   3. The graph must be weighted with nonnegative edges.
   4. The graph must be acyclic with all edges directed.
   5. All vertices must have an out-degree at least 2.

5. Dijkstra's Limitation with Negative Weights

   Why is Dijkstra's shortest path algorithm incorrect on graphs containing negative edge weights, even if no negative cycles exist?

   1. Because it ignores edge directions entirely.
   2. Because it creates cycles when updating node distances.
   3. Because it always works with negative weights.
   4. Because it must visit all nodes before producing any output.
   5. Because it assumes once a node's shortest path is found, it cannot be improved later.

6. Bellman-Ford Algorithm Output

   Given a directed graph with 'n' vertices and possible negative edge weights but no negative cycles, what does the Bellman-Ford algorithm guarantee after (n-1) relaxations?

   1. Correct shortest path distances from the source to all other vertices.
   2. An Eulerian path, if one exists.
   3. The longest paths from the source to all vertices.
   4. A minimum spanning tree of the graph.
   5. A valid topological sort of the vertices.

7. Floyd-Warshall's Core Principle

   Which principle does Floyd-Warshall's all-pairs shortest path algorithm use to incrementally build solutions, as demonstrated when updating distance(i, j) via possible intermediate vertices?

   1. Divide and conquer splitting the graph in half.
   2. Dynamic programming with repeated state updates using intermediate nodes.
   3. Heap-based edge selection for every update.
   4. Backtracking on all possible path combinations.
   5. Greedy selection of minimum weight edges iteratively.

8. Kruskal's Edge Selection Sequence

   When applying Kruskal's algorithm to construct a Minimum Spanning Tree for a weighted undirected graph, which of the following steps ensures a valid solution?

   1. Use BFS to add edges in level order.
   2. Select the highest-weight edge first and recurse.
   3. Add any random edge until all vertices are included.
   4. Sort all edges by increasing weight and add them if they don't create a cycle.
   5. Sort vertices by degree, then add their lowest edge.

9. Prim's Algorithm Priority Structure

   When running Prim's algorithm to grow a Minimum Spanning Tree from a starting vertex, which data structure most efficiently tracks and updates the nearest neighbors to the growing tree?

   1. A binary min-heap or priority queue maintaining candidate edges.
   2. A hash table keyed by vertex degree.
   3. A stack to allow backtracking from leaves.
   4. A simple array of visited flags only.
   5. A recursion stack used for DFS cleaning.

10. Comparing Adjacency Representation Operations

    Which operation is typically faster using an adjacency matrix than an adjacency list for a graph with 'n' vertices and 'e' edges?

    1. Listing all neighbors of a vertex.
    2. Checking the existence of an edge between two given vertices.
    3. Iterating over all outgoing edges efficiently.
    4. Finding the degree of every vertex.
    5. Reducing space for sparse graphs.