Graph Basics

🌐 Graph Basics: Building Your City of Connections

Imagine you’re building a city where every house can connect to any other house with roads. That’s exactly what a graph is—a way to show how things are connected!

🏘️ The Universal Analogy: Your Neighborhood Map

Think of a graph like a neighborhood map:

• Houses = Nodes (or vertices) — the things we care about
• Roads = Edges — the connections between houses
• Some roads go one way (like a one-way street)
• Some roads go both ways (like regular streets)

Every concept we learn today uses this simple idea. Ready to explore your neighborhood?

📍 Graph Representation Methods

How Do We Draw Our Neighborhood Map?

There are two main ways to write down which houses connect to which:

1️⃣ Adjacency List: The Neighbor Notebook

Imagine each house has a little notebook. Inside, it writes down only the houses it’s directly connected to.

# Each house keeps a list of neighbors
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Why it’s great:

• Easy to see who’s connected to whom
• Uses less memory when roads are few
• Most common in real code!

2️⃣ Adjacency Matrix: The Big Grid Chart

Imagine a giant chart with all houses on top AND on the side. Put a ✓ where two houses connect.

#     A  B  C  D
# A [ 0, 1, 1, 0 ]
# B [ 1, 0, 0, 1 ]
# C [ 1, 0, 0, 1 ]
# D [ 0, 1, 1, 0 ]

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

Why it’s great:

• Super fast to check: “Is A connected to D?”
• Good when almost everything connects

graph TD
    A((A)) --- B((B))
    A((A)) --- C((C))
    B((B)) --- D((D))
    C((C)) --- D((D))

🏷️ Graph Types and Properties

Different Kinds of Neighborhoods

1. Directed vs Undirected

# Undirected: Both can visit each other
undirected = {'A': ['B'], 'B': ['A']}

# Directed: A can visit B, but not back
directed = {'A': ['B'], 'B': []}

2. Weighted vs Unweighted

• Unweighted: All roads are equal
• Weighted: Some roads are longer/shorter

# Weighted: Distance matters!
weighted = {
    'A': [('B', 5), ('C', 2)],
    'B': [('D', 3)]
}
# From A to B costs 5 minutes

3. Cyclic vs Acyclic

• Cyclic: You can walk in circles (A → B → C → A)
• Acyclic: No loops possible (like a family tree)

graph TD
    subgraph Cyclic
        X((X)) --> Y((Y))
        Y((Y)) --> Z((Z))
        Z((Z)) --> X((X))
    end

4. Connected vs Disconnected

• Connected: Every house can reach every other house
• Disconnected: Some houses are totally isolated

🔍 Breadth-First Search (BFS)

Exploring Level by Level

Imagine you’re looking for your lost puppy in the neighborhood. BFS means:

1. First, check all your direct neighbors
2. Then, check all THEIR neighbors
3. Keep going outward like ripples in water

The Water Ripple Method:

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        house = queue.popleft()
        order.append(house)

        for neighbor in graph[house]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# Example
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}

print(bfs(graph, 'A'))
# Output: ['A', 'B', 'C', 'D', 'E', 'F']

graph TD
    A((Start A)) --> B((B))
    A((Start A)) --> C((C))
    B((B)) --> D((D))
    B((B)) --> E((E))
    C((C)) --> F((F))

    style A fill:#ff6b6b
    style B fill:#ffd93d
    style C fill:#ffd93d
    style D fill:#6bcb77
    style E fill:#6bcb77
    style F fill:#6bcb77

BFS finds the SHORTEST path (fewest hops) in unweighted graphs!

🕳️ Depth-First Search (DFS)

Exploring One Path Completely

Now imagine you’re exploring a maze. DFS means:

1. Go as deep as you can down one path
2. Hit a dead end? Backtrack and try another path
3. Keep going until you’ve seen everything

The Brave Explorer Method:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    order = [start]

    for neighbor in graph[start]:
        if neighbor not in visited:
            order += dfs(graph, neighbor, visited)

    return order

# Same graph as before
print(dfs(graph, 'A'))
# Output: ['A', 'B', 'D', 'E', 'C', 'F']

Iterative version (using a stack):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        house = stack.pop()
        if house not in visited:
            visited.add(house)
            order.append(house)
            # Add neighbors (reversed for order)
            for neighbor in reversed(graph[house]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

🏘️ Connected Components

Finding Separate Neighborhoods

Sometimes your city has islands—groups of houses that don’t connect to each other at all. Each island is a “connected component.”

How to find them:

def find_components(graph):
    visited = set()
    components = []

    for node in graph:
        if node not in visited:
            # Found a new island!
            component = []
            stack = [node]

            while stack:
                current = stack.pop()
                if current not in visited:
                    visited.add(current)
                    component.append(current)
                    for neighbor in graph[current]:
                        if neighbor not in visited:
                            stack.append(neighbor)

            components.append(component)

    return components

# Graph with 2 separate islands
graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B'],
    'X': ['Y'],
    'Y': ['X']
}

print(find_components(graph))
# Output: [['A', 'B', 'C'], ['X', 'Y']]

graph TD
    subgraph Island1["Island 1"]
        A((A)) --- B((B))
        B((B)) --- C((C))
    end

    subgraph Island2["Island 2"]
        X((X)) --- Y((Y))
    end

Real World Uses:

• Finding friend groups in social networks
• Finding clusters in data
• Checking if a network is fully connected

🖨️ Clone Graph

Making an Exact Copy of Your Map

Imagine you need to give someone a perfect copy of your neighborhood map. But here’s the tricky part—each house points to its neighbors. If you just copy the pointers, you’re not making a new neighborhood, you’re just sharing the old one!

The Problem:

# This is a Node in our graph
class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

The Solution: Use a Dictionary to Track Clones

def clone_graph(node):
    if not node:
        return None

    # Dictionary: original → clone
    clones = {}

    def dfs(original):
        if original in clones:
            return clones[original]

        # Create the clone
        copy = Node(original.val)
        clones[original] = copy

        # Clone all neighbors
        for neighbor in original.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

Step by step:

1. Visit a house
2. Build a copy of that house
3. Remember: “Original A → Copy A”
4. For each neighbor, do the same
5. Connect the copies together

📋 Deep Copy Patterns

The Art of True Duplication

A deep copy means every piece is brand new—no sharing with the original. This is crucial for graphs because of cycles!

Pattern 1: Hash Map + DFS

def deep_copy_graph(node):
    if not node:
        return None

    old_to_new = {}

    def clone(n):
        if n in old_to_new:
            return old_to_new[n]

        copy = Node(n.val)
        old_to_new[n] = copy

        for neighbor in n.neighbors:
            copy.neighbors.append(clone(neighbor))

        return copy

    return clone(node)

Pattern 2: Hash Map + BFS

from collections import deque

def deep_copy_bfs(node):
    if not node:
        return None

    old_to_new = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        current = queue.popleft()

        for neighbor in current.neighbors:
            if neighbor not in old_to_new:
                old_to_new[neighbor] = Node(neighbor.val)
                queue.append(neighbor)

            old_to_new[current].neighbors.append(
                old_to_new[neighbor]
            )

    return old_to_new[node]

Key Insight: The hash map prevents infinite loops! When we see a node we’ve already cloned, we just grab the existing copy instead of making another one.

graph LR
    subgraph Original
        A1((A)) --> B1((B))
        B1((B)) --> A1((A))
    end

    subgraph Clone
        A2((A prime)) --> B2((B prime))
        B2((B prime)) --> A2((A prime))
    end

    A1 -.-> A2
    B1 -.-> B2

🎯 Quick Summary

🚀 You Did It!

You now understand how graphs work—from representing them to searching them to copying them! These concepts power everything from Google Maps to social networks to AI.

Remember: A graph is just a neighborhood. Nodes are houses. Edges are roads. Everything else builds on this simple idea!

Now go explore the interactive playground and put your knowledge to the test! 🎮