Graph: From Subway Maps to Facebook Friends

Prologue: "Wait, there are multiple routes?"

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.

Why I Studied This

At work, got assigned: "Build a friend recommendation feature."

Requirements:

1. Recommend friends of friends.
2. Exclude people already friends with.
3. Prioritize by number of mutual friends.

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.

What Confused Me Initially

• How's it different from a tree? Both have nodes and edges, right?
• Adjacency matrix? Adjacency list? Which is better? When do I use what?
• BFS, DFS? Why two algorithms? What's the difference?
• Memory usage? If someone has 10,000 friends, how big does the array get?
• Topological sort? Minimum spanning tree? Even the names are intimidating...

Most confusing: "Why are there so many implementation approaches? There's no single answer?"

The Aha Moment: "Friendships have no hierarchy"

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.

Deep Dive 1: Adjacency Matrix vs List - The Memory War

This is where it gets real. How do you store a graph in memory?

Adjacency Matrix

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?

1. Dense graphs: When edges approach V²

   • Example: Small social group where everyone's friends with everyone (10 people all mutual friends)
   • Memory: O(V²) → 10² = 100 slots. Edges: 45. Space efficiency 45%

2. Fast edge lookup critical: When "Are A and B friends?" queries happen constantly

   • O(1) time instant answer
   • Games: "Can this character see that character?" real-time checks

3. 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):

• Space: O(V²) → 10K friends = 10K × 10K = 100M cells = 400MB (assuming int)
• Get friend list: O(V) → must scan entire row

Adjacency List

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?

1. Sparse graphs: Most real-world cases

   • Facebook: Average 338 friends (2014 data). V = 3 billion, E = 3B × 338 / 2
   • Matrix: 3B² = 9 × 10¹⁸ cells (impossible)
   • List: 3B + 3B × 338 / 2 ≈ 500B cells (possible)

2. 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);
   }
   

3. 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.

Deep Dive 2: Full Graph Class Implementation

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:

1. Map vs Object: Map is cleaner. Can use objects as keys, easier size tracking
2. visited Set is crucial: Without it, infinite loops (because of cycles)
3. BFS uses Queue, DFS uses Stack: The data structure IS the algorithm

Deep Dive 3: BFS Complete Analysis - Level Tracking

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.

Deep Dive 4: DFS Applications - Topological Sort

For directed graphs, finding the right order.

Example: University course prerequisites

Data 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:

• Build systems (Makefile, Webpack): File A depends on B → determine order
• Task scheduling: Task A must finish before Task B starts
• Package managers (npm, pip): Dependency resolution order

Deep Dive 5: Connected Components

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

Deep Dive 6: Minimum Spanning Tree - Brief Intro

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.

Deep Dive 7: Graph Coloring Problem

"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

Summary: When to Use What

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.

Closing: "The world is a graph"

Initially thought "What does a subway map have to do with my code?"

Six months later, things I've built with graphs:

• Friend recommendation system (BFS, 2nd-degree search)
• Social feed ranking (PageRank variant)
• Task dependency management (topological sort)
• Network failure detection (connected components)
• Delivery shortest route (Dijkstra)

Key takeaways:

1. Tree vs Graph: Tree is hierarchy, graph is relationships
2. Matrix vs List: 90% of the time, use list (sparse graphs)
3. BFS vs DFS: BFS for levels/shortest, DFS for depth/cycles
4. visited Set essential: Without it, infinite loops
5. Directionality matters: Follow (directed) vs Friends (undirected)

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.