Graph Representation: Adjacency List & Adjacency Matrix

Graphs are abstract data structures consisting of nodes (vertices) connected by edges. Representing a graph in a computer efficiently is critical to perform various graph algorithms such as traversal, shortest path, and connectivity.

1. Adjacency Matrix

An adjacency matrix is a 2D array of size V x V where V is the number of vertices. The element at row i and column j is 1 (or the weight of edge) if there is an edge from vertex i to vertex j, otherwise 0.

• Simple and fast edge lookup.
• Consistent space usage: always V² space.
• Less efficient for sparse graphs due to space.

Python Example for Adjacency Matrix

def create_adj_matrix(vertices, edges):
    graph = [[0] * vertices for _ in range(vertices)]
    for (src, dst) in edges:
        graph[src][dst] = 1  # Directed graph
        # For undirected, add graph[dst][src] = 1
    return graph

vertices = 4
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
adj_matrix = create_adj_matrix(vertices, edges)

for row in adj_matrix:
    print(row)

2. Adjacency List

An adjacency list represents a graph as an array (or dictionary) of lists. Each index represents a vertex; its list contains all adjacent vertices (neighbors).

• Memory efficient for sparse graphs.
• Edge listing is direct and fast.
• Traversal and modifications are easier for large graphs.

JavaScript Example for Adjacency List

function addEdge(adj, src, dst) {
    adj[src].push(dst);
    // For undirected graph, add:
    // adj[dst].push(src);
}

const vertices = 4;
const adj = Array.from({ length: vertices }, () => []);

addEdge(adj, 0, 1);
addEdge(adj, 0, 2);
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);

adj.forEach((neighbors, vertex) => {
    console.log(vertex + ": " + neighbors.join(", "));
});

Comparison