Adjacency List vs Matrix: Understanding Graph Representations Quiz

Explore the key differences between adjacency lists and matrices in graph representations with this engaging quiz. Designed for beginners, these questions cover space complexity, edge handling, and practical use-cases in undirected and directed graphs.

1. Space Efficiency in Sparse Graphs

   Which graph representation typically uses less memory in a sparse graph with many vertices but few edges?

   1. Edge Table
   2. Adjacency Matrix
   3. Incidence Matrix
   4. Adjacency List

   Explanation: An adjacency list only stores edges that actually exist, making it more space-efficient for sparse graphs. An adjacency matrix uses space for every possible edge, even if most do not exist, resulting in wasted memory. An incidence matrix is more efficient than a matrix in some cases but is not typically as compact as an adjacency list for sparse graphs. An edge table is not a standard representation for this context.

2. Determining Edge Existence Speed

   If you want to quickly check if an edge exists between two vertices in a dense graph, which representation is usually faster?

   1. Matrix List
   2. Adjacency Matrix
   3. Adjency List
   4. Adjacency Tree

   Explanation: An adjacency matrix allows you to check for an edge in constant time by directly accessing its cell. An Adjency List (note the typo) requires searching through a list, which is slower. Matrix List and Adjacency Tree are not standard, recognized representations for this task.

3. Handling Weighted Edges

   How are weighted edges usually represented in an adjacency matrix for a weighted graph?

   1. Each cell stores a count of edges
   2. Cells store the edge weights
   3. Weights are ignored in matrices
   4. Cells store only 0 or 1

   Explanation: In a weighted graph, each entry in an adjacency matrix stores the weight of the edge if it exists. Using only 0 or 1 would lose the weight information. Weights are not ignored in matrices; instead, the actual value is used. Storing a count of edges is not standard for typical adjacency matrices.

4. Listing All Outgoing Neighbors

   Which representation makes it easier to efficiently list all outgoing neighbors of a given vertex in a directed graph?

   1. Sequence List
   2. Adjacency Matrix
   3. Edge Matrix
   4. Adjacency List

   Explanation: An adjacency list allows direct access to the list of neighbors for each vertex, making enumeration easy. With an adjacency matrix, you have to scan the entire row to find neighbors, which is less efficient. Edge Matrix and Sequence List are not typical names for standard representations.

5. Best for Dense Graphs

   When should you prefer using an adjacency matrix instead of an adjacency list?

   1. When the graph is dense
   2. When the graph has no edges
   3. When storing strings as vertices
   4. When vertices rarely change

   Explanation: Adjacency matrices are more efficient for dense graphs because the space overhead is less significant, and checking for an edge is very fast. For graphs with few or no edges, a matrix wastes memory. Whether the vertices change rarely is not a deciding factor, and storing strings as vertices is unrelated to the representation choice.

6. Effect on Space Complexity

   What is the space complexity of an adjacency matrix for a graph with n vertices?

   1. O(n^2)
   2. O(n)
   3. O(e)
   4. O(log n)

   Explanation: An adjacency matrix uses O(n^2) space since it needs to store the connection status between every pair of n vertices. O(n) and O(e) are the space complexities for adjacency lists in sparse graphs, and O(log n) is incorrect for either representation.

7. Self-loops Representation

   How is a self-loop (an edge from a vertex to itself) represented in an adjacency matrix?

   1. By a nonzero value in the last column only
   2. By a zero in every cell
   3. By a nonzero value on the main diagonal
   4. Self-loops cannot be represented

   Explanation: Self-loops appear as nonzero entries (such as 1 or the weight) on the diagonal of the matrix. Setting every cell to zero eliminates all edges, and the last column has no special status. Self-loops can indeed be represented in both matrices and lists.

8. Directed Edge Representation Difference

   How does an adjacency matrix show the difference between directed and undirected edges?

   1. Directed graphs use different sizes of matrices
   2. Undirected graphs leave matrices empty
   3. The matrix is not always symmetric for directed graphs
   4. Symmetry is required for all graphs

   Explanation: For undirected graphs, adjacency matrices are symmetric, while for directed graphs, only one entry is filled for each edge, making the matrix asymmetric in general. Symmetry is not required for all graphs, only undirected ones. The size of the matrix remains n by n for both types. Matrices for undirected graphs are not empty.

9. Counting Total Number of Edges in a List

   How can you determine the total number of edges in an undirected graph stored as an adjacency list?

   1. Count all entries in all lists and divide by 2
   2. Multiply the number of vertices by 2
   3. Sum the diagonal elements only
   4. Count each list once

   Explanation: Since each edge is stored twice (once at each endpoint) in the adjacency list for undirected graphs, you count all entries and divide by two to get the correct edge count. Counting each list once will overcount, summing diagonal elements ignores edges not involving self-loops, and multiplying the number of vertices by two does not return correct results unless every vertex is connected to exactly two others.

10. Adding and Removing Edges

    Which representation is usually faster for adding or removing an edge in a mutable, sparse graph?

    1. Adjacency List
    2. Distance Matrix
    3. Path Table
    4. Adjacency Matrix

    Explanation: In an adjacency list, adding or removing an edge involves updating a small list, typically taking less time in sparse graphs. With an adjacency matrix, modification requires changing a specific cell, but adjacency lists are more efficient with less memory overhead in sparse graphs. Path Table and Distance Matrix are either not standard or used in other contexts.