Pattern GuideGraphs & Networks
Curriculum Masterclass

Graphs & Networks

"The Master Data Structure: Modeling complex relations, nodes, and pathways."

15 min read Beginner-Friendly Runtime: O(V + E)
PHASE 01: THE WHAT & THE HOW
01
THE INTUITION

What is a Graph?

At its core, a graph is extremely simple. A graph is just a collection of dots (called Vertices or Nodes) and lines (called Edges) that connect them. Unlike a Tree (which has a single root node at the top and spreads downward), a Graph has no hierarchy, no roots, and can form loops or cycles.

Directed vs. Undirected

• Undirected: Edges are two-way. Connections are mutual (like Facebook friendships).

• Directed: Edges have arrows. Flow goes one way (like Twitter followers or class prerequisites).

Weighted vs. Unweighted

• Unweighted: All lines are equal. Moving between nodes always costs 1 step.

• Weighted: Connections have costs (like mileage between cities or server response latencies).

02
STORAGE

How to Represent Graphs in Code

Since a graph has no single "root" pointer, how do we pass it to functions? Switch tabs in the interactive visualizer below to see the three main ways programmers store graph relations in code:

w=4w=3w=8w=2w=601234
Hover or tap nodes to trace adjacent links

Graph Representations

Graphs have no root nodes. We store them by cataloging connections. Hover over any node in the SVG to see which edges light up, then click the tabs above to inspect how the relationships are stored in variables!

PHASE 02: MOVING THROUGH A GRAPH
03
THE SEARCH ENGINES

Graph Traversals: DFS vs. BFS

Once a graph is stored, how do we navigate it? We have two primary search engines: DFS and BFS. Unlike trees (which always expand downward and can never loop), graphs can contain cycles. This introduces the most important rule in Graph algorithms: You must maintain a visited tracker to avoid infinite loops.

DFS: Depth Exploration

Plunges down a single path as far as possible before backtracking.

Ideal for: Finding path existence, traversing cycles, or checking if two items are connected.

BFS: Layered Expansion

Explores the graph layer-by-layer like ripples expanding in water.

Ideal for: Shortest path on an unweighted structure, finding the minimum steps.

THE VISITED SET TRAP

Without a visited set, cyclic graph searches cause stack overflows (DFS) or memory exhaustion (BFS) from spinning in loops. In BFS, always mark nodes visited as soon as you push them onto the queue, not when you pop them!

PHASE 03: ESSENTIAL GRAPH PATTERNS
04
DIAGNOSTIC PATTERN

Cycle Detection (Finding Loops)

Why it Matters

Cycles create infinite loops, locking algorithms or causing compilation circular dependencies (e.g., File A imports B, B imports A).

When to Use

• Detect grid/maze deadlocks.
• Verify circular course scheduling dependencies.
• Confirm if a structure is a valid tree (no cycles).

How to Code

Maintain a currentPath recursion stack tracking nodes in the current DFS path. If we revisit a node that is currently in our traversal route, we have a cycle!

This is the same idea as the 3-color version on the DFS page — currentPath is GRAY, and visited without currentPath is BLACK.

cycleDetection.js
1
// Directed Graph Cycle Detection (3-Color algorithm / DFS path tracking)
2
function hasCycle(numVertices, edges) {
3
const adj = new Map();
4
for (let i = 0; i < numVertices; i++) adj.set(i, []);
5
for (const [u, v] of edges) adj.get(u).push(v);
6
7
const visited = new Set();
8
const currentPath = new Set();
9
10
function dfs(node) {
11
if (currentPath.has(node)) return true; // Found loop back (cycle)
12
if (visited.has(node)) return false;
13
14
visited.add(node);
15
currentPath.add(node);
16
17
for (const neighbor of adj.get(node) || []) {
18
if (dfs(neighbor)) return true;
19
}
20
21
currentPath.delete(node);
22
return false;
23
}
24
25
for (let i = 0; i < numVertices; i++) {
26
if (dfs(i)) return true;
27
}
28
return false;
29
}
05
SCHEDULING PATTERN

Topological Sort (Ordering DAGs)

Why it Matters

If tasks have prerequisites (like university courses), you need a linear sequence ordering them so you never attempt a task before completing its requirements.

When to Use

• Finding a compiler file-build schedule.
• Creating a valid class graduation roadmap.
• Modeling package dependency trees.

How to Code (Kahn's BFS)

Track each node's incoming connections (inDegree). Put all nodes with inDegree = 0 (no prerequisites) in a queue. As we pop them, decrement neighbors' inDegree. Push any that hit 0.

topologicalSort.js
1
// Topological Sort (Kahn's BFS In-Degree Algorithm)
2
function topologicalSort(numCourses, prerequisites) {
3
const adj = new Map();
4
const inDegree = new Array(numCourses).fill(0);
5
for (let i = 0; i < numCourses; i++) adj.set(i, []);
6
7
for (const [dest, src] of prerequisites) {
8
adj.get(src).push(dest);
9
inDegree[dest]++;
10
}
11
12
const queue = [];
13
for (let i = 0; i < numCourses; i++) {
14
if (inDegree[i] === 0) queue.push(i);
15
}
16
17
const order = [];
18
while (queue.length > 0) {
19
const curr = queue.shift();
20
order.push(curr);
21
22
for (const neighbor of adj.get(curr) || []) {
23
inDegree[neighbor]--;
24
if (inDegree[neighbor] === 0) {
25
queue.push(neighbor);
26
}
27
}
28
}
29
30
return order.length === numCourses ? order : []; // Returns empty array if cycle exists
31
}
06
GROUPING PATTERN

Disjoint Set Union (DSU / Union-Find)

Why it Matters

Queries connection queries (are A and B connected?) in near constant amortized time ($O(\alpha(N))$) without conducting complete BFS or DFS traversals.

When to Use

• Dynamic connection updates (real-time friends adding).
• Kruskal's Minimum Spanning Tree algorithm.
• Finding redundant connections in undirected networks.

How to Code

Treat groups as trees where each element points to a parent. Use find(x) with Path Compression to locate the group leader. Connect trees with Union-by-Rank to maintain shallow depths.

unionFind.js
1
// Disjoint Set Union (DSU / Union-Find) with Path Compression & Union-By-Rank
2
class UnionFind {
3
constructor(size) {
4
this.parent = Array.from({ length: size }, (_, i) => i);
5
this.rank = new Array(size).fill(0);
6
}
7
8
find(i) {
9
if (this.parent[i] === i) return i;
10
this.parent[i] = this.find(this.parent[i]); // Path compression
11
return this.parent[i];
12
}
13
14
union(i, j) {
15
const rootI = this.find(i);
16
const rootJ = this.find(j);
17
if (rootI === rootJ) return false; // Already connected
18
19
// Union by rank
20
if (this.rank[rootI] < this.rank[rootJ]) {
21
this.parent[rootI] = rootJ;
22
} else {
23
this.parent[rootJ] = rootI;
24
if (this.rank[rootI] === this.rank[rootJ]) {
25
this.rank[rootI]++;
26
}
27
}
28
return true;
29
}
30
}
07
OPTIMIZATION PATTERN

Shortest Path Algorithms

Why it Matters

Finding the minimum-cost route between points on weighted connection maps.

When to Use

• Unweighted Graphs: Use simple BFS queue.
• Weighted Graphs (positive): Use Dijkstra's algorithm.
• Negative Weights: Use Bellman-Ford.

How to Code (Dijkstra)

Use a Min-Priority Queue mapping nodes sorted by current distance. Always expand the lowest-cost node, updating adjacent distances and pushing nodes.

dijkstra.js
1
// Dijkstra's Shortest Path Algorithm (using Min-heap array sort)
2
function dijkstra(numVertices, adjList, start) {
3
const dist = new Array(numVertices).fill(Infinity);
4
dist[start] = 0;
5
6
// elements: [distance, node]
7
const pq = [[0, start]];
8
9
while (pq.length > 0) {
10
pq.sort((a, b) => a[0] - b[0]); // Sort ascending (min-priority queue)
11
const [d, u] = pq.shift();
12
13
if (d > dist[u]) continue;
14
15
for (const [v, weight] of adjList.get(u) || []) {
16
if (dist[u] + weight < dist[v]) {
17
dist[v] = dist[u] + weight;
18
pq.push([dist[v], v]);
19
}
20
}
21
}
22
return dist;
23
}
08
ISLAND SCANNING

Connected Components (Multi-Start searches)

Why it Matters

Graphs are often divided into disjoint, isolated components. Standard single-start searches will fail to scan everything.

When to Use

• Count "Number of Islands" on grid matrices.
• Identify isolated, disjoint clusters of social users.

How to Code

Loop from 0 to V-1. If a node is unvisited, we increment the cluster count and launch a DFS to traverse and mark all nodes in that cluster.

connectedComponents.js
1
function countComponents(numVertices, edges) {
2
const adj = new Map();
3
for (let i = 0; i < numVertices; i++) adj.set(i, []);
4
for (const [u, v] of edges) {
5
adj.get(u).push(v);
6
adj.get(v).push(u); // Undirected graph
7
}
8
9
const visited = new Set();
10
let count = 0;
11
12
function dfs(node) {
13
visited.add(node);
14
for (const neighbor of adj.get(node) || []) {
15
if (!visited.has(neighbor)) {
16
dfs(neighbor);
17
}
18
}
19
}
20
21
for (let i = 0; i < numVertices; i++) {
22
if (!visited.has(i)) {
23
count++;
24
dfs(i);
25
}
26
}
27
return count;
28
}
09
PITFALLS

Common Mistakes

Forgetting Visited

Without a visited set, any graph with a cycle spins forever — stack overflow in DFS, unbounded queue growth in BFS. Always track it, and for BFS mark visited the moment a node is pushed, not when it's popped.

Directed vs Undirected Adjacency

Building an adjacency list with only adj[a].push(b) makes a directed edge a→b. If the graph is actually undirected, you must also add adj[b].push(a) — forgetting this silently turns half your edges one-way.

1-Indexed Nodes, 0-Indexed Arrays

Many problems label nodes 1..N, but arrays (visited, adj) are naturally 0..N-1. Either size arrays to N+1 and ignore index 0, or subtract 1 consistently everywhere — mixing the two is a classic off-by-one source.

10
PRACTICE

Ready to Practice?

Course ScheduleMedium
Topological SortMedium
Number of ProvincesMedium

"A graph is just nodes that know their neighbors. Trace your links, remember where you've been, and never get trapped in a cycle."