Graph Representation in Data Structure – Adjacency Matrix – Adjacency List – Edge List

Graph Representation

Graphs can be represented in various ways:

1. Adjacency Matrix:

• A 2D array where A[i][j]=1(or the weight of the edge) if there is an edge between vertices i and j, otherwise A[i][j]=0.
• Space Complexity: O(V2).
• Good for dense graphs.

Matrix Representation:

The adjacency matrix is a V×V table where:

• Rows and columns represent vertices.
• 1 indicates an edge from vertex i to vertex j.
• 0 indicates no edge.

2. Adjacency List:

• An array (or list) where each element contains a list of all adjacent vertices.
• Space Complexity: O(V+E).
• Good for sparse graphs.

List Representation:

3. Edge List:

• A list of all edges, where each edge is represented as a pair (u, v) (or triplet (u, v, w) for weighted graphs) of vertices.
• Space Complexity: O(E).

List Representation: