Graph Representations

We have already discussed what are graphs here. Now graph can be represented in 2ways:

1. Adjacency matrix 
2. Adjacency list

Adjacency Matrix
Undirected graph
Represent G by a nXn, n being number of vertices 0-1 matrix A,
where Aij = 1 for every edge between 2 nodes.

Undirected graph with parallel edges
Aij = b*1 where b is number of parallel edges between i and j.

Weighted Undirected graph
Aij = w for every edge between 2 nodes with weight w

Directed graph
Aij = +1 if edge goes from node i to j, similarly for edge from j to i, it is -1.

Space Complexity
Space required by adjacency matrix is θ (n²), no matter how many edges the graph has. In case of sparse graph it is super-wasteful implementation.

Adjacency lists
Adjacency lists contains:

• array or list of vertices
• array or list of edges
• each edge points to its end points - i.e. each edge will have 2 end points
• each vertex points to edges incident on it.

Space Complexity

Space required by adjacency list is θ (m+n) OR θ(|V|=|E|).

Which method to use?
It depends on 2 items:

1. Density of the graph
2. Operations needed

Usage of adjacency list : 

For sparse matrix, there is lots of space wastage if we use Adjacency matrix, hence we use adjacency list method. In case of Operations we deal with, for graph search operations, adjacency lists suits more as it fast to iterate over adjacency list, but slow when finding the presence or absence of any edge.  

Usage of adjacency matrix:

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.