---

Graphs Representation

A Graph ( G = (V, E) ) is a collection of:

• Vertices (Nodes) → V
• Edges (Connections) → E

To store a graph in memory, we need efficient representations that allow fast traversal, search, and other operations.

There are three primary ways to represent graphs:

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

Let’s discuss each one in detail.

---

1. Adjacency Matrix Representation

An Adjacency Matrix is a 2D array (matrix) of size V × V, where each cell A[i][j] tells whether an edge exists between vertex i and j.

---

1.1 Definition

For a graph with vertices V:

[
Adj[i][j] =
\begin{cases}
1 & \text{if edge (i,j) exists} \
0 & \text{otherwise}
\end{cases}
]

For weighted graphs:

[
Adj[i][j] = w(i,j)
]

where w = weight of the edge.

---

1.2 Example

Vertices: {0, 1, 2}

Edges: (0,1), (1,2)

Adjacency Matrix:

    0 1 2
  --------
0 | 0 1 0
1 | 1 0 1
2 | 0 1 0

---

1.3 Advantages

✔ Very simple and easy
✔ Edge existence check = O(1)
✔ Good for dense graphs
✔ Perfect for matrix-based algorithms (Floyd–Warshall)

---

1.4 Disadvantages

✘ Uses O(V²) space always
✘ Inefficient for sparse graphs
✘ Iterating all neighbors takes O(V)

---

1.5 Best Use Cases

• Dense graphs (many edges)
• Weighted adjacencies
• Graph algorithms using matrices

---

2. Adjacency List Representation

The Adjacency List is the most common and efficient representation for graphs.

---

2.1 Definition

Each vertex stores a list of all vertices to which it has outgoing edges.

Example using lists:

0 → 1
1 → 0 → 2
2 → 1

---

2.2 Structure

You can implement adjacency list using:

• Array of linked lists
• Array of dynamic lists (vector)
• Hash maps (for large/labelled nodes)

---

2.3 Example

Graph: 0—1—2

Adjacency List:

0: 1
1: 0, 2
2: 1

Directed graph example:

0: 1
1: 2
2: (none)

---

2.4 Advantages

✔ Space efficient → O(V + E)
✔ Perfect for sparse graphs
✔ Easy to traverse neighbors
✔ Fast for BFS/DFS
✔ Edge insertion = O(1)

---

2.5 Disadvantages

✘ Checking edge existence = O(deg(v))
✘ Not suitable for dense graphs
✘ Requires dynamic memory structures

---

2.6 Best Use Cases

• Sparse graphs
• Large real-world graphs
• BFS, DFS, Dijkstra (with priority queue)

---

3. Incidence Matrix Representation

An Incidence Matrix is a 2D matrix of size V × E.

It shows the relationship between vertices and edges.

---

3.1 Definition

For each vertex i and edge ej:

[
Inc[i][j] =
\begin{cases}
1 & \text{if vertex i is incident to edge ej} \
-1 & \text{(directed) if vertex i is starting of ej} \
1 & \text{(directed) if vertex i is ending of ej} \
0 & \text{otherwise}
\end{cases}
]

---

3.2 Example

Graph: Edge e1 = (0,1), Edge e2 = (1,2)

Incidence Matrix:

      e1  e2
    ---------
0 |   1   0
1 |   1   1
2 |   0   1

For directed graphs:

0 → 1 (e1)
1 → 2 (e2)

      e1  e2
    ---------
0 |  -1   0
1 |   1  -1
2 |   0   1

---

3.3 Advantages

✔ Useful in mathematical graph theory
✔ Good for network flow algorithms
✔ Good for matrix-based computations

---

3.4 Disadvantages

✘ Space = O(V × E) (huge!)
✘ Not intuitive
✘ Inefficient for large graphs

---

4. Summary Comparison

Method	Space	Edge Check	Best For
Adjacency Matrix	O(V²)	O(1)	Dense graphs
Adjacency List	O(V+E)	O(degree(v))	Sparse graphs, practical use
Incidence Matrix	O(V×E)	O(E)	Theoretical/mathematical use

---

5. Additional Representations (Advanced)

A. Edge List

A list of all edges:

[(u1, v1), (u2, v2), ...]

Used in Kruskal’s algorithm.

B. Compressed Sparse Row (CSR)

Used for storing huge sparse graphs (e.g., social networks).
Efficient for GPU-based graph processing.

---

6. Which Representation to Choose?

Scenario	Recommended
Sparse graph (E ≪ V²)	Adjacency List
Dense graph (E ≈ V²)	Adjacency Matrix
Fast edge lookup	Adjacency Matrix
Fast traversal	Adjacency List
Mathematical algorithms	Incidence Matrix
Kruskal’s MST	Edge List

---

Summary

A graph can be represented in various ways:

1. Adjacency Matrix:

2D matrix → simple, O(V²) space, constant-time edge check.

2. Adjacency List:

List for each vertex → space-efficient (O(V+E)), used in most graph algorithms.

3. Incidence Matrix:

Matrix of vertices vs edges → used mainly in theoretical graph processing.

---