Graph Basics

Graph Basics: Your Map to Connected Worlds 🗺️

Imagine you have a bunch of friends. Some friends know each other, some don’t. Now imagine drawing circles for each friend and drawing lines between friends who know each other. That’s a graph!

A graph is like a map that shows connections between things. Just like how roads connect cities, graphs show how things are linked together.

📍 Graph Representation Methods

The Big Question: How Do We Store a Graph?

Think of it like keeping track of your friends list. You have two main ways:

1. Adjacency Matrix (The Grid Approach)

Imagine a big checkerboard. Each row and column is a person. If two people are friends, you put a 1 in their box. Otherwise, 0.

// 4 people: 0, 1, 2, 3
int[][] matrix = {
  {0, 1, 1, 0},  // Person 0
  {1, 0, 1, 0},  // Person 1
  {1, 1, 0, 1},  // Person 2
  {0, 0, 1, 0}   // Person 3
};
// matrix[0][1] = 1 means 0 and 1 are connected

Good for: Checking if two things are connected (super fast!) Bad for: Wastes space when you have few connections

2. Adjacency List (The Neighbor List)

Each person has their own list of friends.

// Using ArrayList
List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(1, 2));    // 0's friends
graph.add(Arrays.asList(0, 2));    // 1's friends
graph.add(Arrays.asList(0, 1, 3)); // 2's friends
graph.add(Arrays.asList(2));       // 3's friends

Good for: Saves space, easy to list all neighbors Bad for: Slower to check if two specific things connect

graph TD
    A["Graph Storage"] --> B["Adjacency Matrix"]
    A --> C["Adjacency List"]
    B --> D["2D Array Grid"]
    C --> E["List of Lists"]

🎨 Graph Types and Properties

Directed vs Undirected

Undirected Graph: Like a two-way street. If Alice knows Bob, Bob knows Alice.

Directed Graph: Like a one-way street. Alice follows Bob on Twitter, but Bob might not follow Alice back.

// Directed: Add edge from A to B only
void addDirectedEdge(int from, int to) {
    graph.get(from).add(to);
}

// Undirected: Add both ways
void addUndirectedEdge(int a, int b) {
    graph.get(a).add(b);
    graph.get(b).add(a);
}

Weighted vs Unweighted

Unweighted: All roads are equal. Just “connected” or “not connected.”

Weighted: Roads have distances. “It’s 5 miles to the store, 10 miles to school.”

Cyclic vs Acyclic

Cyclic: You can walk in circles. Start at A, visit some places, end up back at A.

Acyclic: No circles allowed. Trees are acyclic!

graph TD
    A["Graph Types"] --> B["By Direction"]
    A --> C["By Weight"]
    A --> D["By Cycles"]
    B --> E["Directed"]
    B --> F["Undirected"]
    C --> G["Weighted"]
    C --> H["Unweighted"]
    D --> I["Cyclic"]
    D --> J["Acyclic"]

🌊 Breadth-First Search (BFS)

The Story: Finding Your Friend at a Party

You’re at a party looking for Sam. What do you do?

1. First, ask everyone right next to you
2. Then ask everyone one step away
3. Then everyone two steps away
4. Keep going outward like ripples in water!

This is BFS: explore layer by layer, closest first.

void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

Key Tools:

• Queue: First In, First Out (like a line at the movies)
• Visited array: Remember who you’ve already asked

BFS is perfect for: Finding the shortest path in unweighted graphs!

graph TD
    A["Start: 0"] --> B["Level 1: 1, 2"]
    B --> C["Level 2: 3, 4"]
    C --> D["Level 3: 5"]

🏃 Depth-First Search (DFS)

The Story: Exploring a Maze

You’re in a maze. Instead of checking all paths at once, you:

1. Pick ONE path and go as deep as possible
2. Hit a dead end? Backtrack and try another path
3. Keep going until you’ve explored everything!

This is DFS: go deep first, then backtrack.

void dfs(int node, boolean[] visited,
         List<List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

// Start DFS
void startDFS(List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    dfs(0, visited, graph);
}

Key Tools:

• Recursion (or a Stack): Last In, First Out
• Visited array: Don’t go in circles!

DFS is perfect for: Finding cycles, topological sort, exploring all paths!

graph TD
    A["0"] -->|Go Deep| B["1"]
    B -->|Go Deeper| C["3"]
    C -->|Dead End| D["Backtrack"]
    D --> E["Try 2"]

🏝️ Connected Components

The Story: Islands in an Ocean

Imagine you have islands. People on the same island can walk to each other. People on different islands cannot.

Connected Components = separate islands in your graph.

int countComponents(int n,
                    List<List<Integer>> graph) {
    boolean[] visited = new boolean[n];
    int islands = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            islands++;  // Found a new island!
            dfs(i, visited, graph);
        }
    }
    return islands;
}

How it works:

1. Start at node 0, explore the whole island with DFS
2. Find an unvisited node? That’s a NEW island!
3. Count how many times you start fresh

graph TD
    subgraph Island1
    A["0"] --- B["1"]
    B --- C["2"]
    end
    subgraph Island2
    D["3"] --- E["4"]
    end
    subgraph Island3
    F["5"]
    end

🐑 Clone Graph

The Story: Making a Copy of a Family Tree

You have a family tree and want to make an exact copy. But here’s the catch: each person in the copy should point to copied relatives, not the originals!

class Node {
    int val;
    List<Node> neighbors;

    Node(int val) {
        this.val = val;
        neighbors = new ArrayList<>();
    }
}

// Clone using BFS
Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> clones = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    clones.put(node, new Node(node.val));
    queue.add(node);

    while (!queue.isEmpty()) {
        Node curr = queue.poll();

        for (Node neighbor : curr.neighbors) {
            if (!clones.containsKey(neighbor)) {
                clones.put(neighbor,
                    new Node(neighbor.val));
                queue.add(neighbor);
            }
            clones.get(curr).neighbors
                .add(clones.get(neighbor));
        }
    }
    return clones.get(node);
}

The Secret: Use a HashMap to remember:

• “I’ve already copied this original person”
• “Here’s their clone”

📋 Deep Copy Patterns

The Story: Copying a Lego Structure

When you copy something with connections:

Shallow Copy: You copy the box, but the Lego pieces inside are the SAME pieces (not duplicated).

Deep Copy: You copy the box AND every Lego piece inside gets duplicated too.

The Deep Copy Recipe

1. Track originals to copies (use a HashMap)
2. Create new nodes first
3. Copy relationships using the map

// General Deep Copy Pattern
Map<OriginalType, CopyType> map = new HashMap<>();

// Step 1: Create all copies
for (OriginalType orig : allNodes) {
    map.put(orig, new CopyType(orig.value));
}

// Step 2: Copy relationships
for (OriginalType orig : allNodes) {
    CopyType copy = map.get(orig);
    for (OriginalType neighbor : orig.neighbors) {
        copy.neighbors.add(map.get(neighbor));
    }
}

Why This Works

The HashMap is your translation dictionary:

• Original Alice → Clone Alice
• Original Bob → Clone Bob

When Clone Alice needs to point to her neighbor Bob, you look up: “What’s the clone of original Bob?” and use THAT.

graph TD
    subgraph Original
    A1["Alice"] --> B1["Bob"]
    B1 --> C1["Carol"]
    end
    subgraph Clone
    A2["Alice Copy"] --> B2["Bob Copy"]
    B2 --> C2["Carol Copy"]
    end
    A1 -.->|HashMap| A2
    B1 -.->|HashMap| B2
    C1 -.->|HashMap| C2

🎯 Quick Summary

🌟 You Did It!

Graphs are everywhere:

• 🗺️ Maps and GPS
• 👥 Social networks
• 🌐 The internet itself!

Now you understand how to store them, explore them, count their pieces, and copy them perfectly. That’s the foundation of solving countless real-world problems!

Next up: Using these basics to solve amazing puzzles like finding shortest paths, detecting cycles, and more!