Graph Representation — Adjacency List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Graph G = (V, E) where V = {0, 1, 2, 3, 4}
 
Edges: (0,1), (0,4), (1,2), (1,3), (1,4), (2,3), (3,4)
 
Adjacency List Representation:
┌─────────┬─────────────────────────────────┐
│ Vertex  │ Neighbors (Adjacent Vertices)   │
├─────────┼─────────────────────────────────┤
│    0    │ → [1, 4]                        │
│    1    │ → [0, 2, 3, 4]                  │
│    2    │ → [1, 3]                        │
│    3    │ → [1, 2, 4]                     │
│    4    │ → [0, 1, 3]                     │
└─────────┴─────────────────────────────────┘
 
Total storage: 14 entries (7 edges × 2 for undirected)
Matrix would need: 25 cells (5 × 5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class GraphArrayBased:
    """
    Adjacency list using Python lists (dynamic arrays).
    
    This is the most common implementation:
    - graph[i] contains a list of all vertices adjacent to vertex i
    - Works for both directed and undirected graphs
    """
    
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        # Create a list of empty lists, one per vertex
        self.adj = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u: int, v: int, directed: bool = False):
        """Add edge from u to v (and v to u if undirected)."""
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)
    
    def neighbors(self, v: int) -> list[int]:
        """Return all neighbors of vertex v."""
        return self.adj[v]
    
    def has_edge(self, u: int, v: int) -> bool:
        """Check if edge (u, v) exists."""
        return v in self.adj[u]  # O(degree) time!
    
    def degree(self, v: int) -> int:
        """Return the degree of vertex v."""
        return len(self.adj[v])
 
# Example usage
g = GraphArrayBased(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
 
print(f"Neighbors of vertex 1: {g.neighbors(1)}")  # [0, 2, 3, 4]
print(f"Degree of vertex 1: {g.degree(1)}")         # 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class ListNode:
    """A node in the linked list of neighbors."""
    def __init__(self, vertex: int):
        self.vertex = vertex
        self.next = None
 
class GraphLinkedList:
    """
    Adjacency list using linked lists.
    
    Classic textbook implementation.
    Pros: Efficient insertion at head
    Cons: Poor cache locality, more memory overhead
    """
    
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        # Array of linked list heads, one per vertex
        self.adj = [None] * num_vertices
    
    def add_edge(self, u: int, v: int, directed: bool = False):
        """Add edge by prepending to the linked list (O(1) insertion)."""
        # Add v to u's list
        new_node = ListNode(v)
        new_node.next = self.adj[u]
        self.adj[u] = new_node
        
        if not directed:
            # Add u to v's list
            new_node = ListNode(u)
            new_node.next = self.adj[v]
            self.adj[v] = new_node
    
    def neighbors(self, v: int):
        """Generator that yields all neighbors of vertex v."""
        current = self.adj[v]
        while current:
            yield current.vertex
            current = current.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class GraphHashSet:
    """
    Adjacency list using hash sets.
    
    Best for algorithms that frequently check edge existence.
    Trades memory for O(1) edge lookup.
    """
    
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        # Array of sets, one per vertex
        self.adj = [set() for _ in range(num_vertices)]
    
    def add_edge(self, u: int, v: int, directed: bool = False):
        """Add edge to sets (O(1) average time)."""
        self.adj[u].add(v)
        if not directed:
            self.adj[v].add(u)
    
    def remove_edge(self, u: int, v: int, directed: bool = False):
        """Remove edge (O(1) average time)."""
        self.adj[u].discard(v)
        if not directed:
            self.adj[v].discard(u)
    
    def has_edge(self, u: int, v: int) -> bool:
        """Check edge existence in O(1) average time!"""
        return v in self.adj[u]
    
    def neighbors(self, v: int) -> set[int]:
        """Return set of neighbors (iteration order may vary)."""
        return self.adj[v]

1
2
3
4
5
6
7
8
9

Undirected graph with edges: {A-B, B-C, A-C}
 
Adjacency List:
A → [B, C]    // A connects to B and C
B → [A, C]    // B connects to A and C  
C → [A, B]    // C connects to A and B
 
Notice: Edge A-B appears in A's list (as B) AND in B's list (as A)
Total entries: 6 (3 edges × 2)

1
2
3
4
5
6
7
8

Directed graph with edges: A→B, B→C, C→A
 
Adjacency List (Outgoing Edges):
A → [B]       // A has an outgoing edge to B
B → [C]       // B has an outgoing edge to C
C → [A]       // C has an outgoing edge to A
 
Total entries: 3 (exactly |E| entries for directed graphs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class DirectedGraphWithReverse:
    """
    Maintains both forward (outgoing) and reverse (incoming) edges.
    Useful for algorithms that traverse edges in both directions.
    """
    
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        self.out_adj = [[] for _ in range(num_vertices)]  # v → successors
        self.in_adj = [[] for _ in range(num_vertices)]   # v → predecessors
    
    def add_edge(self, u: int, v: int):
        """Add directed edge u → v."""
        self.out_adj[u].append(v)  # u's outgoing neighbor
        self.in_adj[v].append(u)   # v's incoming neighbor
    
    def successors(self, v: int) -> list[int]:
        """Return vertices that v points to."""
        return self.out_adj[v]
    
    def predecessors(self, v: int) -> list[int]:
        """Return vertices that point to v."""
        return self.in_adj[v]
    
    def out_degree(self, v: int) -> int:
        """Number of outgoing edges from v."""
        return len(self.out_adj[v])
    
    def in_degree(self, v: int) -> int:
        """Number of incoming edges to v."""
        return len(self.in_adj[v])
 
# Example: Building dependency graph
# Task 0 must complete before tasks 1 and 2
g = DirectedGraphWithReverse(4)
g.add_edge(0, 1)  # 0 → 1
g.add_edge(0, 2)  # 0 → 2
g.add_edge(1, 3)  # 1 → 3
g.add_edge(2, 3)  # 2 → 3
 
# What depends on task 0?
print(f"Tasks depending on 0: {g.successors(0)}")  # [1, 2]
 
# What must complete before task 3?
print(f"Prerequisites of 3: {g.predecessors(3)}")  # [1, 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# Approach 1: List of (neighbor, weight) tuples
class WeightedGraphTuples:
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        self.adj = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u: int, v: int, weight: float, directed: bool = False):
        self.adj[u].append((v, weight))
        if not directed:
            self.adj[v].append((u, weight))
    
    def neighbors_with_weights(self, v: int):
        """Returns list of (neighbor, weight) tuples."""
        return self.adj[v]
 
# Approach 2: Dictionary of dictionaries (more Pythonic)
class WeightedGraphDict:
    def __init__(self):
        self.adj = {}  # {vertex: {neighbor: weight, ...}, ...}
    
    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = {}
    
    def add_edge(self, u, v, weight, directed=False):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u][v] = weight
        if not directed:
            self.adj[v][u] = weight
    
    def get_weight(self, u, v) -> float | None:
        """O(1) weight lookup for edge (u, v)."""
        return self.adj.get(u, {}).get(v)
    
    def neighbors(self, v):
        """Returns dict: {neighbor: weight, ...}"""
        return self.adj.get(v, {})
 
# Example: Road network
roads = WeightedGraphDict()
roads.add_edge("NYC", "Boston", 215)     # 215 miles
roads.add_edge("NYC", "Philadelphia", 95)
roads.add_edge("Boston", "Portland", 110)
 
print(f"NYC neighbors: {roads.neighbors('NYC')}")
# {'Boston': 215, 'Philadelphia': 95}
 
print(f"NYC to Boston distance: {roads.get_weight('NYC', 'Boston')}")
# 215

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.*;
 
// Edge class for weighted graphs
class Edge {
    int destination;
    double weight;
    
    Edge(int destination, double weight) {
        this.destination = destination;
        this.weight = weight;
    }
}
 
class WeightedGraph {
    private int V;
    private List<List<Edge>> adj;
    
    WeightedGraph(int vertices) {
        V = vertices;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }
    
    void addEdge(int u, int v, double weight, boolean directed) {
        adj.get(u).add(new Edge(v, weight));
        if (!directed) {
            adj.get(v).add(new Edge(u, weight));
        }
    }
    
    List<Edge> getNeighbors(int v) {
        return adj.get(v);
    }
    
    // For Dijkstra's algorithm, we often need this interface:
    void relaxNeighbors(int u, double[] dist, PriorityQueue<int[]> pq) {
        for (Edge e : adj.get(u)) {
            if (dist[u] + e.weight < dist[e.destination]) {
                dist[e.destination] = dist[u] + e.weight;
                pq.offer(new int[]{e.destination, (int)dist[e.destination]});
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class LabeledGraph:
    """
    Graph supporting arbitrary vertex labels (strings, etc.)
    Internally maps labels to integer indices for efficiency.
    """
    
    def __init__(self):
        self.label_to_index = {}  # label → integer index
        self.index_to_label = []  # index → label
        self.adj = []             # adjacency list (by index)
        self.V = 0
    
    def add_vertex(self, label) -> int:
        """Add a vertex with the given label, return its index."""
        if label not in self.label_to_index:
            index = self.V
            self.label_to_index[label] = index
            self.index_to_label.append(label)
            self.adj.append([])
            self.V += 1
            return index
        return self.label_to_index[label]
    
    def add_edge(self, label_u, label_v, directed=False):
        """Add edge between labeled vertices."""
        u = self.add_vertex(label_u)
        v = self.add_vertex(label_v)
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)
    
    def neighbors(self, label):
        """Return neighbor labels for the given vertex."""
        idx = self.label_to_index.get(label)
        if idx is None:
            return []
        return [self.index_to_label[i] for i in self.adj[idx]]
 
# Example: Social network with usernames
social = LabeledGraph()
social.add_edge("alice", "bob")
social.add_edge("alice", "carol")
social.add_edge("bob", "dave")
 
print(f"Alice's friends: {social.neighbors('alice')}")  # ['bob', 'carol']
print(f"Bob's friends: {social.neighbors('bob')}")      # ['alice', 'dave']

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

from collections import defaultdict
 
class DynamicGraph:
    """
    Fully dynamic graph using dictionaries.
    No fixed vertex count, arbitrary vertex labels.
    
    Tradeoff: Slightly more memory for dict overhead,
    but maximum flexibility for dynamic graphs.
    """
    
    def __init__(self, directed=False):
        self.adj = defaultdict(set)  # auto-creates empty sets
        self.directed = directed
    
    def add_edge(self, u, v):
        """Add edge (creates vertices implicitly)."""
        self.adj[u].add(v)
        if not self.directed:
            self.adj[v].add(u)
    
    def remove_edge(self, u, v):
        """Remove edge if it exists."""
        self.adj[u].discard(v)
        if not self.directed:
            self.adj[v].discard(u)
    
    def remove_vertex(self, v):
        """Remove vertex and all its edges."""
        # Remove v from all neighbor lists
        for neighbor in list(self.adj[v]):
            self.adj[neighbor].discard(v)
        # Remove v's entry
        del self.adj[v]
    
    def has_edge(self, u, v) -> bool:
        return v in self.adj[u]
    
    def has_vertex(self, v) -> bool:
        return v in self.adj
    
    def vertices(self):
        return self.adj.keys()
    
    def neighbors(self, v):
        return self.adj[v]
 
# Example: Building graph incrementally
g = DynamicGraph()
g.add_edge("node_a", "node_b")
g.add_edge("node_a", "node_c")
g.add_edge("node_b", "node_c")
 
print(f"All vertices: {list(g.vertices())}")
# ['node_a', 'node_b', 'node_c']
 
g.remove_vertex("node_b")
print(f"After removing node_b: {list(g.vertices())}")
# ['node_a', 'node_c']

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

from collections import defaultdict
 
# ==================================================
# Pattern 1: Edge List Input
# Common in competitive programming
# ==================================================
 
def build_from_edge_list(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    """
    Input: number of vertices and list of (u, v) pairs
    
    Example input:
    n = 4
    edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
    """
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)  # remove for directed graph
    return adj
 
 
# ==================================================
# Pattern 2: Edge List with Number of Edges First
# Very common format: first line has V E, then E edges
# ==================================================
 
def build_from_competitive_input():
    """
    Input format:
    4 5       <- 4 vertices, 5 edges
    0 1       <- edge 1
    0 2       <- edge 2
    1 2       <- edge 3
    1 3       <- edge 4
    2 3       <- edge 5
    """
    line = input().split()
    V, E = int(line[0]), int(line[1])
    
    adj = [[] for _ in range(V)]
    for _ in range(E):
        edge = input().split()
        u, v = int(edge[0]), int(edge[1])
        adj[u].append(v)
        adj[v].append(u)
    
    return adj
 
 
# ==================================================
# Pattern 3: Adjacency List Input (Direct Neighbors)
# Each line lists neighbors of vertex i
# ==================================================
 
def build_from_neighbor_lists(neighbor_lists: list[list[int]]) -> list[list[int]]:
    """
    Input: directly given neighbors for each vertex
    
    Example:
    neighbor_lists = [
        [1, 2],    # vertex 0 connects to 1, 2
        [0, 2, 3], # vertex 1 connects to 0, 2, 3
        [0, 1, 3], # vertex 2 connects to 0, 1, 3
        [1, 2]     # vertex 3 connects to 1, 2
    ]
    """
    # Input is already in adjacency list format!
    return [list(neighbors) for neighbors in neighbor_lists]
 
 
# ==================================================
# Pattern 4: Matrix to Adjacency List Conversion
# Converting from matrix representation
# ==================================================
 
def matrix_to_adj_list(matrix: list[list[int]]) -> list[list[int]]:
    """
    Convert adjacency matrix to adjacency list.
    Essential skill for choosing representation at runtime.
    """
    n = len(matrix)
    adj = [[] for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            if matrix[i][j] != 0:  # edge exists
                adj[i].append(j)
    
    return adj
 
 
# ==================================================
# Pattern 5: Grid to Graph Conversion
# 2D grids are implicit graphs
# ==================================================
 
def grid_to_adj_list(grid: list[list[str]], 
                      blocked: str = '#') -> dict[tuple[int,int], list[tuple[int,int]]]:
    """
    Convert a 2D grid to an adjacency list.
    Each cell (r, c) becomes a vertex.
    4-directional neighbors become edges.
    
    Example grid:
    . . # .
    . . . .
    # . . .
    """
    rows, cols = len(grid), len(grid[0])
    adj = defaultdict(list)
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != blocked:
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != blocked:
                        adj[(r, c)].append((nr, nc))
    
    return adj