Graph Fundamentals — The Language of Connections

Before you write a single line of graph algorithm code, you need the vocabulary. Not for its own sake, but because the representation you choose determines your algorithm’s time and space complexity, and the wrong choice for the wrong problem is the kind of mistake that costs you in an interview before you’ve even started solving it.

Graphs are described by their vertices (things) and edges (relationships between things). Every problem that involves connectivity, dependencies, distances, or reachability is a graph problem, whether the word “graph” appears in the problem statement or not.

---

Core Definitions

Vertex (node): a fundamental unit. Could represent a city, a course, a character, a cell in a grid.

Edge: a connection between two vertices. Could be a road, a prerequisite relationship, an adjacency in a grid.

Directed graph (digraph): edges have direction. Edge u→v means you can go from u to v, but not necessarily v to u. Example: course prerequisites, social media “follows.”

Undirected graph: edges have no direction. If u is connected to v, then v is connected to u. Example: friendships, road networks (ignoring one-ways).

Weighted graph: each edge carries a numeric weight (cost, distance, capacity). Example: road with distance, network link with bandwidth.

Unweighted graph: edges are just present or absent, no weight. For shortest path purposes, every edge has implicit weight 1.

Cyclic graph: contains at least one cycle (a path that starts and ends at the same vertex).

Acyclic graph: contains no cycles. A directed acyclic graph is a DAG — the structure that enables topological sort.

Connected graph (undirected): every vertex is reachable from every other vertex.

Strongly connected (directed): every vertex is reachable from every other vertex following edge directions.

Degree: number of edges incident to a vertex. In directed graphs: in-degree (edges coming in) and out-degree (edges going out).

---

Graph Representations

Three representations exist. Each has distinct trade-offs. The choice should follow from the problem’s structure, not habit.

---

Adjacency Matrix

A 2D boolean (or weight) matrix adj[V][V] where adj[u][v] = true (or the edge weight) if edge u→v exists.

int V = 5;
int[][] adj = new int[V][V];   // adj[u][v] = weight; 0 means no edge

// Add edge u→v with weight w:
adj[u][v] = w;
// For undirected, also: adj[v][u] = w;

Operation	Cost
Check if edge (u,v) exists	O(1)
Iterate all neighbors of u	O(V)
Space	O(V²)

When to use: dense graphs (E ≈ V²), when you need O(1) edge existence queries, Floyd-Warshall.

When NOT to use: sparse graphs (most real-world graphs). If V = 10,000 and E = 50,000, the matrix wastes 10⁸ cells for ~50,000 actual edges.

---

Adjacency List

An array (or map) of lists: adj[u] contains all vertices v where edge u→v exists. For weighted graphs, store pairs (v, weight).

int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());

// Add edge u→v:
adj.get(u).add(v);
// For weighted: List<List<int[]>> where int[] = {v, weight}
// For undirected: also adj.get(v).add(u);

Operation	Cost
Check if edge (u,v) exists	O(degree(u))
Iterate all neighbors of u	O(degree(u))
Space	O(V + E)

When to use: sparse graphs, BFS, DFS, Dijkstra, topological sort — basically everything on LeetCode.

---

Edge List

A list of all edges, each represented as a tuple (u, v) or (u, v, weight).

int[][] edges = {{0,1,4}, {0,2,1}, {1,3,2}, ...};  // [from, to, weight]

Operation	Cost
Check if edge (u,v) exists	O(E)
Iterate all edges	O(E)
Space	O(E)

When to use: algorithms that process all edges in sorted order (Kruskal’s MST). Not useful for traversal.

---

Decision Table: Which Representation?

Situation	Use
Graph is sparse (E << V²)	Adjacency list
Graph is dense (E ≈ V²)	Adjacency matrix
Need O(1) edge lookup	Adjacency matrix
Need to sort/process all edges	Edge list
BFS, DFS, Dijkstra, topological sort	Adjacency list
Floyd-Warshall	Adjacency matrix
Kruskal’s MST	Edge list (sorted)

For LeetCode: default to adjacency list. You will rarely be wrong.

---

Traversal Invariants: The Visited Set

Every graph traversal maintains a visited set (or array). Without it, cycles cause infinite loops.

boolean[] visited = new boolean[V];

// In BFS or DFS:
if (!visited[neighbor]) {
    visited[neighbor] = true;
    // enqueue or recurse
}

What most people get wrong: marking a node visited at the wrong time. In BFS, mark the node visited when you enqueue it, not when you dequeue and process it. If you mark on dequeue, the same node can be enqueued multiple times before it’s processed, leading to redundant work and potentially wrong results (e.g., non-shortest paths processed).

// CORRECT BFS visited marking:
queue.offer(start);
visited[start] = true;       // ← mark BEFORE processing, AT enqueue time

while (!queue.isEmpty()) {
    int node = queue.poll();  // process here
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;  // mark AT enqueue time
            queue.offer(neighbor);
        }
    }
}

---

Connected Components

In an undirected graph, a connected component is a maximal set of vertices all reachable from each other.

BFS/DFS from a single node only covers its connected component. To find all components:

int components = 0;
boolean[] visited = new boolean[V];

for (int i = 0; i < V; i++) {
    if (!visited[i]) {
        components++;
        bfs(i, visited, adj);   // or dfs(i, visited, adj)
    }
}

What most people get wrong: running BFS/DFS from only vertex 0 and concluding they’ve traversed the whole graph. If the graph has disconnected components, they’ve only seen one. Always loop over all vertices and trigger a new traversal for each unvisited one.

---

Building a Graph from a Problem

Most LeetCode graph problems don’t hand you an adjacency list. They give you edge pairs, a grid, or a set of relationships. Build the graph first.

From edge list (e.g., course prerequisites):

// prerequisites[i] = [ai, bi] means bi must be taken before ai
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

for (int[] pre : prerequisites) {
    adj.get(pre[1]).add(pre[0]);  // bi → ai (bi must come before ai)
}

From a grid (e.g., number of islands):

// Grid cells are vertices. Edges connect adjacent cells.
// No explicit adjacency list needed — neighbors are computed on the fly:
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] d : dirs) {
    int nr = r + d[0], nc = c + d[1];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        // (nr, nc) is a neighbor of (r, c)
    }
}

The grid approach is an implicit graph: you never build an explicit adjacency list, you compute neighbors on the fly during traversal.

---

Practice Problems

#	Problem	Difficulty	Focus
1	LC 547 — Number of Provinces	Medium	BFS/DFS to count connected components
2	LC 200 — Number of Islands	Medium	Grid as implicit graph, connected components
3	LC 133 — Clone Graph	Medium	BFS with node mapping, graph construction
4	LC 207 — Course Schedule	Medium	Directed graph, cycle detection (preview of topo sort)

Problems 1 and 2 are the foundation problems — do not skip them. They establish the “loop over all vertices to find all components” pattern that you will use in every subsequent graph problem. Problem 4 is a forward bridge into topological sort.

---

Navigation

← Previous	Phase 3 README
→ Next	02 — BFS and DFS
↑ Phase Home	Phase 3 README
⌂ Root	Master README