A graph is the most general shape data comes in: a set of nodes, and a set of connections between them. That is all. There is no root, there is no "first" node, and — the part that changes everything — a path can lead you back to where you started.

Trees are graphs with the loops removed and a root chosen. Every technique in dfs.md and bfs.md still applies, plus one mandatory addition:

You must remember where you have already been. Without a visited set, a single cycle makes the traversal run forever.

Three sub-problems cover almost every graph question in an interview, and telling them apart is the actual skill:

• "How many separate pieces are there?" → Traverse from every unvisited node; each traversal you start is one new piece.
• "In what order can I do these tasks, given that some must come before others?" → Topological sort. Only possible when the graph has no cycles.
• "What is the cheapest route, when steps cost different amounts?" → Dijkstra. BFS is wrong here, and knowing why is the point.

🔬 Variable Anatomy: The 7 Variables Every Graph Algorithm Uses

To connect abstract graph concepts with concrete Python syntax, here is the universal code anatomy showing what every variable does:

from collections import defaultdict, deque
import heapq
 
def graphMasterTemplate(
    num_nodes: int,
    edges: list[list[int]],
    source: int
) -> dict[int, int]:
    # =========================================================================
    # 1. THE TOPOLOGY & STATE STORAGE POOLS
    # =========================================================================
    adj = defaultdict(list)           # 🕸️ Graph Adjacency List: node -> list of (neighbor, weight)
    in_degree = [0] * num_nodes       # 📥 Prerequisite Counter: tracks incoming DAG(Directed Acyclic Graph) edges
    visited = set()                   # 🚫 Visited Deduplication Set: prevents infinite cycles
    dist = {source: 0}                # ⏱️ Shortest Distance Table: tracks minimal cost to each node
    
    # =========================================================================
    # 2. THE GRAPH BUILD PHASE
    # =========================================================================
    for u, v, w in edges:
        adj[u].append((v, w))
        in_degree[v] += 1             # In-degree populated for topological sorting
 
    # =========================================================================
    # 3. FRONTIER PROCESSING PIPELINE (DIJKSTRA / BFS / KAHN'S)
    # =========================================================================
    # Min-heap priority queue storing (current_distance, node_id)
    min_heap = [(0, source)]
 
    while min_heap:
        d, u = heapq.heappop(min_heap)
 
        # ⚠️ CRITICAL: Stale-entry guard for lazy Dijkstra heap relaxation
        if d > dist.get(u, float('inf')):
            continue
 
        visited.add(u)
 
        for v, weight in adj[u]:
            new_dist = d + weight
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                heapq.heappush(min_heap, (new_dist, v))  # ⚡ Edge relaxation
 
    return dist
 

Variable Role Reference:

🧠 The Universal Representation Contract:
In graph algorithms, graph structure is represented in two standard ways:

• Explicit Adjacency List (adj[u] = [v1, v2]): Used for sparse node-and-edge graphs (e.g. Course Schedule, Network Delay). Built once in $O(V + E)$ before traversal.
• Implicit Coordinate Grids (dr, dc = [(-1,0), (1,0), (0,-1), (0,1)]): Used for 2D matrices (e.g. Number of Islands, Walls and Gates). Neighbors are dynamically computed on-the-fly without allocating adjacency lists.

🌟 The 3 Dimensions of Graph Algorithms & The Cycle-Breaker Principle

Every graph problem is governed by 3 Fundamental Dimensions:

┌─────────────────────────────────────────────────────────────────────────────┐
│                       THE 3 DIMENSIONS OF GRAPH ALGORITHMS                  │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. FRONTIER ORDER │ Queue (BFS), Stack (DFS),         │ "Which node gets    │
│    (Discipline)   │ or Min-Heap (Dijkstra)            │ processed next?"    │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. EDGE DYNAMICS  │ Unweighted (step count),          │ "How is transition  │
│    (Weights/Dir)  │ Directed DAG(Directed Acyclic Graph), or Weighted edges   │ cost evaluated?"    │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. CYCLE CONTROL  │ `visited` set, in-degree counter, │ "How do we prevent  │
│    (Loop Breaker) │ or 3-color state machine          │ infinite loops?"    │
└───────────────────┴───────────────────────────────────┴─────────────────────┘
 

How this plays out in actual problems:

🟢 Scenario A: Connected Components & Grid Flood Fill (Using Outer Scan + Sink)

• In connected component problems (like Number of Islands), we want to count separate isolated clusters.
• The Rule: The outer loop scans every cell. When it hits an unvisited land cell, increment components += 1 and launch a traversal to sink the entire island so the outer loop never sees it again.
• The Code: if grid[r][c] == '1': count += 1; dfs(r, c)

🔵 Scenario B: Topological Sort on DAGs(Directed Acyclic Graphs) (Using In-Degree Reduction)

• In dependency resolution (like Course Schedule II), tasks must be ordered such that all prerequisites precede dependent tasks.
• The Rule: Only enqueue nodes whose in_degree == 0. When a node is popped, decrement in_degree[v] for all neighbors, and enqueue any neighbor whose in_degree reaches 0. If processed count $< V$, a cycle exists!
• The Code: if in_degree[neighbor] == 0: queue.append(neighbor)

🟣 Scenario C: Single-Source Shortest Paths with Weights (Using Dijkstra's Heap Relaxation)

• When edge weights vary, BFS fails because the earliest visited path is not necessarily the cheapest.
• The Rule: Greedily pop the minimum provisional distance node from a min-heap. Relax outgoing edges with if d + weight < dist[v]: dist[v] = d + weight; heappush(...). Always guard stale entries with if d > dist[u]: continue.

💡 The Ultimate Takeaway Decision Rule:
When analyzing a new graph problem, ask: "Are edge weights present, and are there dependencies?"

• Unweighted Grid / Components ➔ Outer scan + DFS/BFS in-place sink ($O(V + E)$ or $O(R \cdot C)$).
• Prerequisites / DAG(Directed Acyclic Graph) Order ➔ Kahn's Algorithm with in-degree 0 queue ($O(V + E)$).
• Weighted Non-Negative Edges ➔ Dijkstra's Algorithm with Min-Heap ($O((V + E) \log V)$).
• Weighted 0 or 1 Edges ➔ 0-1 BFS with deque.appendleft / append ($O(V + E)$).

🎯 The 5 Essential Graph Paradigms & Archetypes

🏝️ 1. Connected Components & Grid Flood Fill (LC 200 & 733)

• Mental Model: A grid is an implicit graph where each cell $(r, c)$ connects to its 4 orthogonal neighbors.
• Outer Counter vs Inner Drain: The counter must live in the outer grid scan (for r in range(R): for c in range(C)). The inner DFS/BFS traversal exists solely to consume ("sink") the entire connected cluster so it is never counted again.
• Code: see the Flood Fill card.

📋 2. Topological Sort & DAG(Directed Acyclic Graph) Cycle Detection (LC 207 & 210 — Kahn's Algorithm)

• Mental Model: Kahn's algorithm removes nodes with zero incoming prerequisites sequentially.
• The Cycle Detection Guarantee: If all prerequisites can be satisfied, every node is enqueued and dequeued exactly once (len(order) == numCourses). If len(order) < numCourses, any remaining nodes are trapped in a cyclic dependency deadlock.
• Code: see the Topological Sort card.

⚡ 3. Weighted Shortest Paths (LC 743 — Dijkstra's Algorithm)

• Mental Model: Dijkstra uses a priority queue to greedily finalize shortest distances from origin in ascending order of total cost.
• The Stale Entry Guard: Because Python's heapq does not support $O(\log N)$ decrease-key, we push new (new_dist, v) pairs whenever an edge relaxes. Outdated higher-cost entries remain in the heap and must be dropped with if d > dist[u]: continue.
• Code: see the Dijkstra card.

🚀 4. 0-1 BFS with Double-Ended Queue (LC 1368)

• Mental Model: When edges cost strictly 0 or 1, a collections.deque replaces the priority queue.
• How It Works: Cost-0 transitions are pushed to the front (appendleft), while Cost-1 transitions are pushed to the back (append). This maintains strict distance monotonicity in $O(V + E)$ linear time without $O(\log V)$ heap overhead!

🎨 5. Graph 2-Coloring & Bipartition Check (LC 785)

• Mental Model: A graph is bipartite if its vertices can be partitioned into two sets such that no two adjacent vertices share the same color.
• How It Works: Run BFS from every unvisited node. Assign color 0 to root. For every neighbor, if unvisited, assign 1 - color[curr]; if already visited and color[neighbor] == color[curr], return False immediately.

🌳 Evaluating Graph Topologies, State Management & Frontier Management

Building an accurate mental model of graph representation and frontier management prevents the most pervasive graph bugs:

1. Graph Representation Best Practices

• Never build an adjacency list for a 2D matrix: On grids, neighbor offsets [(-1,0), (1,0), (0,-1), (0,1)] generate valid edges dynamically in $O(1)$ without memory allocation.
• Always verify edge direction in prerequisites: If taking course $B$ is required before $A$ ([A, B]), the directed edge points $B \rightarrow A$.

2. Frontier Discipline & Cycle Prevention

• Mark on Enqueue / Discovery: In BFS, adding a node to visited at the moment it is placed in the queue prevents duplicate queue insertions across diamond graphs ($A \rightarrow B, C \rightarrow D$).
• Iterative over Recursive for Large Grids: A $300 \times 300$ grid contains 90,000 cells. Recursive DFS will exceed CPython's 1000-frame recursion limit; use an explicit stack or BFS queue.

💡 Staff SWE Architectural Invariant:
In graph traversal, the choice of frontier data structure completely defines the algorithm: a FIFO Queue produces unweighted shortest paths (BFS), a LIFO Stack produces deep component reachability (DFS), a Min-Heap produces weighted shortest paths (Dijkstra), and an In-Degree Array produces valid topological DAG(Directed Acyclic Graph) orderings (Kahn's).