Data Structures for Graph Representation

Graphs can be represented in different ways based on efficiency, space complexity, and ease of access. The three primary methods used for graph representation are:

🔹 1. Adjacency Matrix

An adjacency matrix is a 2D array where:

• Rows & columns represent vertices.
• A cell (i, j) stores a value indicating whether an edge exists between vertex i and vertex j.

✅ Properties:

✔ Fast edge lookup: Checking if an edge exists is O(1).
✔ Simple implementation.
❌ Space Complexity: O(V²) (not suitable for sparse graphs).

📌 Example:

For a graph with 4 vertices:

  0  1  2  3
0 0  1  0  1
1 1  0  1  1
2 0  1  0  1
3 1  1  1  0

(1 represents an edge, 0 means no edge).

---

🔹 2. Adjacency List

An adjacency list is an array of lists, where:

• Each index represents a vertex.
• Each index stores a list of connected vertices.

✅ Properties:

✔ Efficient for sparse graphs (O(V + E) space complexity).
✔ Faster traversal for large graphs.
❌ Edge lookup is O(V) in the worst case.

📌 Example:

For a graph:

0 → [1, 3]  
1 → [0, 2, 3]  
2 → [1, 3]  
3 → [0, 1, 2]  

(Each vertex stores a list of its neighbors).

---

🔹 3. Incidence Matrix

An incidence matrix is a V × E matrix where:

• Rows represent vertices.
• Columns represent edges.
• Each cell (i, j) indicates whether vertex i is part of edge j.

✅ Properties:

✔ Useful in graph theory applications.
✔ Can represent both directed and undirected graphs.
❌ Takes more space (O(V × E)).

📌 Example:

For a graph with edges: (0-1), (1-2), (2-3), (3-0), (1-3)

  e1 e2 e3 e4 e5
0  1  0  0  1  0
1  1  1  0  0  1
2  0  1  1  0  0
3  0  0  1  1  1

(1 means the vertex is part of the edge).

---

Which Representation to Use? 🤔

• ✅ Adjacency Matrix: Best for dense graphs & fast edge lookup.
• ✅ Adjacency List: Best for sparse graphs & efficient traversal.
• ✅ Incidence Matrix: Used in specific graph problems (e.g., edge-centric algorithms).