🗺️ Graph Algorithms

The City Map Analogy

Think of a city map:

• Nodes (Vertices): Cities, intersections, or locations
• Edges: Roads connecting them
• Weights: Distance, time, or cost to travel

Graph algorithms help you answer questions like:

• What's the shortest route from A to B?
• Are all cities connected?
• What order should I visit places?

How Graphs Are Stored

Adjacency List (Most Common)

Each node stores its list of neighbors:

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

Adjacency List:
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

Memory: O(V + E) - efficient for sparse graphs

Adjacency Matrix

A 2D grid where matrix[i][j] = 1 if edge exists:

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

Memory: O(V²) - efficient for dense graphs
Lookup: O(1) to check if edge exists

When to Use Which

Core Graph Algorithms

1. Traversal: BFS and DFS

BFS (Breadth-First Search): Level by level, finds shortest path in unweighted graphs.

DFS (Depth-First Search): Go deep first, good for path finding and cycle detection.

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

BFS from A: A → B → C → D → E (level order)
DFS from A: A → B → E → D → C (deep first)

2. Shortest Path

Unweighted graphs: Use BFS - first time you reach a node is the shortest path.

Weighted graphs (no negative): Use Dijkstra's algorithm.

Weighted with negatives: Use Bellman-Ford.

All pairs: Use Floyd-Warshall.

Find A to E:

Unweighted: BFS gives path length 2 (A→B→E)

Weighted:
    A --5-- B --1-- E
    |
    +--10-- C --2-- E

Dijkstra finds: A→B→E (cost 6) beats A→C→E (cost 12)

3. Cycle Detection

Undirected graph: DFS, check if you visit an already-visited node (not the parent).

Directed graph: DFS with recursion stack. If you reach a node in current path, cycle found!

A → B → C → A  ← Cycle detected!

4. Connected Components

Groups of nodes that can reach each other:

  A---B     E---F     Separate
  |   |               components!
  C---D     G

Component 1: {A, B, C, D}
Component 2: {E, F}
Component 3: {G}

Run DFS/BFS from each unvisited node to find all components.

5. Topological Sort

Linear ordering of vertices such that for every edge A→B, A comes before B.

Only works on DAGs (Directed Acyclic Graphs).

Course prerequisites:
  Math → Physics → Engineering
  English → Writing

Topological order: Math, English, Physics, Writing, Engineering
(Any valid order where prerequisites come first)

Use DFS postorder, then reverse!

Common Graph Problems

Problem 1: Number of Islands

Grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Count connected groups of ones = 3 islands

Approach: DFS/BFS from each unvisited land cell, mark all connected land as visited.

Problem 2: Clone Graph

Create a deep copy of a graph.

Approach: BFS/DFS with a map from original → clone.

Problem 3: Course Schedule

Can you finish all courses given prerequisites?

Approach: Detect cycle in directed graph. No cycle = can finish.

Problem 4: Word Ladder

Transform "hit" → "cog" changing one letter at a time.

Approach: BFS where neighbors are words differing by one letter.

Problem 5: Bipartite Check

Can you color nodes with 2 colors so no neighbors share a color?

Approach: BFS with alternating colors. Conflict = not bipartite.

Graph Algorithm Patterns

Pattern 1: Multi-Source BFS

Start BFS from multiple nodes simultaneously:

Problem: Distance to nearest 0 in matrix

Instead of BFS from each cell:
  Start BFS from ALL zeros at once!
  Expand outward, marking distances.

Pattern 2: Union-Find (Disjoint Set)

Efficient for dynamic connectivity:

Are A and B connected?
Connect C and D.
Are they in the same group?

Operations: O(α(n)) ≈ O(1) with path compression

Pattern 3: Graph as Implicit Structure

Sometimes the graph isn't explicit:

Word Ladder: Words are nodes, edges connect words differing by 1 letter
Matrix: Cells are nodes, edges connect adjacent cells
State Space: States are nodes, moves are edges

Time Complexities

Common Mistakes

1. Forgetting Visited Set

You'll revisit nodes infinitely in cyclic graphs!

2. Wrong Algorithm for Weighted Graphs

BFS only works for unweighted shortest path. Use Dijkstra for weighted.

3. Topological Sort on Cyclic Graph

This won't work on a cyclic graph. Check that it's a DAG first.

4. Confusing Directed vs Undirected

Edge A→B in directed only goes one way. In undirected, it goes both ways.

FAQ

Q: When to use BFS vs Dijkstra?

BFS: Unweighted graphs (all edges same weight). Dijkstra: Weighted graphs (edges have different costs).

Q: How do I detect if a graph is connected?

Run DFS/BFS from any node. If you visit all nodes, it's connected.

Q: What's the difference between directed and undirected?

Directed: Edges have direction (A→B ≠ B→A). Undirected: Edges go both ways (A—B).

Q: When should I use Union-Find vs BFS?

Union-Find: Many connectivity queries or dynamic edges. BFS: Single traversal or shortest path.

Summary

Graph algorithms solve problems on networks of connected nodes.

Key Takeaways:

• Adjacency list for sparse, matrix for dense graphs
• BFS: shortest path (unweighted), level order
• DFS: cycle detection, topological sort, path finding
• Dijkstra: shortest path with weights
• Topological sort: ordering with prerequisites (DAG only)
• Many problems reduce to graph traversal

Graphs are everywhere - master these patterns!