Graph Analysis

🔍 Graph Analysis: Finding Hidden Patterns in Connected Worlds

Imagine you’re a detective investigating a city. You want to find loops in streets, groups of friends who all know each other, and the right order to complete tasks. That’s exactly what Graph Analysis does!

🌟 The Big Picture

Think of graphs like a map of friendships. Each person is a node (a dot), and when two people know each other, we draw a line (edge) between them. Graph Analysis helps us answer cool questions about these connections!

Our Everyday Analogy: Think of graphs like a city map with one-way streets and neighborhoods. We’ll use this idea throughout!

🔄 Cycle Detection in Graphs

What is a Cycle?

A cycle is like walking around your neighborhood and ending up exactly where you started!

Simple Example:

• You leave your house → Go to the park → Visit the bakery → Return home
• That’s a cycle! You went in a circle back to the start.

Why Do We Care?

Cycles can be good or bad:

• ✅ Good: A delivery truck route that ends at the warehouse
• ❌ Bad: Tasks that depend on each other forever (deadlock!)

How to Detect Cycles

In Undirected Graphs (two-way streets): Use DFS (Depth-First Search). If you visit a node you’ve seen before (and it’s not your parent), you found a cycle!

boolean hasCycle(int node,
                 int parent,
                 boolean[] visited,
                 List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            if (hasCycle(neighbor, node,
                        visited, graph))
                return true;
        } else if (neighbor != parent) {
            return true; // Cycle found!
        }
    }
    return false;
}

In Directed Graphs (one-way streets): Track nodes in your current path. If you meet one again, cycle found!

boolean hasCycleDirected(int node,
                         boolean[] visited,
                         boolean[] inPath,
                         List<List<Integer>> graph) {
    visited[node] = true;
    inPath[node] = true;

    for (int neighbor : graph.get(node)) {
        if (inPath[neighbor])
            return true; // Cycle!
        if (!visited[neighbor]) {
            if (hasCycleDirected(neighbor,
                    visited, inPath, graph))
                return true;
        }
    }
    inPath[node] = false;
    return false;
}

🏘️ Strongly Connected Components (SCCs)

What Are SCCs?

Imagine a city where some neighborhoods are so well connected that you can walk from ANY house to ANY other house in that neighborhood (using one-way streets). Each such neighborhood is an SCC!

Simple Example:

• In your school, the library, cafeteria, and gym might all have hallways connecting them in circles
• You can get from any of these to any other
• That’s one Strongly Connected Component!

Kosaraju’s Algorithm (The Two-Pass Method)

Think of it like this:

1. First Pass: Walk around and note the order you finish visiting each house
2. Reverse all streets: Make every one-way street go the opposite direction
3. Second Pass: Visit houses in reverse finish order

// Step 1: Fill the stack with
// finish order
void fillOrder(int node,
               boolean[] visited,
               Stack<Integer> stack,
               List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor])
            fillOrder(neighbor, visited,
                     stack, graph);
    }
    stack.push(node);
}

// Step 2: DFS on reversed graph
void dfs(int node, boolean[] visited,
         List<Integer> component,
         List<List<Integer>> reversed) {
    visited[node] = true;
    component.add(node);
    for (int neighbor : reversed.get(node)) {
        if (!visited[neighbor])
            dfs(neighbor, visited,
               component, reversed);
    }
}

graph TD
    subgraph SCC1[" Neighborhood 1"]
        A((A)) --> B((B))
        B --> C((C))
        C --> A
    end
    subgraph SCC2["Neighborhood 2"]
        D((D)) --> E((E))
        E --> D
    end
    C --> D

🎨 Bipartite Graph Check

What is a Bipartite Graph?

Imagine dividing all students into two teams for a game. A graph is bipartite if you can color every node with just TWO colors, and no two neighbors have the same color!

Simple Example:

• Boys vs Girls in a dance: Each dance pair is a boy-girl pair
• Students vs Teachers: Only students connect to teachers
• If you can split a graph this way, it’s bipartite!

How to Check

Use BFS or DFS with two colors (like Red and Blue):

boolean isBipartite(int n,
        List<List<Integer>> graph) {
    int[] color = new int[n];
    Arrays.fill(color, -1);

    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            Queue<Integer> queue =
                new LinkedList<>();
            queue.offer(i);
            color[i] = 0; // Red

            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int neighbor :
                     graph.get(node)) {
                    if (color[neighbor] == -1) {
                        color[neighbor] =
                            1 - color[node];
                        queue.offer(neighbor);
                    } else if (color[neighbor]
                               == color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

Key Insight: A graph is bipartite if and only if it has NO odd-length cycles!

🌈 Graph Coloring

What is Graph Coloring?

Like coloring a map where no two neighboring countries share the same color! The goal is to use as few colors as possible.

Simple Example:

• Scheduling exam times: No two exams that share students can be at the same time
• Assigning radio frequencies: Nearby towers need different frequencies
• Each “color” represents a different time slot or frequency

Greedy Coloring Algorithm

Start simple: Give each node the smallest color that none of its neighbors have!

int[] greedyColoring(int n,
        List<List<Integer>> graph) {
    int[] result = new int[n];
    Arrays.fill(result, -1);
    result[0] = 0; // First node = color 0

    boolean[] available = new boolean[n];

    for (int node = 1; node < n; node++) {
        Arrays.fill(available, true);

        // Mark neighbor colors unavailable
        for (int neighbor :
             graph.get(node)) {
            if (result[neighbor] != -1)
                available[result[neighbor]]
                    = false;
        }

        // Find first available color
        for (int c = 0; c < n; c++) {
            if (available[c]) {
                result[node] = c;
                break;
            }
        }
    }
    return result;
}

Fun Fact: The famous Four Color Theorem says any map needs at most 4 colors!

📋 Topological Sort

What is Topological Sort?

Imagine you’re getting dressed. You MUST put on underwear before pants, socks before shoes. Topological sort gives you a valid order to do things when some things must come before others!

Simple Example:

• Making a sandwich: Get bread → Add filling → Close sandwich
• You can’t close the sandwich before adding filling!

When Does It Work?

Only for DAGs (Directed Acyclic Graphs) - graphs with no cycles!

graph TD
    A["Wake Up"] --> B["Brush Teeth"]
    A --> C["Shower"]
    B --> D["Get Dressed"]
    C --> D
    D --> E["Eat Breakfast"]
    E --> F["Leave House"]

DFS-Based Topological Sort

void topologicalSort(int n,
        List<List<Integer>> graph) {
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        if (!visited[i])
            topoHelper(i, visited,
                      stack, graph);
    }

    // Print order (reversed stack)
    while (!stack.isEmpty())
        System.out.print(stack.pop() + " ");
}

void topoHelper(int node, boolean[] visited,
        Stack<Integer> stack,
        List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node))
        if (!visited[neighbor])
            topoHelper(neighbor, visited,
                      stack, graph);
    stack.push(node); // Add after children
}

🎯 Kahn’s Algorithm

A Different Way to Topological Sort

Instead of DFS, Kahn’s Algorithm uses in-degrees (how many arrows point TO a node).

The Idea:

1. Find all nodes with no incoming edges (in-degree = 0)
2. Remove them and add to result
3. Update in-degrees of remaining nodes
4. Repeat until done!

Simple Example:

• If a task has no prerequisites, do it first!
• Once done, other tasks might now have no prerequisites

List<Integer> kahnsAlgorithm(int n,
        List<List<Integer>> graph) {
    int[] inDegree = new int[n];

    // Calculate in-degrees
    for (int i = 0; i < n; i++)
        for (int neighbor : graph.get(i))
            inDegree[neighbor]++;

    Queue<Integer> queue =
        new LinkedList<>();

    // Start with 0 in-degree nodes
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0)
            queue.offer(i);

    List<Integer> result =
        new ArrayList<>();

    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);

        for (int neighbor :
             graph.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }

    // If result size != n, cycle exists!
    return result.size() == n ?
           result : new ArrayList<>();
}

Bonus: Kahn’s Algorithm can also detect cycles! If the result doesn’t contain all nodes, there’s a cycle.

📚 Course Schedule Problems

The Classic Problem

You want to take some courses, but some courses have prerequisites. Can you finish all courses?

Simple Example:

• To take “Web Development”, you need “HTML Basics” first
• To take “HTML Basics”, you need nothing
• Order: HTML Basics → Web Development ✅

Course Schedule I: Can We Finish?

This is just cycle detection in a directed graph!

boolean canFinish(int numCourses,
        int[][] prerequisites) {
    List<List<Integer>> graph =
        new ArrayList<>();
    for (int i = 0; i < numCourses; i++)
        graph.add(new ArrayList<>());

    for (int[] prereq : prerequisites)
        graph.get(prereq[1])
             .add(prereq[0]);

    // Use Kahn's - if we can't process
    // all nodes, there's a cycle
    int[] inDegree = new int[numCourses];
    for (int[] prereq : prerequisites)
        inDegree[prereq[0]]++;

    Queue<Integer> queue =
        new LinkedList<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0)
            queue.offer(i);

    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0)
                queue.offer(next);
        }
    }

    return count == numCourses;
}

Course Schedule II: Give Me the Order!

Same algorithm, but return the actual order!

🔤 Alien Dictionary

The Problem

Aliens have a dictionary with words in their alphabet. Given sorted words, figure out the order of their letters!

Simple Example:

Words: ["wrt", "wrf", "er", "ett", "rftt"]

By comparing adjacent words:

• “wrt” vs “wrf”: t comes before f
• “wrf” vs “er”: w comes before e
• “er” vs “ett”: r comes before t
• “ett” vs “rftt”: e comes before r

The Solution: Build a Graph!

Each letter is a node. If letter A comes before letter B, draw an edge A → B. Then topologically sort!

String alienOrder(String[] words) {
    // Build graph
    Map<Character, Set<Character>> graph =
        new HashMap<>();
    Map<Character, Integer> inDegree =
        new HashMap<>();

    // Initialize all characters
    for (String word : words) {
        for (char c : word.toCharArray()) {
            graph.putIfAbsent(c,
                new HashSet<>());
            inDegree.putIfAbsent(c, 0);
        }
    }

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

        // Check invalid case:
        // "abc" before "ab"
        if (w1.length() > w2.length() &&
            w1.startsWith(w2))
            return "";

        // Find first different character
        for (int j = 0; j <
             Math.min(w1.length(),
                      w2.length()); j++) {
            char c1 = w1.charAt(j);
            char c2 = w2.charAt(j);
            if (c1 != c2) {
                if (!graph.get(c1)
                          .contains(c2)) {
                    graph.get(c1).add(c2);
                    inDegree.put(c2,
                        inDegree.get(c2) + 1);
                }
                break;
            }
        }
    }

    // Kahn's Algorithm
    Queue<Character> queue =
        new LinkedList<>();
    for (char c : inDegree.keySet())
        if (inDegree.get(c) == 0)
            queue.offer(c);

    StringBuilder result =
        new StringBuilder();
    while (!queue.isEmpty()) {
        char c = queue.poll();
        result.append(c);
        for (char next : graph.get(c)) {
            inDegree.put(next,
                inDegree.get(next) - 1);
            if (inDegree.get(next) == 0)
                queue.offer(next);
        }
    }

    return result.length() ==
           inDegree.size() ?
           result.toString() : "";
}

🎯 Summary: Your Graph Analysis Toolkit

🚀 You’ve Got This!

Graph Analysis is like being a detective:

• Cycles = Finding loops in your investigation
• SCCs = Identifying tight-knit groups
• Bipartite = Splitting into teams
• Coloring = Assigning without conflicts
• Topological Sort = Finding the right order
• Kahn’s = Starting with the easiest first

Now go analyze some graphs! 🎉