Graph representations (adjacency matrix vs list) in Data Structures Theory - Key Differences Explained

Introduction

Imagine you want to keep track of connections between places or friends. Choosing the right way to store these connections can make finding and using them much easier and faster.

Explanation

Adjacency Matrix

An adjacency matrix uses a square grid to show connections between nodes. Each row and column represents a node, and the cell where they meet shows if there is a connection. This makes it quick to check if two nodes are connected, but it uses a lot of space, especially if there are few connections.

Adjacency matrix is a grid that quickly shows if two nodes are connected but can waste space for sparse graphs.

Adjacency List

An adjacency list keeps a list for each node showing only the nodes it connects to. This saves space when there are fewer connections because it only stores existing links. However, checking if two nodes are connected can take longer since you may need to search through a list.

Adjacency list saves space by listing only existing connections but can be slower to check specific links.

When to Use Each

Use an adjacency matrix when the graph is dense, meaning many connections exist, because it allows fast lookups. Use an adjacency list when the graph is sparse, with fewer connections, to save memory and handle large graphs efficiently.

Choose adjacency matrix for dense graphs and adjacency list for sparse graphs to balance speed and memory.

Real World Analogy

Think of a city map where every street intersection is a node. An adjacency matrix is like a big table listing every possible pair of intersections and marking if a direct road connects them. An adjacency list is like having a list at each intersection showing only the streets that lead out from there.

Adjacency Matrix → A big table showing every possible pair of intersections and whether a direct road connects them

Adjacency List → A list at each intersection showing only the streets that lead out from there

When to Use Each → Choosing between a full city map table or small lists at intersections depending on how many roads exist

Diagram

Diagram

    Nodes
      0   1   2   3
  0 [0] [1] [0] [0]
  1 [1] [0] [1] [1]
  2 [0] [1] [0] [0]
  3 [0] [1] [0] [0]

Adjacency List:
0: 1
1: 0, 2, 3
2: 1
3: 1

This diagram shows a graph with four nodes represented as both an adjacency matrix and an adjacency list.

Key Facts

Adjacency Matrix → A square grid where each cell shows if a pair of nodes is connected.

Adjacency List → A list for each node showing only its connected nodes.

Dense Graph → A graph with many connections between nodes.

Sparse Graph → A graph with few connections compared to the number of nodes.

Space Complexity → How much memory a data structure uses to store information.

Code Example

Data Structures Theory

graph_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0]
]

graph_list = {
    0: [1],
    1: [0, 2, 3],
    2: [1],
    3: [1]
}

# Check if node 0 is connected to node 1 using matrix
print('Matrix:', graph_matrix[0][1] == 1)

# Check if node 0 is connected to node 1 using list
print('List:', 1 in graph_list[0])

Common Confusions

Believing adjacency matrix always uses less memory.

Believing adjacency matrix always uses less memory. Adjacency matrix uses more memory for sparse graphs because it stores all possible connections, even if many don't exist.

Thinking adjacency list is always slower to check connections.

Thinking adjacency list is always slower to check connections. Adjacency list can be fast for checking neighbors but slower than matrix for direct connection checks because it may require searching a list.

Summary

Graphs can be stored using adjacency matrices or adjacency lists, each with different strengths.

Adjacency matrices use more memory but allow quick connection checks, best for dense graphs.

Adjacency lists save memory by storing only existing connections, ideal for sparse graphs.

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