Representation of Graphs

Introduction

Graphs can be represented in different ways depending on the application. Each representation has trade-offs in terms of space complexity, time complexity, and ease of implementation.

Methods of Representation

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

1. Adjacency Matrix

Definition

An adjacency matrix is a 2D array A of size n×n, where n is the number of vertices.

For undirected graph:

• A[i][j] = 1 if there is an edge between vertices i and j
• A[i][j] = 0 otherwise

For weighted graph:

• A[i][j] = weight of edge (i,j)
• A[i][j] = ∞ or 0 if no edge

Example 1: Undirected Graph

Graph:

1 --- 2
|     |
3 --- 4

Adjacency Matrix:

   1  2  3  4
1 [0  1  1  0]
2 [1  0  0  1]
3 [1  0  0  1]
4 [0  1  1  0]

Properties:

• Symmetric matrix (A[i][j] = A[j][i])
• Diagonal is 0 (no self-loops)
• Row sum = degree of vertex

Example 2: Directed Graph

Graph: 1 → 2 → 3 → 1

Adjacency Matrix:

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

Example 3: Weighted Graph

Graph: 1 —5— 2 —7— 4, 1 —3— 3 —2— 4

Adjacency Matrix:

   1  2  3  4
1 [0  5  3  0]
2 [5  0  0  7]
3 [3  0  0  2]
4 [0  7  2  0]

Operations with Adjacency Matrix

Check if edge (i,j) exists: O(1) Find all neighbors of vertex i: O(n) Add edge (i,j): O(1) Remove edge (i,j): O(1)

Space Complexity

Space: O(n²) - always, regardless of number of edges

Advantages

1. Fast edge lookup: O(1)
2. Easy to implement
3. Edge addition/removal: O(1)
4. Good for dense graphs

Disadvantages

1. Space inefficient: O(n²) even for sparse graphs
2. Finding neighbors: O(n) time
3. Not scalable for very large graphs

When to Use

• Dense graphs (many edges)
• Frequent edge queries
• Small graphs (hundreds of vertices)

2. Adjacency List

Definition

An adjacency list represents a graph as an array of lists. For each vertex, store a list of its adjacent vertices.

Example 1: Undirected Graph

Graph:

1 --- 2
|     |
3 --- 4

Adjacency List:

1: [2, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3]

Example 2: Directed Graph

Graph: 1 → 2 → 3 → 1

Adjacency List:

1: [2]
2: [3]
3: [1]

Example 3: Weighted Graph

Adjacency List (with weights):

1: [(2,5), (3,3)]
2: [(1,5), (4,7)]
3: [(1,3), (4,2)]
4: [(2,7), (3,2)]

Operations with Adjacency List

Check if edge (i,j) exists: O(deg(i)) Find all neighbors of vertex i: O(1) to access, O(deg(i)) to iterate Add edge (i,j): O(1) Remove edge (i,j): O(deg(i)) Find degree of vertex i: O(1)

Space Complexity

For undirected graph: O(V + E) For directed graph: O(V + E)

Where V = vertices, E = edges

Advantages

1. Space efficient: O(V + E) - great for sparse graphs
2. Fast neighbor iteration: O(deg(v))
3. Easy to add edges
4. Scalable to large graphs

Disadvantages

1. Edge lookup slower: O(deg(v)) vs O(1) for matrix
2. Removing edges slower
3. More complex implementation

When to Use

• Sparse graphs (few edges)
• Large graphs (thousands/millions of vertices)
• Frequent neighbor iterations (BFS, DFS)
• Real-world networks (social, web, roads)

3. Edge List

Definition

Simply store all edges as a list of pairs.

Example

Graph: 1 --- 2, 1 --- 3, 2 --- 4, 3 --- 4

Edge List:

[(1,2), (1,3), (2,4), (3,4)]

For weighted:

[(1,2,5), (1,3,3), (2,4,7), (3,4,2)]

Space Complexity

Space: O(E) - most compact!

Advantages

1. Most compact: O(E) space
2. Simple to implement
3. Efficient for edge iterations
4. Good for algorithms that process all edges

Disadvantages

1. Very slow for vertex operations
2. Edge lookup: O(E)
3. Finding neighbors: O(E)

When to Use

• Algorithms that process all edges (Kruskal’s MST)
• Very sparse graphs
• Simple storage

Comparison Summary

Dense vs. Sparse Graphs

Dense graph: E ≈ V²

• Use: Adjacency Matrix

Sparse graph: E ≈ V

• Use: Adjacency List

Key Points for Exams

1. Adjacency matrix: O(V²) space, O(1) edge check
2. Adjacency list: O(V+E) space, O(deg) edge check
3. Matrix is symmetric for undirected graphs
4. List stores each edge twice in undirected graphs
5. Dense graph: matrix better
6. Sparse graph: list better
7. Edge list: simplest, O(E) space
8. Matrix good for: small, dense graphs
9. List good for: large, sparse graphs
10. Row sum in matrix: vertex degree

Practice Problems

1. Draw adjacency matrix for K₄

2. Draw adjacency list for graph with edges: {1,2}, {2,3}, {3,4}, {4,1}, {1,3}

3. Graph has 100 vertices and 200 edges. Compare space usage of matrix vs list.

4. Convert adjacency matrix to list: [[0,1,1,0], [1,0,1,1], [1,1,0,1], [0,1,1,0]]

5. What is time complexity to find all edges in adjacency list?

6. For directed graph with edge (1→2), what does A[1][2] contain?

7. Why is adjacency list better for BFS/DFS?

8. Graph has edge list [(1,2), (2,3), (3,1)]. How to check if (1,3) exists?

9. In adjacency matrix of undirected graph, what is relationship between A[i][j] and A[j][i]?

10. Calculate space ratio: (adjacency list) / (adjacency matrix) for V=1000, E=5000