Graphs — Representation, BFS, DFS & Dijkstra Step-by-Step

Module 13 — Graphs: Representation, BFS, DFS & Shortest Path Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Graph Representations: Adjacency Matrix vs Adjacency List

A graph $G = (V, E)$ consists of a set of vertices $V$ connected by edges $E$. Unlike trees, graphs may contain cycles, disconnected subgraphs, and multiple pathways between vertices.

• Adjacency Matrix: A 2D array of size $V imes V$ where matrix[u][v] = 1 (or edge weight).
  • Pros: $O(1)$ edge existence query.
  • Cons: Requires $O(V^2)$ memory and $O(V)$ time to find all neighbors of a node. Wasteful for sparse graphs.
• Adjacency List: An array of lists where adj[u] contains the immediate neighbors of vertex $u$.
  • Pros: Requires only $O(V + E)$ memory and $O(\text{degree}(u))$ time to inspect neighbors.
  • Cons: Checking edge existence between $u$ and $v$ takes $O(\text{degree}(u))$.

2. BFS vs DFS Traversal Pathways

• Breadth-First Search (BFS): Uses a Queue (FIFO). Traverses level by level like ripples in water. Guaranteed to find the shortest unweighted path.
• Depth-First Search (DFS): Uses recursion or a Stack (LIFO). Plunges straight down one branch as deep as possible before backtracking. Ideal for cycle detection and topological sorting.

// 1. Breadth-First Search: O(V + E) Time, O(V) Space
void bfs(int start, const vector<vector<int>>& adj, int n) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

// 2. Depth-First Search: O(V + E) Time, O(V) Call Stack
void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

3. Shortest Path: Dijkstra's Algorithm & Edge Relaxation

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Edge Relaxation Principle

If you know a path to vertex $u$ with distance $dist[u]$, and there exists a directed edge $(u, v)$ with weight $w$: $$ ext{If } dist[u] + w < dist[v] implies dist[v] = dist[u] + w$$

vector<int> dijkstra(int start, int n, const vector<vector<pair<int, int>>>& adj) {
    vector<int> dist(n, 1e9);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

4. Graph Algorithm Complexity Matrix