Graph Basics

🗺️ Graph Fundamentals: Your Map to Connected Worlds

Imagine you have a bunch of cities, and roads connecting them. How would you figure out the best way to travel? That’s what graphs help us do!

🌟 The Big Picture: What is a Graph?

Think of a graph like a friendship map at school. Each kid is a dot (we call it a node or vertex), and when two kids are friends, we draw a line between them (we call it an edge).

   🧒 Alice
    |
    | (friends)
    |
   👦 Bob ———— 👧 Carol
         (friends)

That’s it! Graphs are just dots connected by lines. Simple, right?

📦 Graph Representation Methods

The Problem

How do we tell a computer about our friendship map? Computers don’t understand drawings. We need to write it down in a way they understand.

Method 1: Adjacency List 📋

“For each person, list all their friends”

Think of it like a phone contact list. Each person has their own list of friends:

// Alice is friends with Bob
// Bob is friends with Alice and Carol
// Carol is friends with Bob

const friendshipMap = {
  'Alice': ['Bob'],
  'Bob': ['Alice', 'Carol'],
  'Carol': ['Bob']
};

Why use this?

• ✅ Saves space when people have few friends
• ✅ Easy to find “Who are Bob’s friends?”

Method 2: Adjacency Matrix 🔢

“Make a big table with checkmarks”

Imagine a seating chart where ✓ means “these two are friends”:

        Alice  Bob  Carol
Alice     0     1     0
Bob       1     0     1
Carol     0     1     0

In code:

const matrix = [
  [0, 1, 0],  // Alice's row
  [1, 0, 1],  // Bob's row
  [0, 1, 0]   // Carol's row
];
// matrix[0][1] = 1 means Alice(0)
// and Bob(1) are friends

Why use this?

• ✅ Super fast to check “Are Alice and Carol friends?”
• ❌ Uses more space if few friendships exist

🎨 Graph Types and Properties

Directed vs Undirected

Undirected: Friendship goes both ways 🤝

Alice ——— Bob
(If Alice is Bob's friend, Bob is Alice's friend too)

Directed: Like following on Instagram 📱

Alice ——→ Bob
(Alice follows Bob, but Bob might not follow back!)

// Directed graph example
const following = {
  'Alice': ['Bob', 'Carol'],  // Alice follows these
  'Bob': ['Carol'],           // Bob follows Carol
  'Carol': []                 // Carol follows no one
};

Weighted vs Unweighted

Unweighted: All roads are equal

CityA ——— CityB

Weighted: Roads have distances! 🛣️

CityA ——5km—— CityB ——10km—— CityC

// Weighted graph: cities and distances
const roads = {
  'CityA': [{ to: 'CityB', distance: 5 }],
  'CityB': [
    { to: 'CityA', distance: 5 },
    { to: 'CityC', distance: 10 }
  ],
  'CityC': [{ to: 'CityB', distance: 10 }]
};

Cyclic vs Acyclic

Cyclic: You can walk in circles 🔄

A → B → C → A (back to start!)

Acyclic: No circles allowed

A → B → C (one way, no going back)

🌊 Breadth-First Search (BFS)

The Story

Imagine you’re looking for your lost puppy in a neighborhood. You’d check:

1. First, all houses on YOUR street (closest)
2. Then, all houses one street away
3. Then, all houses two streets away
4. And so on…

This is BFS! Check nearby things first, then go further.

graph TD
    A["Start: Your House"] --> B["Neighbor 1"]
    A --> C["Neighbor 2"]
    B --> D["Their Neighbor"]
    C --> E["Their Neighbor"]
    style A fill:#ff6b6b
    style B fill:#4ecdc4
    style C fill:#4ecdc4
    style D fill:#ffe66d
    style E fill:#ffe66d

The Code

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  while (queue.length > 0) {
    // Take the first person in line
    const node = queue.shift();

    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);

      // Add their friends to the line
      for (let neighbor of graph[node]) {
        queue.push(neighbor);
      }
    }
  }
  return result;
}

// Example usage
const friends = {
  'You': ['Amy', 'Ben'],
  'Amy': ['You', 'Carl'],
  'Ben': ['You', 'Dana'],
  'Carl': ['Amy'],
  'Dana': ['Ben']
};

console.log(bfs(friends, 'You'));
// Output: ['You', 'Amy', 'Ben', 'Carl', 'Dana']

Key insight: BFS uses a queue (first in, first out) - like a line at a store!

🏔️ Depth-First Search (DFS)

The Story

Now imagine you’re exploring a cave. You pick one tunnel and go as deep as possible until you hit a dead end. Then you backtrack and try another tunnel.

This is DFS! Go deep first, then backtrack.

graph TD
    A["Cave Entrance"] --> B["Tunnel 1"]
    A --> C["Tunnel 2"]
    B --> D["Deep Cave 1"]
    D --> E["Treasure!"]
    C --> F["Dead End"]
    style A fill:#ff6b6b
    style B fill:#4ecdc4
    style D fill:#4ecdc4
    style E fill:#ffe66d

The Code

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  const result = [start];

  for (let neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      // Go deeper!
      result.push(...dfs(graph, neighbor, visited));
    }
  }
  return result;
}

// Same friends example
console.log(dfs(friends, 'You'));
// Output: ['You', 'Amy', 'Carl', 'Ben', 'Dana']
// Notice: Goes deep through Amy→Carl first!

Key insight: DFS uses a stack (last in, first out) - or recursion naturally does this for us!

BFS vs DFS: When to Use?

🏝️ Connected Components

The Story

Imagine islands in the ocean. Some islands have bridges connecting them (they’re “connected”). Other islands are alone.

A connected component is a group of nodes where you can travel between any two of them.

Island Group 1:    Island Group 2:
   A --- B            D --- E
    \   /
     \ /
      C

(2 connected components!)

The Code

function findComponents(graph) {
  const visited = new Set();
  const components = [];

  for (let node in graph) {
    if (!visited.has(node)) {
      // Found a new island!
      const component = [];
      dfsCollect(graph, node, visited, component);
      components.push(component);
    }
  }
  return components;
}

function dfsCollect(graph, node, visited, component) {
  visited.add(node);
  component.push(node);

  for (let neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfsCollect(graph, neighbor, visited, component);
    }
  }
}

// Example with separate friend groups
const school = {
  'Alice': ['Bob'],
  'Bob': ['Alice', 'Carol'],
  'Carol': ['Bob'],
  'Dan': ['Eve'],  // Different group!
  'Eve': ['Dan']
};

console.log(findComponents(school));
// Output: [['Alice','Bob','Carol'], ['Dan','Eve']]

🐑 Clone Graph

The Story

Imagine you have a family tree and want to make an exact copy for your cousin. You can’t just point to the same tree - you need to recreate every person and every connection!

The Problem

Given a node, create a complete copy of the entire graph.

// A graph node looks like this:
class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

The Solution

function cloneGraph(node) {
  if (!node) return null;

  // Map: original node → its clone
  const cloned = new Map();

  function dfsClone(original) {
    // Already cloned? Return the clone
    if (cloned.has(original)) {
      return cloned.get(original);
    }

    // Create a new copy
    const copy = new GraphNode(original.val);
    cloned.set(original, copy);

    // Clone all neighbors
    for (let neighbor of original.neighbors) {
      copy.neighbors.push(dfsClone(neighbor));
    }

    return copy;
  }

  return dfsClone(node);
}

Key insight: Use a Map to remember what you’ve already copied. This prevents infinite loops and connects clones correctly!

📋 Deep Copy Patterns

The Problem

A shallow copy only copies the surface - changes to nested objects affect both copies! 😱

// SHALLOW COPY - Danger!
const original = { friends: ['Alice', 'Bob'] };
const shallow = { ...original };

shallow.friends.push('Carol');
console.log(original.friends);
// ['Alice', 'Bob', 'Carol'] - Original changed too!

Pattern 1: JSON Method (Simple but Limited)

const deep1 = JSON.parse(JSON.stringify(original));
// ✅ Works for simple data
// ❌ Loses functions, dates, undefined

Pattern 2: Recursive Deep Copy

function deepCopy(obj, seen = new Map()) {
  // Handle primitives and null
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }

  // Handle circular references
  if (seen.has(obj)) {
    return seen.get(obj);
  }

  // Handle arrays
  if (Array.isArray(obj)) {
    const arrCopy = [];
    seen.set(obj, arrCopy);
    for (let item of obj) {
      arrCopy.push(deepCopy(item, seen));
    }
    return arrCopy;
  }

  // Handle objects
  const objCopy = {};
  seen.set(obj, objCopy);
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      objCopy[key] = deepCopy(obj[key], seen);
    }
  }
  return objCopy;
}

Pattern 3: structuredClone (Modern JS)

const deep2 = structuredClone(original);
// ✅ Handles most cases including cycles
// ✅ Built into modern browsers/Node

Why Deep Copy Matters for Graphs

When cloning a graph, each node references other nodes. A shallow copy would mean:

• Your “copy” and original share the same neighbor objects
• Changing a neighbor in one changes it in both!

Deep copy ensures complete independence.

🎯 Quick Reference

🚀 You Did It!

You now understand:

• ✅ Two ways to represent graphs
• ✅ The difference between directed/undirected, weighted/unweighted
• ✅ How BFS explores level by level
• ✅ How DFS dives deep then backtracks
• ✅ How to find separate groups (connected components)
• ✅ How to make true copies of graphs

Remember: Graphs are everywhere - social networks, maps, the internet, your family tree! Now you have the tools to work with them all. 🎉