Graph Analysis

🕵️ Graph Detective Academy: Uncovering Hidden Patterns

Welcome, young detective! Today we explore the secret world of graphs—finding loops, groups, and hidden orders!

🎯 Our Adventure Map

Think of a graph like a treasure map with islands (nodes) connected by bridges (edges). Today, we become graph detectives who:

1. Find loops (cycles) in our map
2. Discover tight-knit groups (strongly connected components)
3. Check if we can divide islands into two teams (bipartite check)
4. Paint islands with colors so neighbors differ (graph coloring)
5. Find the right order to do things (topological sort)
6. Use Kahn’s clever trick for ordering
7. Solve course schedule puzzles
8. Decode an alien dictionary

🔄 Cycle Detection: Finding the Loop!

What’s a Cycle?

Imagine walking through a maze. If you can walk from your room, through other rooms, and end up back where you started—that’s a cycle!

graph TD
    A((🏠 Home)) --> B((🏪 Shop))
    B --> C((🏫 School))
    C --> A

Real Life Example:

• You leave home → go to shop → go to school → return home
• That’s a cycle! You made a complete loop.

How to Detect Cycles

For Directed Graphs (one-way streets):

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY  # "I'm visiting!"
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True  # Found cycle!
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        color[node] = BLACK  # "Done visiting"
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False

The Color Code:

• ⚪ WHITE = “Not visited yet”
• 🔘 GRAY = “Currently exploring”
• ⚫ BLACK = “Completely done”

The Magic Rule: If you see a GRAY node while exploring, you’ve found a cycle!

🏘️ Strongly Connected Components (SCCs)

What Are SCCs?

Imagine a group of friends where everyone can reach everyone else through paths. That’s a Strongly Connected Component!

graph TD
    subgraph "SCC 1"
    A((Alice)) --> B((Bob))
    B --> C((Carol))
    C --> A
    end
    subgraph "SCC 2"
    D((Dave)) --> E((Eve))
    E --> D
    end
    C --> D

Finding SCCs with Kosaraju’s Algorithm

Think of it like a two-pass treasure hunt:

1. First Pass: Walk everywhere and note when you finish each place
2. Flip all bridges (reverse all edges)
3. Second Pass: Start from the latest finish time, find groups

def kosaraju_scc(graph):
    n = len(graph)
    visited = [False] * n
    finish_order = []

    # Step 1: DFS and record finish times
    def dfs1(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs1(neighbor)
        finish_order.append(node)

    for i in range(n):
        if not visited[i]:
            dfs1(i)

    # Step 2: Reverse the graph
    reversed_graph = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            reversed_graph[v].append(u)

    # Step 3: DFS in reverse finish order
    visited = [False] * n
    sccs = []

    def dfs2(node, component):
        visited[node] = True
        component.append(node)
        for neighbor in reversed_graph[node]:
            if not visited[neighbor]:
                dfs2(neighbor, component)

    for node in reversed(finish_order):
        if not visited[node]:
            component = []
            dfs2(node, component)
            sccs.append(component)

    return sccs

👥 Bipartite Graph Check: Two Teams!

What’s a Bipartite Graph?

Can you split all people into two teams so that:

• Team Red people only connect to Team Blue
• Team Blue people only connect to Team Red

graph LR
    subgraph "Team 🔴"
    A((A))
    C((C))
    end
    subgraph "Team 🔵"
    B((B))
    D((D))
    end
    A --- B
    A --- D
    C --- B
    C --- D

Real Life: Dating apps! Men on one side, women on the other. Connections only between sides.

The Two-Color Test

def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n  # -1 = uncolored

    def bfs(start):
        queue = [start]
        color[start] = 0  # Red team

        while queue:
            node = queue.pop(0)
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    # Color opposite
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False  # Same color = not bipartite!
        return True

    for i in range(n):
        if color[i] == -1:
            if not bfs(i):
                return False
    return True

Simple Rule: If any neighbor has the same color, it’s NOT bipartite!

🎨 Graph Coloring: The Map Puzzle

What’s Graph Coloring?

Color all nodes so that no two neighbors share the same color. Use as few colors as possible!

graph TD
    A((🔴 A)) --- B((🔵 B))
    A --- C((🟢 C))
    B --- C
    B --- D((🔴 D))
    C --- D

Real Life: Coloring a map so no touching countries share a color!

Greedy Coloring Algorithm

def greedy_coloring(graph):
    n = len(graph)
    result = [-1] * n  # No color assigned

    for node in range(n):
        # Find colors used by neighbors
        neighbor_colors = set()
        for neighbor in graph[node]:
            if result[neighbor] != -1:
                neighbor_colors.add(result[neighbor])

        # Pick smallest unused color
        color = 0
        while color in neighbor_colors:
            color += 1
        result[node] = color

    return result

Fun Fact: Any map can be colored with just 4 colors!

📋 Topological Sort: The Right Order

What’s Topological Sort?

Find an order to do tasks when some tasks depend on others.

Example: Getting dressed!

• Must wear underwear BEFORE pants
• Must wear shirt BEFORE jacket
• Must wear socks BEFORE shoes

graph TD
    U["Underwear"] --> P["Pants"]
    P --> SH["Shoes"]
    SO["Socks"] --> SH
    S["Shirt"] --> J["Jacket"]

One valid order: Underwear → Socks → Pants → Shoes → Shirt → Jacket

DFS-Based Topological Sort

def topological_sort(graph):
    n = len(graph)
    visited = [False] * n
    result = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)  # Add when done

    for i in range(n):
        if not visited[i]:
            dfs(i)

    return result[::-1]  # Reverse!

Key Insight: Add nodes to result when you’re done exploring them, then reverse!

📊 Kahn’s Algorithm: Count and Queue

A Different Approach to Topological Sort

Instead of DFS, Kahn’s Algorithm uses in-degree counting:

1. Count incoming edges for each node
2. Start with nodes that have zero incoming edges
3. Remove them, update counts, repeat!

from collections import deque

def kahns_algorithm(graph, n):
    # Count incoming edges
    in_degree = [0] * n
    for node in range(n):
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # Start with zero in-degree nodes
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)

    result = []
    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If result has all nodes, no cycle!
    if len(result) == n:
        return result
    return []  # Cycle exists!

Bonus: Kahn’s algorithm also detects cycles! If result is incomplete, there’s a cycle.

📚 Course Schedule Problems

The Classic Problem

You have courses with prerequisites. Can you finish all courses?

Example:

• Course 1 requires Course 0
• Course 2 requires Course 1
• Course 3 requires Course 0

graph TD
    C0["Course 0"] --> C1["Course 1"]
    C1 --> C2["Course 2"]
    C0 --> C3["Course 3"]

Solution: Detect Cycle + Topological Sort

def can_finish(numCourses, prerequisites):
    # Build graph
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # Use Kahn's algorithm
    in_degree = [0] * numCourses
    for prereqs in graph:
        for course in prereqs:
            in_degree[course] += 1

    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:
            queue.append(i)

    completed = 0
    while queue:
        course = queue.popleft()
        completed += 1
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)

    return completed == numCourses

If there’s a cycle, you can’t finish! (Course A needs B, B needs A = impossible!)

👽 Alien Dictionary: Decoding Unknown Languages

The Problem

Aliens gave us words in sorted order. Figure out their alphabet!

Given words: [“wrt”, “wrf”, “er”, “ett”, “rftt”]

Deduce:

• “wrt” before “wrf” → ‘t’ comes before ‘f’
• “wrf” before “er” → ‘w’ comes before ‘e’
• “er” before “ett” → ‘r’ comes before ‘t’
• “ett” before “rftt” → ‘e’ comes before ‘r’

graph LR
    W((w)) --> E((e))
    E --> R((r))
    R --> T((t))
    T --> F((f))

Alien alphabet: w → e → r → t → f

Solution: Build Graph + Topological Sort

def alien_order(words):
    # Build graph from comparisons
    graph = {c: set() for word in words for c in word}
    in_degree = {c: 0 for c in graph}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))

        # Check for invalid case
        if len(w1) > len(w2) and w1[:min_len] == w2:
            return ""  # Invalid!

        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    # Topological sort with Kahn's
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    result = []

    while queue:
        c = queue.popleft()
        result.append(c)
        for neighbor in graph[c]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) == len(graph):
        return "".join(result)
    return ""  # Cycle = no valid order

🎓 Summary: Your Detective Toolkit

🌟 Key Takeaways

1. Cycles = Walking in circles. Detect with colors!
2. SCCs = Friend groups where everyone knows everyone
3. Bipartite = Can split into two non-mixing teams?
4. Coloring = Make neighbors different. Greedy works!
5. Topo Sort = Order tasks by dependencies
6. Kahn’s = Count incoming, process zeros first
7. Course Schedule = Topo sort the prerequisites
8. Alien Dictionary = Compare adjacent words, topo sort letters

Now go forth, young detective, and analyze any graph that comes your way! 🕵️✨