Graphs — Adjacency List & Matrix Representation Guide

In this tutorial, you'll learn about Graphs. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections). Graphs model real-world relationships — from social networks and road maps to web page links and network topologies.

What You'll Learn

You will learn graph terminology, adjacency list and adjacency matrix representations, how to add vertices and edges, and how to choose the right representation for different scenarios.

Why It Matters

Graphs are everywhere: social networks (users as nodes, friendships as edges), GPS navigation (intersections as nodes, roads as edges), web crawling (pages as nodes, links as edges), and dependency resolution.

Real-World Use

Doda Browser's page ranking algorithm models the web as a directed graph. Web pages are vertices and hyperlinks are edges. The ranking system traverses this graph — similar to Google's original PageRank — to determine which pages are most authoritative.

Graph Terminology

graph LR
    A[Vertex A] --> B[Vertex B]
    A --> C[Vertex C]
    B --> D[Vertex D]
    C --> D
    D --> E[Vertex E]
    style A fill:#4a90d9,stroke:#333,color:#fff
    style D fill:#e67e22,stroke:#333,color:#fff

• Vertex (Node): A single entity
• Edge: Connection between two vertices
• Directed vs Undirected: Edges have direction or not
• Weighted vs Unweighted: Edges have associated costs or not
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at the same vertex

Adjacency List

Each vertex stores a list of its neighbors. Space: O(V + E) — efficient for sparse graphs.

class AdjacencyList:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, u, v, directed=False):
        self.add_vertex(u)
        self.add_vertex(v)
        self.graph[u].append(v)
        if not directed:
            self.graph[v].append(u)

    def get_neighbors(self, vertex):
        return self.graph.get(vertex, [])

    def display(self):
        for vertex, neighbors in self.graph.items():
            print(f"{vertex}: {neighbors}")

g = AdjacencyList()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")
g.display()
print("Neighbors of A:", g.get_neighbors("A"))

Expected output:

A: ['B', 'C']
B: ['A', 'D']
C: ['A', 'D']
D: ['B', 'C', 'E']
E: ['D']
Neighbors of A: ['B', 'C']

class AdjacencyList {
    constructor() { this.graph = {}; }

    addVertex(v) { if (!this.graph[v]) this.graph[v] = []; }

    addEdge(u, v, directed = false) {
        this.addVertex(u);
        this.addVertex(v);
        this.graph[u].push(v);
        if (!directed) this.graph[v].push(u);
    }

    getNeighbors(v) { return this.graph[v] || []; }

    display() {
        for (let [v, neighbors] of Object.entries(this.graph)) {
            console.log(`${v}: ${neighbors.join(', ')}`);
        }
    }
}

let g = new AdjacencyList();
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "D");
g.addEdge("D", "E");
g.display();
console.log("Neighbors of A:", g.getNeighbors("A").join(', '));

Expected output:

A: B, C
B: A, D
C: A, D
D: B, C, E
E: D
Neighbors of A: B, C

Adjacency Matrix

A V×V matrix where matrix[i][j] = 1 (or weight) if there's an edge from i to j. Space: O(V²) — efficient for dense graphs.

class AdjacencyMatrix:
    def __init__(self, num_vertices):
        self.n = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
        self.vertices = list(range(num_vertices))

    def add_edge(self, i, j, directed=False, weight=1):
        self.matrix[i][j] = weight
        if not directed:
            self.matrix[j][i] = weight

    def has_edge(self, i, j):
        return self.matrix[i][j] != 0

    def get_neighbors(self, i):
        return [j for j in range(self.n) if self.matrix[i][j] != 0]

    def display(self):
        for row in self.matrix:
            print(row)

am = AdjacencyMatrix(5)
am.add_edge(0, 1)
am.add_edge(0, 2)
am.add_edge(1, 3)
am.add_edge(2, 3)
am.add_edge(3, 4)
am.display()
print("Has edge 0-1:", am.has_edge(0, 1))
print("Neighbors of 3:", am.get_neighbors(3))

Expected output:

[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]
Has edge 0-1: True
Neighbors of 3: [1, 2, 4]

Representation Comparison

Weighted Graph (with Dijkstra Setup)

class WeightedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v, weight, directed=False):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append((v, weight))
        if not directed:
            self.graph[v].append((u, weight))

    def display(self):
        for vertex, edges in self.graph.items():
            edges_str = ", ".join(f"{v}({w})" for v, w in edges)
            print(f"{vertex}: {edges_str}")

wg = WeightedGraph()
wg.add_edge("A", "B", 4)
wg.add_edge("A", "C", 2)
wg.add_edge("B", "C", 1)
wg.add_edge("B", "D", 5)
wg.add_edge("C", "D", 8)
wg.add_edge("C", "E", 10)
wg.add_edge("D", "E", 2)
wg.display()

Expected output:

A: B(4), C(2)
B: A(4), C(1), D(5)
C: A(2), B(1), D(8), E(10)
D: B(5), C(8), E(2)
E: C(10), D(2)

Common Pitfalls

1. Forgetting to Handle Both Directions

For undirected graphs, always add the reverse edge. Missing this creates a directed graph by accident.

2. Off-by-One Vertex Indexing

In adjacency matrices, ensure vertex indices are 0-based and within bounds. Out-of-range access causes runtime errors.

3. Not Tracking Visited Nodes

Graph traversal without a visited set causes infinite loops in cyclic graphs. Always maintain a visited structure.

4. Assuming Graph Is Connected

Not all vertices are reachable from a given start. Code must handle disconnected components gracefully.

5. Memory Bloat from Dense Matrices

For a graph with 10,000 vertices, an adjacency matrix uses ~400 MB (assuming integers). An adjacency list uses far less for sparse graphs.

Practice Questions

1. Detect if there is a path between two vertices (reachability).

def has_path(graph, start, end, visited=None):
    if visited is None:
        visited = set()
    if start == end:
        return True
    visited.add(start)
    for neighbor in graph.get_neighbors(start):
        if neighbor not in visited:
            if has_path(graph, neighbor, end, visited):
                return True
    return False

2. Find all connected components in an undirected graph.

3. Detect a cycle in a directed graph using DFS with state colors.

4. Challenge: Implement a graph cloning function (deep copy) that works with cyclic graphs.

5. Real-world task: DodaZIP's dependency resolver builds a directed graph of file dependencies. Write a function that takes a list of (file, dependency) pairs, builds the graph, and detects circular dependencies that would prevent archive extraction.

What's Next

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.