Graph representations (adjacency matrix vs list) in Data Structures Theory - Quick Revision & Key Differences

Recall & Review

beginner

What is an adjacency matrix in graph representation?

An adjacency matrix is a 2D array where each cell at row i and column j indicates if there is an edge between vertex i and vertex j. It uses rows and columns to represent connections.

beginner

What is an adjacency list in graph representation?

An adjacency list represents a graph by storing a list of neighbors for each vertex. Each vertex has a list of vertices it connects to, making it efficient for sparse graphs.

intermediate

Which graph representation uses more memory for large sparse graphs: adjacency matrix or adjacency list?

Adjacency matrix uses more memory for large sparse graphs because it stores information for every possible edge, even if many edges don't exist. Adjacency list only stores existing edges.

intermediate

How does checking if an edge exists differ between adjacency matrix and adjacency list?

In an adjacency matrix, checking if an edge exists is fast and direct by looking up the cell. In an adjacency list, you may need to search through the list of neighbors, which can be slower.

beginner

When is it better to use an adjacency list over an adjacency matrix?

Use an adjacency list when the graph has few edges compared to the number of vertices (sparse graph). It saves memory and is efficient for iterating over neighbors.

Which graph representation uses a 2D array to store edges?

A Adjacency matrix

B Adjacency list

C Edge list

D Incidence matrix

An adjacency matrix uses a 2D array where rows and columns represent vertices and cells indicate edges.

Which representation is more memory efficient for a graph with very few edges?

A Adjacency matrix

B Adjacency list

C Both use the same memory

D None of the above

Adjacency lists store only existing edges, so they use less memory for sparse graphs.

How do you check if an edge exists between two vertices in an adjacency matrix?

A Look up the cell at row i and column j

B Search the list of neighbors for vertex i

C Count the total edges

D Check the degree of vertex j

In an adjacency matrix, the presence of an edge is directly indicated by the value in the cell at row i and column j.

Which graph representation is better for quickly iterating over all neighbors of a vertex?

A Adjacency matrix

B Edge list

C Adjacency list

D None of the above

Adjacency lists store neighbors directly, making iteration over them faster and more efficient.

What is a disadvantage of using an adjacency matrix?

A Does not support weighted edges

B Cannot represent directed graphs

C Edges are hard to find

D Uses a lot of memory for large graphs

Adjacency matrices use memory for every possible edge, which can be large for big graphs, especially if many edges are missing.

Explain the difference between adjacency matrix and adjacency list in graph representation.

Think about how each stores connections and when each is useful.

When would you choose an adjacency list over an adjacency matrix? Give reasons.

Consider the number of edges compared to vertices.

Practice

1. Which graph representation uses a 2D grid to show connections between nodes?

easy

A. Incidence matrix

B. Adjacency matrix

C. Edge list

D. Adjacency list

Solution

1. Step 1: Understand adjacency matrix structure

   An adjacency matrix is a 2D grid where rows and columns represent nodes, and cells show if an edge exists.

2. Step 2: Compare with other representations

   Adjacency lists store neighbors in lists, not grids. Edge lists and incidence matrices differ in format.

3. Final Answer:

   Adjacency matrix -> Option B

4. Quick Check:

   2D grid = adjacency matrix [OK]

Hint: Matrix means grid; list means neighbors [OK]

Common Mistakes:

• Confusing adjacency list with matrix
• Thinking edge list is a grid
• Mixing incidence matrix with adjacency matrix

2. Which of the following is the correct way to represent an adjacency list in Python?

easy

A. graph = [[1, 2], 0, [0, 1]]

B. graph = [[0,1,0],[1,0,1],[0,1,0]]

C. graph = [(0,1), (1,2), (2,0)]

D. graph = {0: [1, 2], 1: [0], 2: [0, 1]}

Solution

1. Step 1: Identify adjacency list format

   An adjacency list maps each node to a list of its neighbors, often using a dictionary in Python.

2. Step 2: Check each option

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} uses a dictionary with keys as nodes and values as neighbor lists, which is correct. graph = [[0,1,0],[1,0,1],[0,1,0]] is a matrix, C is an edge list, D incorrectly uses an integer 0 for node 1 instead of a list.

3. Final Answer:

   graph = {0: [1, 2], 1: [0], 2: [0, 1]} -> Option D

4. Quick Check:

   Dict with neighbors = adjacency list [OK]

Hint: Adjacency list uses dict with node keys [OK]

Common Mistakes:

• Choosing matrix format as list
• Confusing edge list with adjacency list
• Using integer instead of list for neighbors

3. Given the adjacency matrix below, which nodes are connected to node 1?
graph = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

medium

A. Nodes 0 and 2

B. Nodes 1 and 2

C. Nodes 0 and 1

D. Nodes 2 only

Solution

1. Step 1: Locate row for node 1

   Row 1 in the matrix is [1, 0, 1], representing edges from node 1 to nodes 0, 1, and 2.

2. Step 2: Identify connected nodes

   Values 1 indicate connection. Here, positions 0 and 2 have 1, so node 1 connects to nodes 0 and 2.

3. Final Answer:

   Nodes 0 and 2 -> Option A

4. Quick Check:

   Row 1 has 1s at 0 and 2 [OK]

Hint: Check row for node, 1 means connected [OK]

Common Mistakes:

• Confusing row and column indices
• Including node itself as connected
• Misreading zeros as edges

4. What is wrong with this adjacency list representation?
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: 1}

medium

A. Node 3's neighbors should be in a list

B. Node 1 has an invalid neighbor

C. Node 0 should not have neighbors

D. The graph should be an adjacency matrix

Solution

1. Step 1: Check format of neighbors for each node

   Nodes 0, 1, and 2 have neighbor lists. Node 3 has a single integer instead of a list.

2. Step 2: Identify correct adjacency list format

   Neighbors must always be in a list, even if only one neighbor exists, to keep consistent structure.

3. Final Answer:

   Node 3's neighbors should be in a list -> Option A

4. Quick Check:

   Neighbors must be lists [OK]

Hint: Neighbors always in lists, never single values [OK]

Common Mistakes:

• Ignoring single neighbor format
• Thinking adjacency list must be matrix
• Assuming neighbors can be integers

5. For a graph with 1000 nodes and only 10,000 edges, which representation is more memory efficient and why?

hard

A. Adjacency matrix, because it allows faster edge checks

B. Adjacency matrix, because it uses fixed size memory

C. Adjacency list, because it stores only existing edges

D. Adjacency list, because it stores all possible edges

Solution

1. Step 1: Calculate memory use for adjacency matrix

   An adjacency matrix for 1000 nodes uses 1000x1000 = 1,000,000 cells, regardless of edges.

2. Step 2: Calculate memory use for adjacency list

   An adjacency list stores only the 10,000 edges, so memory use is proportional to edges, much less than matrix.

3. Step 3: Compare efficiency

   Since edges are sparse compared to possible connections, adjacency list is more memory efficient.

4. Final Answer:

   Adjacency list, because it stores only existing edges -> Option C

5. Quick Check:

   Sparse graph = adjacency list efficient [OK]

Hint: Sparse graph? Use adjacency list for less memory [OK]

Common Mistakes:

• Choosing matrix for sparse graphs
• Confusing speed with memory use
• Thinking adjacency list stores all edges