Graph Algorithms

🗺️ Graph Algorithms: Finding Your Way Through Connected Worlds

Imagine you’re a delivery driver in a big city. Every house is connected by roads. How do you find the best route? That’s exactly what graph algorithms help computers do!

🎯 The Big Picture

A graph is like a map of connections. Think of:

• Nodes (vertices) = Places (houses, cities, people)
• Edges = Roads or connections between places

Graph algorithms help us explore and find the best paths through these connections.

1️⃣ BFS Algorithm (Breadth-First Search)

🌊 The Water Ripple Analogy

Imagine dropping a stone in a pond. The ripples spread outward in circles, touching nearby points first, then farther ones.

BFS explores like ripples:

• First, visit all neighbors (1 step away)
• Then, visit neighbors-of-neighbors (2 steps away)
• Keep going layer by layer

🎯 When to Use BFS

• Finding the shortest path (fewest steps)
• Exploring all reachable nodes
• Level-by-level exploration

📝 How It Works

1. Start at a node
2. Visit ALL its neighbors
3. Then visit all THEIR neighbors
4. Repeat until done

🎮 Simple Example

Graph:     A --- B --- D
           |     |
           C --- E

Start at A:
Layer 1: Visit B, C (neighbors of A)
Layer 2: Visit D, E (neighbors of B, C)

Order: A → B → C → D → E

💡 Real Life Example

Finding friends on social media:

• You = A
• Your friends = 1 step away
• Friends of friends = 2 steps away
• BFS finds “degrees of separation”

2️⃣ DFS Algorithm (Depth-First Search)

🐭 The Maze Explorer Analogy

Imagine a mouse in a maze. It picks ONE path and goes as deep as possible. If stuck, it backtracks and tries another path.

DFS explores like a maze mouse:

• Go deep down one path
• Hit a dead end? Go back
• Try another unexplored path

🎯 When to Use DFS

• Exploring all possible paths
• Detecting cycles (loops)
• Solving puzzles and mazes

📝 How It Works

1. Start at a node
2. Pick ONE neighbor, go there
3. Keep going deeper
4. Dead end? Backtrack
5. Try unexplored paths

🎮 Simple Example

Graph:     A --- B --- D
           |     |
           C --- E

Start at A, go deep:
A → B → D (dead end, backtrack)
   → B → E (dead end, backtrack)
   → B (backtrack to A)
A → C → E (already visited)

Order: A → B → D → E → C

🔄 BFS vs DFS: The Key Difference

3️⃣ Shortest Path Problem

🛤️ The GPS Analogy

When you ask Google Maps for directions, you want the quickest or shortest route. That’s the shortest path problem!

🎯 Two Types of “Shortest”

1. Fewest Stops (Unweighted)

• Every road has the same “cost”
• BFS solves this!
• Example: Fewest subway transfers

2. Lowest Cost (Weighted)

• Roads have different costs (distance, time, money)
• Need special algorithms (Dijkstra!)
• Example: Fastest driving route

📊 Weighted Graph Example

       5 km
    A ───── B
    │       │
2km │       │ 3km
    │       │
    C ───── D
       4 km

Shortest A to D:
- A → B → D = 5 + 3 = 8 km
- A → C → D = 2 + 4 = 6 km ✅ Winner!

4️⃣ Dijkstra’s Algorithm

🎒 The Greedy Traveler Analogy

Imagine a traveler who always picks the cheapest next step. They keep track of the best price to reach each city and update it as they find better deals.

🎯 Key Idea

• Start with infinite cost to all nodes
• Keep picking the closest unvisited node
• Update costs to neighbors if you find a cheaper path

📝 Step-by-Step Process

1. Set distance to start = 0
2. Set distance to all others = ∞
3. Pick unvisited node with
   smallest distance
4. Update neighbors' distances
5. Mark node as visited
6. Repeat until done

🎮 Example Walkthrough

       2
    A ─── B
    │╲    │
  1 │  ╲4 │ 3
    │   ╲ │
    C ─── D
       5

Start: A, Goal: Find shortest to all

Step 1: A=0, B=∞, C=∞, D=∞
        Visit A
        Update: B=2, C=1, D=4

Step 2: C=1 (smallest unvisited)
        Visit C
        Update: D=min(4, 1+5)=4

Step 3: B=2 (smallest unvisited)
        Visit B
        Update: D=min(4, 2+3)=4

Step 4: D=4 (smallest unvisited)
        Visit D

Final: A=0, B=2, C=1, D=4

⚠️ Limitation

Dijkstra cannot handle negative edge weights! (Use Bellman-Ford for that)

5️⃣ MST Problem (Minimum Spanning Tree)

🌳 The City Power Grid Analogy

Imagine building power lines to connect all houses in a village. You want to:

• Connect every house
• Use the least total wire

That’s an MST!

🎯 Key Rules

• Must connect ALL nodes
• Use fewest edges possible (N-1 for N nodes)
• Minimize total edge weight
• NO cycles allowed (it’s a tree!)

📊 Example

Original Graph:        MST (Total: 6):
       2                    2
    A ─── B              A ─── B
    │╲    │              │
  1 │  ╲3 │ 4          1 │
    │   ╲ │              │
    C ─── D              C ─── D
       5                    3

Edges chosen: A-C(1), A-B(2), B-D or A-D(3)
Total = 1 + 2 + 3 = 6

🔧 Popular MST Algorithms

Kruskal’s Algorithm:

1. Sort all edges by weight
2. Pick smallest edge
3. Add if it doesn’t create a cycle
4. Repeat until tree is complete

Prim’s Algorithm:

1. Start from any node
2. Add cheapest edge to a new node
3. Repeat until all nodes connected

💡 Real Applications

• Network design (cables, pipes)
• Clustering data points
• Approximating traveling salesman

6️⃣ Topological Sorting

👔 The Getting Dressed Analogy

You can’t put on shoes before socks! Some tasks have dependencies - they must happen in a certain order.

Topological sort gives a valid order for tasks with dependencies.

🎯 Requirements

• Only works on DAGs (Directed Acyclic Graphs)
• DAG = Has direction, NO cycles
• Result: A valid ordering

📊 Example: Morning Routine

Dependencies:
Underwear → Pants → Belt
Socks → Shoes
Shirt → Belt
Shirt → Tie

Valid Order:
Underwear → Socks → Pants →
Shirt → Belt → Tie → Shoes

(Many valid orders exist!)

📝 How It Works (Kahn’s Algorithm)

1. Find nodes with no incoming
   edges (no dependencies)
2. Add them to result
3. Remove their outgoing edges
4. Repeat until all nodes added

🎮 Code Example Flow

Build Order Dependencies:
  main.c → utils.c
  main.c → network.c
  utils.c → config.c

Topological Order:
config.c → utils.c →
network.c → main.c

(Build files in this order!)

💡 Real Applications

• Build systems (Makefile)
• Course prerequisites
• Task scheduling
• Package dependencies

🗺️ Algorithm Cheat Guide

graph TD
    A["Graph Problem"] --> B{Need shortest path?}
    B -->|Yes, unweighted| C["Use BFS"]
    B -->|Yes, weighted| D["Use Dijkstra"]
    B -->|No| E{Need to explore?}
    E -->|All paths/cycles| F["Use DFS"]
    E -->|Connect all nodes cheaply| G["Use MST"]
    E -->|Order with dependencies| H["Topological Sort"]

🎯 Quick Summary

🚀 You’ve Got This!

Graph algorithms might seem complex, but they’re really just smart ways to explore connections. Whether you’re:

• 🗺️ Finding the best route (Dijkstra)
• 🌊 Exploring level by level (BFS)
• 🐭 Going deep into possibilities (DFS)
• 🌳 Building efficient networks (MST)
• 📋 Ordering tasks (Topological Sort)

You now have the tools to solve real-world problems!

Remember: Every GPS, social network, and game pathfinding system uses these exact algorithms. Now you understand how they work! 🎉