37. Representing Graphs

How we store the graph data significantly impacts the efficiency of algorithms running on it.

1. Adjacency Matrix

• Concept: A 2D array (matrix) of size V x V, where V is the number of vertices.
• Storage: Matrix[i][j] stores a 1 (or the weight) if there is an edge from vertex i to vertex j, and 0 (or infinity) otherwise.
• Pros: Fast checking for an edge between two specific nodes (O(1)).
• Cons: Wastes a lot of space, especially for Sparse Graphs (graphs with few edges). Space complexity: O(V²).

2. Adjacency List

• Concept: An array or Hash Map where each index/key corresponds to a vertex. The value stored at that index is a list of its neighbors.
• Pros: Space efficient, especially for sparse graphs. Space complexity: O(V + E) (Vertices + Edges).
• Cons: Checking if an edge exists between two nodes requires searching the neighbor list (O(Degree of vertex)).

Rule of Thumb: Adjacency Lists are typically preferred for most real-world algorithms unless the graph is extremely dense.