Graph Representation Techniques

# CHAPTER 19

Graph Representation Techniques #

1. Introduction #

2. Learning Objectives #

• Construct an Adjacency Matrix using a 2D Boolean Array.

• Construct an Adjacency List using dynamic Arrays/Linked Lists.

• Calculate the catastrophic $O(V^2)$ Space Complexity of dense matrices.

• Choose the correct architecture based on "Sparse" vs "Dense" graph layouts.

3. Technique 1: The Adjacency Matrix #

• If Vertex 0 connects to Vertex 1, you put a 1 at coordinate [0][1].

• If there is no connection, you put a 0.

Example Graph: A(0) --- B(1) | | C(2) --- D(3)

Matrix Representation:

    0  1  2  3
0 [ 0, 1, 1, 0 ]   <-- Node A connects to B(1) and C(2)
1 [ 1, 0, 0, 1 ]   <-- Node B connects to A(0) and D(3)
2 [ 1, 0, 0, 1 ]   <-- Node C connects to A(0) and D(3)
3 [ 0, 1, 1, 0 ]   <-- Node D connects to B(1) and C(2)

Pros: Checking if an edge exists between A and D is lightning fast: $O(1)$. You just check matrix[0][3]. Cons (The RAM Nightmare): Space Complexity is strictly $O(V^2)$. If Facebook has 1 Billion users, building a $1B \times 1B$ matrix requires ONE QUINTILLION array slots. It would instantly consume all the server memory on Earth, mostly filled with useless 0s representing people who don't know each other!

4. Technique 2: The Adjacency List #

Example Graph (Same as above): A(0) --- B(1) | | C(2) --- D(3)

List Representation:

0 (A) -> [1, 2]
1 (B) -> [0, 3]
2 (C) -> [0, 3]
3 (D) -> [1, 2]

Pros: Space Complexity is $O(V + E)$. It only consumes RAM for edges that *actually exist*. Facebook can easily store 1 Billion users if each user only has a list of ~300 friends. Cons: Checking if an edge exists is slower. To check if A(0) connects to D(3), you must scan A's entire list [1, 2]. Time Complexity degrades to $O(K)$, where $K$ is the degree of the node.

5. Code Implementation (Java) #

import java.util.*;

class Graph {
    int V;
    LinkedList<Integer>[] adjListArray; // Array of Linked Lists

    // Constructor
    Graph(int V) {
        this.V = V;
        adjListArray = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adjListArray[i] = new LinkedList<>(); // Spawn empty lists
        }
    }

    // Add undirected edge
    void addEdge(int src, int dest) {
        adjListArray[src].add(dest); // Link src to dest
        adjListArray[dest].add(src); // Link dest to src
    }
}

6. Sparse vs. Dense Graphs #

• Sparse Graph: Very few edges relative to vertices (e.g., Social Networks). A user has 300 friends out of 1 Billion users. Always use an Adjacency List to prevent RAM crashing.

• Dense Graph: Almost every node connects to every other node (e.g., A map of major airport flights where everyone flies everywhere). Use an Adjacency Matrix to gain ultra-fast $O(1)$ query speeds since the grid is packed with 1s anyway!

7. Complexity Summary #

8. Common Mistakes #

• Forgetting the reverse edge in Undirected Graphs: If building an Adjacency List for an Undirected Graph, when connecting A to B, you MUST write list[A].add(B) AND list[B].add(A). If you forget the reverse link, you accidentally built a Directed Digraph!

9. Exercises #

1. 1. Draw the physical 2D Adjacency Matrix for a Directed Graph where A connects to B, B connects to C, and C connects to A. (Assume vertices A=0, B=1, C=2).

1. 2. Given a massive matrix size of $100,000 \times 100,000$, if the graph is extremely Sparse (only 500 total edges), exactly how many empty 0 slots are wasting RAM?

10. MCQs with Answers #

11. Interview Preparation #

• *Space Constraint Analysis:* "An interviewer asks: You are storing a graph of all 10,000 employees in a company and their reporting structure. Would you use a Matrix or a List?" *(Answer: Adjacency List! 10,000 x 10,000 creates an array of 100 Million slots! But an employee only reports to 1 boss and maybe 5 peers. The graph is extremely sparse. Using a List shrinks memory from 100M slots down to roughly 60,000 slots!)*

12. Summary #

13. Next Chapter Recommendation #