Graph Analysis

Graph Analysis: The Detective’s Guide to Understanding Networks 🕵️

Imagine you’re a detective in a city full of roads. Some roads go one way, some go both ways. Your job? Find secret loops, discover hidden communities, and figure out the right order to do things. That’s exactly what Graph Analysis is all about!

🌍 Our Everyday Metaphor: The City Road Network

Think of a graph like a city map:

• Nodes = Buildings or locations
• Edges = Roads connecting them
• Directed edges = One-way streets
• Undirected edges = Two-way streets

Every concept we learn today is like a different detective skill for exploring this city!

🔄 Cycle Detection in Graphs

What is a Cycle?

A cycle is when you can start at one place, follow the roads, and end up exactly where you started!

Simple Example:

• House → School → Park → House
• You went in a circle!

Why Find Cycles?

Cycles can cause problems! Imagine:

• A delivery truck stuck in a loop forever
• A computer program that never stops

How Do We Detect Cycles?

We use colors like a traffic light:

• White = Not visited yet
• Gray = Currently exploring (on our path)
• Black = Done exploring

If we see a gray node while exploring, we found a cycle!

function hasCycle(graph) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(graph.length).fill(WHITE);

  function dfs(node) {
    color[node] = GRAY;
    for (let neighbor of graph[node]) {
      if (color[neighbor] === GRAY) return true;
      if (color[neighbor] === WHITE && dfs(neighbor)) {
        return true;
      }
    }
    color[node] = BLACK;
    return false;
  }

  for (let i = 0; i < graph.length; i++) {
    if (color[i] === WHITE && dfs(i)) return true;
  }
  return false;
}

🏘️ Strongly Connected Components (SCCs)

What are SCCs?

Imagine neighborhoods in a city where you can walk from ANY house to ANY other house using one-way streets. That’s a Strongly Connected Component!

Simple Example:

• In neighborhood A: House 1 → House 2 → House 3 → House 1
• Everyone can visit everyone else!

Why Do We Care?

SCCs help us:

• Find tight-knit communities
• Simplify complex networks
• Understand how information flows

Kosaraju’s Algorithm (Two-Pass Magic)

1. First Pass: Walk through the graph, note when you finish each node
2. Reverse: Flip all the one-way streets
3. Second Pass: Walk through in reverse finish order

function findSCCs(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const order = [];

  // First DFS - record finish order
  function dfs1(node) {
    visited[node] = true;
    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) dfs1(neighbor);
    }
    order.push(node);
  }

  // Build reversed graph
  const reversed = Array.from({length: n}, () => []);
  for (let i = 0; i < n; i++) {
    for (let j of graph[i]) reversed[j].push(i);
  }

  // Second DFS on reversed graph
  visited.fill(false);
  const sccs = [];

  while (order.length) {
    const node = order.pop();
    if (!visited[node]) {
      const component = [];
      function dfs2(v) {
        visited[v] = true;
        component.push(v);
        for (let neighbor of reversed[v]) {
          if (!visited[neighbor]) dfs2(neighbor);
        }
      }
      dfs2(node);
      sccs.push(component);
    }
  }
  return sccs;
}

🎨 Bipartite Graph Check

What is a Bipartite Graph?

Imagine dividing kids into two teams for a game. A bipartite graph is when you can split all nodes into exactly TWO groups, and every edge only connects nodes from DIFFERENT groups.

Simple Example:

• Team Red: Alice, Bob
• Team Blue: Charlie, Diana
• All friendships are between teams!

The Two-Color Test

Try to color every node with just 2 colors. If neighbors ever have the same color, it’s NOT bipartite!

function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(-1);

  function bfs(start) {
    const queue = [start];
    color[start] = 0;

    while (queue.length) {
      const node = queue.shift();
      for (let neighbor of graph[node]) {
        if (color[neighbor] === -1) {
          color[neighbor] = 1 - color[node];
          queue.push(neighbor);
        } else if (color[neighbor] === color[node]) {
          return false;
        }
      }
    }
    return true;
  }

  for (let i = 0; i < n; i++) {
    if (color[i] === -1 && !bfs(i)) return false;
  }
  return true;
}

🌈 Graph Coloring

What is Graph Coloring?

Give every node a color, but neighbors can’t share the same color. Like seating enemies at different tables!

Simple Example:

• Alice hates Bob, Bob hates Charlie
• Alice = Red, Bob = Blue, Charlie = Red
• No neighbors share colors!

The Greedy Approach

Go through each node and give it the smallest color that none of its neighbors have.

function greedyColoring(graph) {
  const n = graph.length;
  const result = new Array(n).fill(-1);
  result[0] = 0;

  for (let node = 1; node < n; node++) {
    const usedColors = new Set();
    for (let neighbor of graph[node]) {
      if (result[neighbor] !== -1) {
        usedColors.add(result[neighbor]);
      }
    }

    let color = 0;
    while (usedColors.has(color)) color++;
    result[node] = color;
  }
  return result;
}

📋 Topological Sort

What is Topological Sort?

Imagine getting dressed. You MUST put on underwear before pants, shirt before jacket. Topological sort puts tasks in the right order!

Simple Example:

• Underwear → Pants → Shoes
• Shirt → Jacket
• Result: Underwear, Shirt, Pants, Jacket, Shoes

The Rule

In a topological order, every directed edge goes from an earlier node to a later node. Only works for graphs WITHOUT cycles!

function topologicalSort(graph) {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const result = [];

  function dfs(node) {
    visited[node] = true;
    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) dfs(neighbor);
    }
    result.unshift(node);
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i);
  }
  return result;
}

📬 Kahn’s Algorithm

Another Way to Sort!

Kahn’s Algorithm uses a simple idea: start with nodes that have no dependencies!

Think of it like peeling an onion:

1. Find all nodes with no incoming edges
2. Remove them, update counts
3. Repeat until done!

function kahnsAlgorithm(graph) {
  const n = graph.length;
  const inDegree = new Array(n).fill(0);

  // Count incoming edges
  for (let node = 0; node < n; node++) {
    for (let neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  // Start with zero in-degree nodes
  const queue = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (let neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === n ? result : [];
}

📚 Course Schedule Problems

The Classic Problem

You have courses to take, but some courses need prerequisites!

Example:

• Course 0: No prerequisites
• Course 1: Needs Course 0
• Course 2: Needs Course 0 AND Course 1

Question: Can you finish all courses?

Solution: Cycle Detection + Topological Sort!

If there’s a cycle in prerequisites, you can NEVER finish!

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (let [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let count = 0;
  while (queue.length) {
    const node = queue.shift();
    count++;
    for (let neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return count === numCourses;
}

Finding the Order

function findOrder(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (let [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (let neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === numCourses ? order : [];
}

👽 Alien Dictionary

The Mystery

You found a list of alien words sorted in their alphabet order. Can you figure out their alphabet?

Example:

Words: ["wrt", "wrf", "er", "ett", "rftt"]
Alien alphabet: w → e → r → t → f

The Detective Work

1. Compare adjacent words to find letter order
2. Build a graph of letter relationships
3. Topological sort gives the alphabet!

function alienOrder(words) {
  // Build graph
  const graph = new Map();
  const inDegree = new Map();

  // Initialize all characters
  for (let word of words) {
    for (let c of word) {
      if (!graph.has(c)) {
        graph.set(c, new Set());
        inDegree.set(c, 0);
      }
    }
  }

  // Compare adjacent words
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];

    // Check invalid case
    if (w1.length > w2.length && w1.startsWith(w2)) {
      return "";
    }

    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        if (!graph.get(w1[j]).has(w2[j])) {
          graph.get(w1[j]).add(w2[j]);
          inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
        }
        break;
      }
    }
  }

  // Kahn's algorithm
  const queue = [];
  for (let [char, degree] of inDegree) {
    if (degree === 0) queue.push(char);
  }

  let result = "";
  while (queue.length) {
    const c = queue.shift();
    result += c;
    for (let neighbor of graph.get(c)) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) queue.push(neighbor);
    }
  }

  return result.length === graph.size ? result : "";
}

🎯 The Big Picture

graph LR
    A["Graph Analysis"] --> B["Cycle Detection"]
    A --> C["SCCs"]
    A --> D["Bipartite Check"]
    A --> E["Graph Coloring"]
    A --> F["Topological Sort"]
    F --> G[Kahn's Algorithm]
    F --> H["Course Schedule"]
    F --> I["Alien Dictionary"]

    B --> J["Uses: DFS + Colors"]
    C --> K["Uses: Two-Pass DFS"]
    D --> L["Uses: BFS + 2 Colors"]
    E --> M["Uses: Greedy"]
    G --> N["Uses: In-Degree Queue"]

🏆 Summary: Your Detective Toolkit

💡 Remember This!

1. Cycles = Going in circles (bad for scheduling!)
2. SCCs = Neighborhoods where everyone can reach everyone
3. Bipartite = Can divide into exactly 2 teams
4. Topological Sort = Put tasks in the right order
5. Kahn’s = Start with items that have no dependencies

You’re now a Graph Detective! Go explore those networks! 🚀