Up until now, we've dealt with linear data structures like arrays and linked lists, or hierarchical ones like trees. But the real world is messy. Relationships aren't always top-down; they're webs. That's where graphs come in. To make this concrete, let's build a simple "Professional Network" map—think a miniature LinkedIn—where we can track who knows whom and find paths between people.

Mapping the Professional Network

I usually prefer an adjacency list over an adjacency matrix for these kinds of projects. Why? Because most people aren't connected to everyone in the network. A matrix would waste a ton of memory on empty cells. In JavaScript, a Map is perfect for this because it allows us to associate a person's name with an array of their connections.

class SocialGraph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addPerson(person) {
    if (!this.adjacencyList.has(person)) {
      this.adjacencyList.set(person, []);
    }
  }

  addEdge(person1, person2) {
    this.adjacencyList.get(person1).push(person2);
    this.adjacencyList.get(person2).push(person1);
  }
}

const network = new SocialGraph();
network.addPerson("Alice");
network.addPerson("Bob");
network.addPerson("Charlie");
network.addPerson("Diana");

network.addEdge("Alice", "Bob");
network.addEdge("Bob", "Charlie");
network.addEdge("Charlie", "Diana");
network.addEdge("Alice", "Diana");

Finding the Shortest Connection with BFS

If I want to find the shortest path between Alice and Diana, I need Breadth-First Search (BFS). BFS explores the "neighborhood" first. It looks at all immediate friends, then all friends-of-friends, and so on. It's essentially a ripple effect in a pond.

I'll use a queue to keep track of who to visit next. I'm also going to keep a visited set so I don't end up walking in circles.

bfs(start, target) {
  const queue = [start];
  const visited = new Set([start]);
  const parentMap = { [start]: null }; // To reconstruct the path later

  while (queue.length > 0) {
    const current = queue.shift();

    if (current === target) {
      return this.reconstructPath(parentMap, target);
    }

    for (let neighbor of this.adjacencyList.get(current)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parentMap[neighbor] = current;
        queue.push(neighbor);
      }
    }
  }
  return null;
}

reconstructPath(parentMap, target) {
  const path = [];
  let current = target;
  while (current !== null) {
    path.push(current);
    current = parentMap[current];
  }
  return path.reverse();
}

The "Infinite Loop" Trap

Now, here is where I almost tripped up. When I first sketched out the Depth-First Search (DFS) version of this, I forgot to pass the visited set through the recursive calls. Because our graph is undirected (Alice knows Bob, and Bob knows Alice), the code just bounced back and forth between them until the stack overflowed.

It's a classic mistake. If your graph has any cycles—which almost every real-world graph does—you must track where you've been. If you don't, your program is basically a hiker who forgot their compass and keeps walking in a circle.

Exploring Every Avenue with DFS

While BFS is for shortest paths, Depth-First Search (DFS) is what you use when you need to explore as far as possible along a branch before backtracking. It's often cleaner to write using recursion. Let's implement it so we can find any path between two people, regardless of length.

dfs(start, target, visited = new Set()) {
  if (start === target) return [start];
  
  visited.add(start);

  for (let neighbor of this.adjacencyList.get(start)) {
    if (!visited.has(neighbor)) {
      const path = this.dfs(neighbor, target, visited);
      if (path) {
        return [start, ...path];
      }
    }
  }

  return null;
}

Notice how the visited set is passed along. By the time the recursion unwinds, we've either found the target or exhausted all possibilities. BFS is like a flood fill; DFS is like a maze solver.

📋 Practical Task

Exercise: Building a Degree-of-Separation Calculator

Using the SocialGraph logic from the lesson, create a program that calculates the "Degrees of Separation" between two people in a professional network.

• Create a SocialGraph instance.
• Add at least 6 people (e.g., "Alice", "Bob", "Charlie", "David", "Eve", "Frank").
• Create a complex web of connections (make sure some people are far apart).
• Implement a function called getDegreesOfSeparation(personA, personB). This function should use BFS to find the shortest path and return the number of edges (links) between them. For example, if Alice knows Bob and Bob knows Charlie, the degrees of separation between Alice and Charlie is 2.
• If no path exists, return -1.