Graph Representation

Overview

A graph is a collection of nodes, called vertices, connected by edges. Graphs can represent relationships between entities, like social networks, road maps, or computer networks. There are two main ways to represent graphs in code: adjacency lists and adjacency matrices.

Adjacency List

An adjacency list stores the graph as an array or dictionary where each vertex maps to a list of its neighboring vertices. This representation is space-efficient for sparse graphs and makes it easy to iterate through all neighbors of a vertex.

Adjacency Matrix

An adjacency matrix is a 2D array where the entry at row i and column j indicates whether an edge exists between vertices i and j. This makes checking for an edge very fast, but uses more memory for sparse graphs.

Directed vs Undirected

In an undirected graph, edges go both ways. In a directed graph, edges have a direction from one vertex to another. The representation method handles both types, with directed graphs only storing edges in one direction.

Weighted Graphs

When edges have associated weights or costs, the representation stores these values too. In adjacency lists, each neighbor entry includes the weight. In adjacency matrices, the entry stores the weight instead of just a boolean.

Choosing a Representation

Adjacency lists are generally preferred for most algorithms because they are space-efficient and make traversal easy. Adjacency matrices are better when you need to frequently check if specific edges exist or when working with dense graphs.