
Graph: From Subway Maps to Facebook Friends
If Tree is Hierarchy, Graph is Web. Navigation and Friend Algorithm.

If Tree is Hierarchy, Graph is Web. Navigation and Friend Algorithm.
Why does my server crash? OS's desperate struggle to manage limited memory. War against Fragmentation.

Two ways to escape a maze. Spread out wide (BFS) or dig deep (DFS)? Who finds the shortest path?

Fast by name. Partitioning around a Pivot. Why is it the standard library choice despite O(N²) worst case?

Establishing TCP connection is expensive. Reuse it for multiple requests.

First time taking the Seoul subway. Stared at the route map. Totally lost.
"Take Line 2, transfer to Line 3... oh wait, Line 4 also works? Which one's faster?"Senior engineer: "That's a graph. Stations are vertices, lines are edges. The computer represents this as a data structure and finds the shortest path."
Me: "Graph? Like an Excel chart?"
Senior: (sighs) "No... a graph data structure... like arrays or trees, it's a way to store data."
Me: "How's it different from a tree? They both have dots and lines connecting them."
Senior: "Trees have a clear parent-child hierarchy and no cycles. Graphs are like friendships—equal relationships, cycles allowed. Alice friends with Bob, Bob friends with Charlie, Charlie friends back to Alice... like that."
That's when it clicked. Most relationships in the real world are graphs, not trees.At work, got assigned: "Build a friend recommendation feature."
Requirements:
Me: "Can't I just do a couple SQL JOINs?"
Senior: "What about someone with 10,000 friends? You gonna JOIN a billion rows?"
Me: (silence)
Senior: "This is a graph traversal problem. Use BFS to search level-by-level and efficiently find 2nd-degree connections. And if you implement it with an adjacency list, you'll use way less memory."
Started studying graphs properly then. Not just the concepts, but how to implement them and which approach to use when.Most confusing: "Why are there so many implementation approaches? There's no single answer?"
Senior drew this on the whiteboard:
Tree:
Company org chart CEO / \ Mgr A Mgr B / \ Dev Dev"Clear hierarchy. No cycles. Exactly one parent."
Graph:
Facebook friends Alice ─ Bob │ │ Charlie ─ Diana"Equal relationships. Cycles allowed. No parent-child concept."
Senior: "A tree is just a special case of a graph. N nodes, N-1 edges, no cycles, connected. Meet those 4 conditions? It's a tree."
"Oh, a tree is just a stricter version of a graph!" Got it.
This is where it gets real. How do you store a graph in memory?
2D array representation:
// 4 people friendship (undirected graph)
const graph = [
[0, 1, 1, 0], // 0(Alice): friends with 1, 2
[1, 0, 0, 1], // 1(Bob): friends with 0, 3
[1, 0, 0, 1], // 2(Charlie): friends with 0, 3
[0, 1, 1, 0] // 3(Diana): friends with 1, 2
];
// Check if Alice(0) and Bob(1) are friends
console.log(graph[0][1] === 1); // true - O(1) instant!
// Find all of Bob's friends
const bobFriends = [];
for (let i = 0; i < graph[1].length; i++) {
if (graph[1][i] === 1) {
bobFriends.push(i); // O(V) - must check all vertices
}
}
console.log(bobFriends); // [0, 3]
When does adjacency matrix win?
Dense graphs: When edges approach V²
Fast edge lookup critical: When "Are A and B friends?" queries happen constantly
Weighted graphs: Store distance or cost directly in array values
const distances = [
[0, 15, 20, 0], // Alice → Bob 15km, Charlie 20km
[15, 0, 0, 30], // Bob → Diana 30km
[20, 0, 0, 25],
[0, 30, 25, 0]
];
Cons (critical):
Store only each person's friend list:
// Implemented with Map or Object
const graph = new Map();
graph.set('Alice', ['Bob', 'Charlie']);
graph.set('Bob', ['Alice', 'Diana']);
graph.set('Charlie', ['Alice', 'Diana']);
graph.set('Diana', ['Bob', 'Charlie']);
// Alice's friends - O(1)
console.log(graph.get('Alice')); // ['Bob', 'Charlie']
// Check if Alice and Bob are friends - O(degree)
const isFriend = graph.get('Alice').includes('Bob'); // true
// degree = number of edges for that vertex (Alice has 2 friends → O(2))
When does adjacency list dominate?
Sparse graphs: Most real-world cases
BFS/DFS traversal: When you only need neighbors
// Adjacency list: direct access to Alice's friends
const neighbors = graph.get('Alice'); // ['Bob', 'Charlie']
// Adjacency matrix: must check all people
for (let i = 0; i < matrix[0].length; i++) {
if (matrix[0][i] === 1) neighbors.push(i);
}
Dynamic graphs: Frequent friend add/remove
// List: just push/filter on array
graph.get('Alice').push('Eve'); // O(1)
// Matrix: adding new person requires recreating entire array
Lesson learned: In practice, use adjacency list 90%+ of the time. Matrix only for dense graphs or competitive programming.
Enough theory. Here's working code I built.
class Graph {
constructor(directed = false) {
this.adjacencyList = new Map();
this.directed = directed; // directed/undirected
}
// Add vertex
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
// Add edge
addEdge(v1, v2, weight = 1) {
// Create vertices if don't exist
this.addVertex(v1);
this.addVertex(v2);
// Add v1 → v2
this.adjacencyList.get(v1).push({ node: v2, weight });
// If undirected, add v2 → v1 too
if (!this.directed) {
this.adjacencyList.get(v2).push({ node: v1, weight });
}
}
// Remove vertex
removeVertex(vertex) {
if (!this.adjacencyList.has(vertex)) return;
// Remove all edges pointing to this vertex
for (let [v, edges] of this.adjacencyList) {
this.adjacencyList.set(
v,
edges.filter(e => e.node !== vertex)
);
}
// Delete vertex itself
this.adjacencyList.delete(vertex);
}
// Remove edge
removeEdge(v1, v2) {
if (!this.adjacencyList.has(v1) || !this.adjacencyList.has(v2)) return;
this.adjacencyList.set(
v1,
this.adjacencyList.get(v1).filter(e => e.node !== v2)
);
if (!this.directed) {
this.adjacencyList.set(
v2,
this.adjacencyList.get(v2).filter(e => e.node !== v1)
);
}
}
// BFS implementation
bfs(start) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const current = queue.shift();
result.push(current);
const neighbors = this.adjacencyList.get(current) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
visited.add(edge.node);
queue.push(edge.node);
}
}
}
return result;
}
// DFS implementation (iterative)
dfsIterative(start) {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length > 0) {
const current = stack.pop();
if (!visited.has(current)) {
visited.add(current);
result.push(current);
const neighbors = this.adjacencyList.get(current) || [];
// Reverse order for stack (adjusts pop order)
for (let i = neighbors.length - 1; i >= 0; i--) {
if (!visited.has(neighbors[i].node)) {
stack.push(neighbors[i].node);
}
}
}
}
return result;
}
// DFS implementation (recursive)
dfsRecursive(start, visited = new Set(), result = []) {
visited.add(start);
result.push(start);
const neighbors = this.adjacencyList.get(start) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
this.dfsRecursive(edge.node, visited, result);
}
}
return result;
}
// Check if path exists
hasPath(start, end) {
if (start === end) return true;
const visited = new Set();
const queue = [start];
visited.add(start);
while (queue.length > 0) {
const current = queue.shift();
const neighbors = this.adjacencyList.get(current) || [];
for (let edge of neighbors) {
if (edge.node === end) return true;
if (!visited.has(edge.node)) {
visited.add(edge.node);
queue.push(edge.node);
}
}
}
return false;
}
// Print graph
print() {
for (let [vertex, edges] of this.adjacencyList) {
const edgeStr = edges.map(e => `${e.node}(${e.weight})`).join(', ');
console.log(`${vertex} → ${edgeStr}`);
}
}
}
// Usage example
const g = new Graph(false); // undirected graph
g.addEdge('Alice', 'Bob');
g.addEdge('Alice', 'Charlie');
g.addEdge('Bob', 'Diana');
g.addEdge('Charlie', 'Diana');
console.log('Graph structure:');
g.print();
// Alice → Bob(1), Charlie(1)
// Bob → Alice(1), Diana(1)
// Charlie → Alice(1), Diana(1)
// Diana → Bob(1), Charlie(1)
console.log('BFS traversal:', g.bfs('Alice'));
// ['Alice', 'Bob', 'Charlie', 'Diana']
console.log('DFS traversal:', g.dfsIterative('Alice'));
// ['Alice', 'Bob', 'Diana', 'Charlie']
console.log('Path Alice → Diana exists?', g.hasPath('Alice', 'Diana'));
// true
Key learnings from this implementation:
Let's revisit friend recommendations. This time tracking levels.
class GraphWithLevels extends Graph {
bfsWithLevels(start, maxLevel = Infinity) {
const visited = new Set([start]);
const queue = [{ node: start, level: 0 }];
const levels = new Map();
levels.set(start, 0);
while (queue.length > 0) {
const { node, level } = queue.shift();
if (level >= maxLevel) continue;
const neighbors = this.adjacencyList.get(node) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
visited.add(edge.node);
levels.set(edge.node, level + 1);
queue.push({ node: edge.node, level: level + 1 });
}
}
}
return levels;
}
// Friend recommendations: up to 2nd degree, exclude 1st degree
recommendFriends(userId) {
const levels = this.bfsWithLevels(userId, 2);
const recommendations = [];
for (let [user, level] of levels) {
if (level === 2) { // 2nd degree only
recommendations.push(user);
}
}
return recommendations;
}
// Recommend based on mutual friends count
recommendWithCommonFriends(userId) {
const myFriends = new Set(
this.adjacencyList.get(userId).map(e => e.node)
);
const candidates = new Map(); // candidate → mutual friend count
// Explore friends of my friends
for (let edge of this.adjacencyList.get(userId)) {
const friend = edge.node;
const friendsOfFriend = this.adjacencyList.get(friend) || [];
for (let fofEdge of friendsOfFriend) {
const fof = fofEdge.node;
// Not me, not already friend
if (fof !== userId && !myFriends.has(fof)) {
candidates.set(fof, (candidates.get(fof) || 0) + 1);
}
}
}
// Sort by mutual friend count
return Array.from(candidates.entries())
.sort((a, b) => b[1] - a[1])
.map(([user, count]) => ({ user, commonFriends: count }));
}
}
// Real usage
const social = new GraphWithLevels(false);
social.addEdge('Me', 'Alice');
social.addEdge('Me', 'Bob');
social.addEdge('Alice', 'Charlie');
social.addEdge('Alice', 'Diana');
social.addEdge('Bob', 'Charlie');
social.addEdge('Bob', 'Eve');
console.log('Relationships by level:');
console.log(social.bfsWithLevels('Me'));
// Map {
// 'Me' => 0,
// 'Alice' => 1, 'Bob' => 1,
// 'Charlie' => 2, 'Diana' => 2, 'Eve' => 2
// }
console.log('Friend recommendations (2nd degree):');
console.log(social.recommendFriends('Me'));
// ['Charlie', 'Diana', 'Eve']
console.log('Recommendations by mutual friends:');
console.log(social.recommendWithCommonFriends('Me'));
// [
// { user: 'Charlie', commonFriends: 2 }, // Alice + Bob
// { user: 'Diana', commonFriends: 1 }, // Alice only
// { user: 'Eve', commonFriends: 1 } // Bob only
// ]
Real-world insight: Facebook actually does this. More mutual friends = higher ranking.
For directed graphs, finding the right order.
Example: University course prerequisitesData Structures → Algorithms
Intro to Programming → Data Structures
Intro to Programming → Operating Systems
Operating Systems → Systems Programming
"What order should I take these courses?"
class DirectedGraph extends Graph {
constructor() {
super(true); // directed
}
// Topological sort (DFS-based)
topologicalSort() {
const visited = new Set();
const stack = [];
const dfsHelper = (vertex) => {
visited.add(vertex);
const neighbors = this.adjacencyList.get(vertex) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
dfsHelper(edge.node);
}
}
// Add to stack in post-order
stack.push(vertex);
};
// Visit all vertices (handle disconnected components)
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
dfsHelper(vertex);
}
}
// Reverse is the topological order
return stack.reverse();
}
// Cycle detection (can we do topological sort?)
hasCycle() {
const visited = new Set();
const recStack = new Set(); // current recursion stack
const dfsHelper = (vertex) => {
visited.add(vertex);
recStack.add(vertex);
const neighbors = this.adjacencyList.get(vertex) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
if (dfsHelper(edge.node)) return true;
} else if (recStack.has(edge.node)) {
// In recursion stack = cycle!
return true;
}
}
recStack.delete(vertex); // backtrack
return false;
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
if (dfsHelper(vertex)) return true;
}
}
return false;
}
}
// Course prerequisite graph
const courses = new DirectedGraph();
courses.addEdge('Intro to Programming', 'Data Structures');
courses.addEdge('Intro to Programming', 'Operating Systems');
courses.addEdge('Data Structures', 'Algorithms');
courses.addEdge('Operating Systems', 'Systems Programming');
console.log('Course order:');
console.log(courses.topologicalSort());
// ['Intro to Programming', 'Operating Systems', 'Data Structures',
// 'Systems Programming', 'Algorithms']
// Or ['Intro to Programming', 'Data Structures', 'Operating Systems',
// 'Algorithms', 'Systems Programming']
// (Multiple valid answers)
console.log('Has cycle?', courses.hasCycle()); // false
// Add circular prerequisite
courses.addEdge('Algorithms', 'Intro to Programming'); // Oops!
console.log('Now has cycle?', courses.hasCycle()); // true
Real-world applications:
In undirected graphs: "How many independent groups exist?"
class UndirectedGraph extends Graph {
constructor() {
super(false); // undirected
}
findConnectedComponents() {
const visited = new Set();
const components = [];
const dfs = (start, component) => {
visited.add(start);
component.push(start);
const neighbors = this.adjacencyList.get(start) || [];
for (let edge of neighbors) {
if (!visited.has(edge.node)) {
dfs(edge.node, component);
}
}
};
for (let vertex of this.adjacencyList.keys()) {
if (!visited.has(vertex)) {
const component = [];
dfs(vertex, component);
components.push(component);
}
}
return components;
}
}
// Find friend groups in SNS
const sns = new UndirectedGraph();
// Group 1
sns.addEdge('Alice', 'Bob');
sns.addEdge('Bob', 'Charlie');
// Group 2 (independent)
sns.addEdge('Diana', 'Eve');
// Group 3 (alone)
sns.addVertex('Frank');
console.log('Friend groups:');
console.log(sns.findConnectedComponents());
// [
// ['Alice', 'Bob', 'Charlie'],
// ['Diana', 'Eve'],
// ['Frank']
// ]
Real applications: Network analysis, community detection, image segmentation
In weighted graphs: "Connect all vertices with minimum total cost"
Example: Connecting islands with bridges, minimize construction cost// Kruskal's algorithm (simplified)
class WeightedGraph extends Graph {
getAllEdges() {
const edges = [];
const seen = new Set();
for (let [v1, neighbors] of this.adjacencyList) {
for (let { node: v2, weight } of neighbors) {
const edgeKey = [v1, v2].sort().join('-');
if (!seen.has(edgeKey)) {
edges.push({ v1, v2, weight });
seen.add(edgeKey);
}
}
}
return edges.sort((a, b) => a.weight - b.weight);
}
// Simple Union-Find (real implementation needs optimization)
kruskalMST() {
const edges = this.getAllEdges();
const mst = [];
const parent = new Map();
// Each vertex is its own parent initially
for (let vertex of this.adjacencyList.keys()) {
parent.set(vertex, vertex);
}
const find = (v) => {
if (parent.get(v) !== v) {
parent.set(v, find(parent.get(v)));
}
return parent.get(v);
};
const union = (v1, v2) => {
const root1 = find(v1);
const root2 = find(v2);
if (root1 !== root2) {
parent.set(root1, root2);
return true;
}
return false;
};
for (let { v1, v2, weight } of edges) {
if (union(v1, v2)) {
mst.push({ v1, v2, weight });
}
}
return mst;
}
}
// Island connection problem
const islands = new WeightedGraph(false);
islands.addEdge('Jeju', 'Mokpo', 150);
islands.addEdge('Jeju', 'Busan', 280);
islands.addEdge('Mokpo', 'Busan', 200);
islands.addEdge('Mokpo', 'Yeosu', 50);
islands.addEdge('Busan', 'Yeosu', 80);
console.log('Minimum cost bridges:');
console.log(islands.kruskalMST());
// [
// { v1: 'Mokpo', v2: 'Yeosu', weight: 50 },
// { v1: 'Busan', v2: 'Yeosu', weight: 80 },
// { v1: 'Jeju', v2: 'Mokpo', weight: 150 }
// ]
// Total cost: 280
The key insight: Add cheapest edges first, but don't create cycles.
"Color adjacent vertices with different colors, minimize number of colors"
Real example: Exam scheduling
class ColoringGraph extends Graph {
greedyColoring() {
const color = new Map();
const vertices = Array.from(this.adjacencyList.keys());
// First vertex gets color 0
color.set(vertices[0], 0);
for (let i = 1; i < vertices.length; i++) {
const vertex = vertices[i];
// Check colors of adjacent vertices
const neighbors = this.adjacencyList.get(vertex) || [];
const usedColors = new Set();
for (let edge of neighbors) {
if (color.has(edge.node)) {
usedColors.add(color.get(edge.node));
}
}
// Find smallest unused color
let assignedColor = 0;
while (usedColors.has(assignedColor)) {
assignedColor++;
}
color.set(vertex, assignedColor);
}
return color;
}
}
// Exam scheduling (courses taken by same student are adjacent)
const exams = new ColoringGraph(false);
exams.addEdge('Math', 'Physics'); // Same student takes both
exams.addEdge('Math', 'Chemistry');
exams.addEdge('Physics', 'Biology');
exams.addEdge('Chemistry', 'Biology');
exams.addEdge('English', 'History');
console.log('Exam schedule:');
const schedule = exams.greedyColoring();
for (let [exam, timeSlot] of schedule) {
console.log(`${exam}: Period ${timeSlot}`);
}
// Math: Period 0
// Physics: Period 1
// Chemistry: Period 1 (doesn't conflict with Math)
// Biology: Period 0 (doesn't conflict with Physics or Chemistry)
// English: Period 0
// History: Period 1
Minimum colors = minimum exam days needed
| Scenario | Representation | Algorithm | Time Complexity |
|---|---|---|---|
| Sparse graph (SNS) | Adjacency list | BFS (friend recommendation) | O(V + E) |
| Dense graph (small complete) | Adjacency matrix | - | O(V²) space |
| Shortest path (unweighted) | List | BFS | O(V + E) |
| Shortest path (weighted) | List | Dijkstra | O((V + E) log V) |
| Course prerequisites | List | Topological sort | O(V + E) |
| Cycle detection | List | DFS | O(V + E) |
| Number of components | List | DFS/BFS | O(V + E) |
| Minimum cost connection | List | Kruskal/Prim | O(E log E) |
| Scheduling | List | Graph coloring | O(V² + E) |
Core insight: Almost always use adjacency list. BFS for shortest distance, DFS for path exploration and cycles.
Initially thought "What does a subway map have to do with my code?"
Six months later, things I've built with graphs:
Key takeaways:
The moment it clicked: "All relationships are graphs." Facebook, YouTube, Google, Uber... all running on graphs.
When facing new problems, just ask: "What are the vertices and what are the edges?" The answer becomes clear.
"This looks familiar..." → It's a graph.