Graphs

advanced5 problems

Prerequisites:Big O & ComplexityArrays & StringsStacks & QueuesTrees & Tries

Beyond Trees: Arbitrary Connections

In the Trees module, every node had exactly one parent (except the root). That's a hierarchy - a strict parent-child relationship.

But what if you need to model something more complex? A social network where anyone can befriend anyone. A road map where intersections connect to many other intersections. A web where pages link to any other page.

That's a graph. A graph has vertices (nodes) and edges (connections) - and there's no restriction on how many connections a node can have, or in what direction.

The key idea: if trees are about hierarchy, graphs are about connectivity.

Graph Representation

A graph consists of vertices (nodes) and edges connecting them. Graphs can be directed or undirected, weighted or unweighted.

Representations:

Approach	Space	Check edge	Iterate neighbors
Adjacency Matrix	O(V²)	O(1)	O(V)
Adjacency List	O(V + E)	O(degree)	O(degree)
Edge List	O(E)	O(E)	O(E)

Adjacency list is the most common choice for interviews.

Building a graph (adjacency list)C#

// Graph as adjacency list
var graph = new Dictionary<int, List<int>>();

// Build from edges
void BuildGraph(int[][] edges) {
    foreach (var e in edges) {
        int u = e[0], v = e[1];
        if (!graph.ContainsKey(u)) graph[u] = new List<int>();
        if (!graph.ContainsKey(v)) graph[v] = new List<int>();
        graph[u].Add(v);
        graph[v].Add(u); // undirected - add both directions
    }
}

// Graph represented as List<int>[] (if vertices are 0..n-1)
int n = 6;
var graph2 = new List<int>[n];
for (int i = 0; i < n; i++) graph2[i] = new List<int>();

// Each edge: graph2[u].Add(v); graph2[v].Add(u);

// Weighted graph
var weighted = new Dictionary<int, List<(int neighbor, int weight)>>();
weighted[u].Add((v, 5));

BFS vs DFS

	BFS (Queue)	DFS (Stack/Recursion)
Order	Level by level	Deep first
Shortest path	Yes (unweighted)	No
Space	O(V) (queue + visited set)	O(V) (stack + visited set)
Use case	Shortest path, level order	Topological, connectivity, cycles

Key difference: BFS uses a queue and explores neighbors level by level. DFS uses a stack (or recursion) and goes deep before backtracking.

Problem

Explore all nodes of this graph starting from node A, visiting each node exactly once.

Graph TraversalStep 1 / 12

Initialize queue with 0

Speed:

Unvisited Next in line Current Visited

BFS and DFS templatesC#

// BFS - shortest path in unweighted graph
int Bfs(Dictionary<int, List<int>> graph, int start, int target) {
    var q = new Queue<int>();
    var visited = new HashSet<int>();
    q.Enqueue(start);
    visited.Add(start);
    int distance = 0;

    while (q.Count > 0) {
        int size = q.Count;
        for (int i = 0; i < size; i++) {
            int node = q.Dequeue();
            if (node == target) return distance;

            foreach (var neighbor in graph.GetValueOrDefault(node, [])) {
                if (visited.Add(neighbor))
                    q.Enqueue(neighbor);
            }
        }
        distance++;
    }
    return -1; // not reachable
}

// DFS - recursive (for connectivity, cycle detection)
bool Dfs(Dictionary<int, List<int>> graph, int node, HashSet<int> visited) {
    if (visited.Contains(node)) return false;
    visited.Add(node);

    foreach (var neighbor in graph.GetValueOrDefault(node, []))
        Dfs(graph, neighbor, visited);

    return true;
}

Topological Sort

A topological order of a directed acyclic graph (DAG) is an ordering where every edge goes from earlier to later nodes.

Applications: Course prerequisites, build dependencies, task scheduling.

Two algorithms:

Kahn's algorithm (BFS) - track in-degrees, process nodes with 0 in-degree
DFS-based - post-order traversal, reverse the result

Kahn's algorithm (BFS)C#

int[] TopologicalSort(int n, int[][] edges) {
    var graph = new List<int>[n];
    var inDegree = new int[n];
    for (int i = 0; i < n; i++) graph[i] = new List<int>();

    foreach (var e in edges) {
        graph[e[0]].Add(e[1]);
        inDegree[e[1]]++;
    }

    var q = new Queue<int>();
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0) q.Enqueue(i);

    var result = new List<int>();
    while (q.Count > 0) {
        int node = q.Dequeue();
        result.Add(node);

        foreach (var neighbor in graph[node]) {
            if (--inDegree[neighbor] == 0)
                q.Enqueue(neighbor);
        }
    }

    return result.Count == n ? result.ToArray() : []; // [] if cycle
}

When to Model as a Graph

A graph is the right abstraction when:

You have entities (nodes) and relationships (edges) between them
The relationships are not hierarchical (use a tree if they are)
You need to find paths, connectivity, or shortest distances

Graph vs other structures:

Structure	Use when
Tree	Strict hierarchy (one parent per node)
Graph	Arbitrary connections (many-to-many)
Adjacency list	Most interview problems (space-efficient)
Adjacency matrix	Dense graph, need O(1) edge check

BFS vs DFS decision guide:

Signal	Choice
"Shortest path in unweighted graph"	BFS (queue)
"Does a path exist?"	Either
"Topological order"	BFS (Kahn's) or DFS
"Detect cycle"	DFS with recursion stack
"Connected components"	Either (DFS is simpler)
"All paths from A to B"	DFS (backtracking)
"Level order / layers"	BFS
"Maze shortest path"	BFS
"Maze find any exit"	DFS (simpler)

When NOT to use a graph:

Only one entity type with no relationships (just use a list)
Relationships are simple and linear (use an array or tree)
Problem can be solved with a hash map and iteration

Common Mistakes

Forgetting the visited set (infinite loop): Without tracking visited nodes, BFS/DFS will revisit nodes and loop forever in a cyclic graph. Always initialize a visited set before traversal and check it before enqueuing/exploring.

Confusing directed and undirected graphs: In an undirected graph, add both directions: graph[u].Add(v) AND graph[v].Add(u). In a directed graph, only add one direction. Missing this causes wrong answers.

"BFS always finds the shortest path": Only for unweighted graphs. In weighted graphs, BFS does NOT find the shortest path - use Dijkstra's algorithm instead.

DFS recursion depth in large graphs: A DFS on a graph with 100,000 nodes might recurse 100,000 levels deep. Stack overflow! Use explicit stack (iterative DFS) for large graphs.

Confusing BFS and DFS approaches: BFS = queue (level by level). DFS = stack/recursion (depth first). Using the wrong one wastes time or gives wrong answers. For shortest path in an unweighted graph, always choose BFS.

Not handling disconnected components: Most graph problems assume a connected graph. If the graph has multiple components, make sure your traversal covers ALL nodes by looping over all vertices and starting a new traversal for any unvisited node.

Key Patterns to Remember

Number of islands / connected components - DFS or BFS on grid
Course schedule / prerequisite order - topological sort
Clone graph - BFS/DFS with hash map to track cloned nodes
Word ladder - BFS shortest path on implicit graph
Detect cycle - DFS with recursion stack tracking (3-coloring: unvisited, in-stack, done)
Dijkstra's shortest path - PriorityQueue for weighted graphs

What's Next?

Graphs are the most flexible data structure - they can model almost anything. But that flexibility comes with a cost: exhaustive search (backtracking) on a state space explores all possibilities, which can be exponential. (Standard BFS/DFS on a graph visits each vertex once — O(V+E).)

Dynamic Programming is the solution to this problem. When your graph-like exploration has overlapping subproblems (the same state visited via different paths), DP caches results to avoid recomputation.

If recursion is "try everything," DP is "try everything but don't repeat yourself."

Next up: Dynamic Programming