Graph Algorithms and BFS/DFS

# CHAPTER 15

Graph Algorithms and BFS/DFS #

1. Chapter Introduction #

2. Representing a Graph in Memory #

adj_list = {
    1: [2, 3],
    2: [4],
    3: [],
    4: []
}

*Always build an Adjacency List as step #1 in a Graph interview.*

3. Graph Traversal: The Cycle Problem #

4. Graph DFS (Depth-First Search) #

*Example: Number of Islands (LeetCode 200)* *Prompt:* Given an M x N 2D grid map of '1's (land) and '0's (water), count the number of islands. *Logic:* Iterate through every cell. If you find a '1', increment the island count. Then, launch a recursive DFS to "sink" (change to '0' or add to visited set) all connected '1's horizontally and vertically.

def dfs(r, c):
    if r < 0 or c < 0 or r >= ROWS or c >= COLS or grid[r][c] == &#039;0':
        return
    grid[r][c] = &#039;0' # Mark as visited (sink the island)
    dfs(r - 1, c) # Up
    dfs(r + 1, c) # Down
    dfs(r, c - 1) # Left
    dfs(r, c + 1) # Right

5. Graph BFS (Breadth-First Search) #

from collections import deque

def shortestPath_BFS(start, target, adj_list):
    queue = deque([(start, 0)]) # Queue stores (Node, Distance)
    visited = set([start])
    
    while queue:
        node, dist = queue.popleft()
        
        if node == target:
            return dist # Found shortest path!
            
        for neighbor in adj_list[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

6. Pattern: Topological Sorting #

1. 1. Calculate the "Indegree" (number of incoming arrows) for every node.

1. 2. Put all nodes with Indegree 0 (courses with no prerequisites) into a Queue.

1. 3. While the Queue is not empty:

• Pop a node (take the course).

• "Remove" its outgoing arrows by reducing the Indegree of its neighbors by 1.

• If a neighbor's Indegree hits 0, add it to the Queue!

1. 4. If you processed all nodes, success. If not, a cycle exists (Course A requires B, and B requires A).

7. Real-World Scenario: Dijkstra's Algorithm #

8. Mini Project: Build an Adjacency List #

adj = {i: [] for i in range(4)}
for n1, n2 in edges:
    adj[n1].append(n2)
    adj[n2].append(n1) # Because it is undirected (two-way street)

9. Common Mistakes #

• Forgetting Directed vs. Undirected: If the prompt says "A is connected to B", you must ask if it's a two-way street. If it is undirected, your Adjacency List must append B to A's list, AND append A to B's list.

• Forgetting the Visited Set: Trying to traverse a graph without a visited set will almost always result in an infinite loop and a crashed interview.

10. Best Practices #

• Time/Space Complexity: Building an Adjacency List takes O(V + E) where V is Vertices (nodes) and E is Edges. Standard BFS/DFS traversal is also O(V + E) Time, because you visit every node once, and iterate through every edge once.

11. Exercises #

1. 1. Why is BFS better than DFS for finding the "Shortest Path" in a maze?

1. 2. Trace Kahn's Algorithm (Indegrees) for Course 1 -> Course 2 -> Course 3.

12. MCQs #

14. Interview Questions #

• Q: "There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, price_i]. Find the cheapest price from src to dst with up to k stops." (LeetCode 787).

15. FAQs #

• Q: Are graph problems considered "Hard"?

16. Summary #

17. Next Chapter Recommendation #