1.1 Graph là gì?

Phân loại

• Directed (có hướng): cạnh có chiều u → v. Ví dụ: dependency graph, social media follows.
• Undirected (vô hướng): cạnh hai chiều u — v. Ví dụ: friendship, road map.
• Weighted (có trọng số): mỗi cạnh có giá trị (cost, distance).
• DAG (Directed Acyclic Graph): có hướng + không có chu kỳ. Cho phép Topological Sort.

Ba loại bài graph trên LeetCode

1. Grid as graph (~50%): mỗi ô là node, neighbors = 4 hướng. Number of Islands, Rotting Oranges.
2. Explicit graph (~30%): edges cho dưới dạng list. Course Schedule, Number of Provinces.
3. Implicit graph (~20%): nodes là string/number, edges xác định bởi quan hệ. Word Ladder.

1.2 Biểu diễn — Adjacency List vs Matrix

Adjacency List trong Python

from collections import defaultdict

# Từ list edges
edges = [[0,1], [0,2], [1,2], [2,3]]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)               # cho undirected; bỏ dòng này nếu directed

Đa số bài LeetCode có graph sparse → ưu tiên adjacency list.

1.3 Visited set — Tránh chu kỳ

Graph có thể có chu kỳ (khác cây). Không kiểm soát visited → vô tận.

Template BFS

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        process(node)
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                q.append(nei)

Template DFS (recursive)

def dfs(graph, node, visited):
    if node in visited: return
    visited.add(node)
    process(node)
    for nei in graph[node]:
        dfs(graph, nei, visited)

1.4 BFS vs DFS — Khi nào dùng cái nào?

Quy tắc nhanh

• "Shortest path" trong graph unweighted → BFS.
• "Connected components", "đếm đảo" → cả hai đều OK; DFS code ngắn hơn.
• "Topological sort" → DFS post-order hoặc Kahn's BFS.
• "Có chu kỳ không?" với directed → DFS với 3-color marking.
• "Shortest path weighted" → Dijkstra (BFS + min-heap).

2.1 Grid as Implicit Graph

Trong các bài lưới, không cần build adjacency list. Mỗi ô (r, c) là node, neighbors là 4 ô kế (hoặc 8 ô với chéo).

# Template duyệt 4 hướng
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]    # up, down, left, right

def neighbors(r, c, m, n):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n:
            yield nr, nc

Visited không cần thiết khi có thể "in-place mark"

# Thay vì set visited, mark trực tiếp lên grid:
grid[r][c] = '0'      # cho Number of Islands — mark land thành water

2.2 Worked Example 1 — Number of Islands (DFS)

Đề (LeetCode #200): Lưới 2D với '1' = land, '0' = water. Đếm số đảo (cụm '1' liên thông qua 4 hướng).

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return
        grid[r][c] = '0'                    # in-place mark visited
        dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

Time O(m × n), Space O(m × n) worst case (recursion depth).

2.3 Number of Islands — BFS Variant

from collections import deque

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                q = deque([(r, c)])
                grid[r][c] = '0'                  # mark KHI push (quan trọng!)
                while q:
                    r0, c0 = q.popleft()
                    for dr, dc in DIRS:
                        nr, nc = r0 + dr, c0 + dc
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'    # mark NGAY
                            q.append((nr, nc))
    return count

Time và space giống DFS. Dùng BFS khi cần tránh stack overflow trên grid lớn.

2.4 Worked Example 2 — Max Area of Island

Đề (LeetCode #695): Tương tự #200 nhưng trả về diện tích đảo lớn nhất.

def maxAreaOfIsland(grid):
    m, n = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        return 1 + dfs(r-1, c) + dfs(r+1, c) + dfs(r, c-1) + dfs(r, c+1)
    best = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                best = max(best, dfs(r, c))
    return best

Time O(m × n).

Khác với Number of Islands

DFS giờ trả về kích thước cây con (= số ô của đảo). Pattern này tận dụng đệ quy bottom-up từ Tuần 8 (đệ quy trả về thông tin tổng hợp).

2.5 Worked Example 3 — Rotting Oranges (Multi-source BFS)

Đề (LeetCode #994): Lưới có 0 (rỗng), 1 (cam tươi), 2 (cam thối). Mỗi phút, cam thối lây sang cam tươi 4 hướng. Trả về số phút để mọi cam thối, -1 nếu không thể.

Pattern: Multi-source BFS

Khởi tạo queue với tất cả cam thối ban đầu. BFS từ chúng đồng thời — mỗi level = 1 phút.

def orangesRotting(grid):
    m, n = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 2: q.append((r, c, 0))
            elif grid[r][c] == 1: fresh += 1
    minutes = 0
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        r, c, t = q.popleft()
        minutes = max(minutes, t)
        for dr, dc in DIRS:
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

2.6 Worked Example 4 — Walls and Gates

Đề (LeetCode #286): Lưới với -1 (tường), 0 (cổng), INF (phòng trống). Điền mỗi phòng trống bằng khoảng cách đến cổng gần nhất.

Multi-source BFS từ MỌI cổng cùng lúc

INF = 2147483647
def wallsAndGates(rooms):
    if not rooms: return
    m, n = len(rooms), len(rooms[0])
    q = deque()
    for r in range(m):
        for c in range(n):
            if rooms[r][c] == 0:
                q.append((r, c))
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r+dr, c+dc
            if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

Time O(m × n).

Knowledge Check — Grid & Multi-source BFS

3.1 BFS — Tại sao cho shortest path?

Lập luận

Quy nạp theo level. Level 0 = source. Level k+1 = neighbors mới của level k chưa visit. Mọi node trong level k cách source đúng k bước. Khi target được mark visited lần đầu, level đó = shortest distance.

Điều kiện áp dụng

• Unweighted: mọi cạnh "tốn" 1 bước.
• Hoặc weighted với weight = 0 hoặc 1: dùng 0-1 BFS với deque.

Khi weight tổng quát → dùng Dijkstra (xem 6.1).

3.2 Worked Example 5 — Word Ladder (Hard)

Đề (LeetCode #127, Hard): Cho beginWord, endWord, wordList. Mỗi bước thay 1 ký tự để tạo từ mới (phải có trong wordList). Trả về độ dài chuỗi ngắn nhất từ begin đến end (bao gồm cả hai), 0 nếu không thể.

Ví dụ: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] → 5 (hit→hot→dot→dog→cog).

Implicit graph

Node = từ. Edge = hai từ khác nhau đúng 1 ký tự. Build adjacency list trực tiếp tốn O(N² × L) — quá đắt. Thay vào đó:

# Generic patterns: thay mỗi vị trí bằng '*'
# "hot" → ["*ot", "h*t", "ho*"]
# Hai từ là neighbors ⟺ chia sẻ ít nhất 1 generic pattern

3.3 Word Ladder — Code và Trace

from collections import defaultdict, deque

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList: return 0
    L = len(beginWord)
    # Build map: pattern → list of words
    patterns = defaultdict(list)
    for w in wordList:
        for i in range(L):
            patterns[w[:i] + '*' + w[i+1:]].append(w)

    visited = {beginWord}
    q = deque([(beginWord, 1)])
    while q:
        word, level = q.popleft()
        for i in range(L):
            p = word[:i] + '*' + word[i+1:]
            for nei in patterns[p]:
                if nei == endWord: return level + 1
                if nei not in visited:
                    visited.add(nei)
                    q.append((nei, level + 1))
            patterns[p] = []          # tối ưu: mỗi pattern dùng 1 lần
    return 0

Time O(N × L²) với N = |wordList|, L = |word|.

3.4 Worked Example 6 — Shortest Path in Binary Matrix

Đề (LeetCode #1091): Lưới 0/1, 0 là đi được, 1 là tường. Tìm đường ngắn nhất từ (0,0) đến (n-1, n-1) qua 8 hướng.

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] != 0 or grid[n-1][n-1] != 0: return -1
    DIRS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]    # 8 hướng
    q = deque([(0, 0, 1)])
    visited = {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n-1, n-1): return d
        for dr, dc in DIRS:
            nr, nc = r+dr, c+dc
            if (0 <= nr < n and 0 <= nc < n
                and grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Time O(n²).

Knowledge Check — BFS Shortest Path

4.1 Connected Components Pattern

Đếm components — Pattern chuẩn

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    count = 0
    def dfs(u):
        if u in visited: return
        visited.add(u)
        for v in graph[u]: dfs(v)

    for u in range(n):
        if u not in visited:
            dfs(u)
            count += 1
    return count

Time O(V + E).

Cùng tinh thần Number of Islands: lặp qua mọi node chưa visited, mỗi DFS "phủ" 1 component, tăng count.

4.2 Worked Example 7 — Number of Connected Components

Đề (LeetCode #323): Cho n nodes (0..n-1) và edges. Trả số connected components.

Đây chính là template ở 4.1. Đáng chú ý là có thể giải bằng Union-Find (Phần 5):

def countComponents(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path compression
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            return True
        return False
    count = n
    for u, v in edges:
        if union(u, v):
            count -= 1
    return count

Time O(E × α(n)) với α = hàm Ackermann ngược (gần như hằng số). So với DFS O(V+E), Union-Find tốt hơn khi có nhiều query incrementally.

4.3 Topological Sort — Định nghĩa và DFS Approach

Ứng dụng: build dependency, course prerequisites, task scheduling.

DFS Approach — Post-order trên DFS tree

def topo_dfs(graph, n):
    visited = [0] * n              # 0=chưa, 1=đang trong stack, 2=xong
    order = []
    def dfs(u):
        if visited[u] == 1: raise Exception("Cycle detected")
        if visited[u] == 2: return
        visited[u] = 1
        for v in graph[u]: dfs(v)
        visited[u] = 2
        order.append(u)            # thêm KHI XONG (post-order)
    for u in range(n):
        if visited[u] == 0: dfs(u)
    return order[::-1]             # đảo lại

3-color marking: 0 = chưa thăm, 1 = đang trong stack hiện tại (gặp lại = chu kỳ), 2 = đã xử lý xong.

4.4 Topological Sort — BFS Approach (Kahn's)

Ý tưởng: bắt đầu từ các node có in-degree = 0, "tháo gỡ" từng node và giảm in-degree của neighbors.

def topo_kahn(graph, n):
    in_deg = [0] * n
    for u in range(n):
        for v in graph[u]:
            in_deg[v] += 1
    q = deque([u for u in range(n) if in_deg[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    if len(order) != n: return []     # có chu kỳ
    return order

So sánh DFS vs Kahn's

4.5 Worked Example 8 — Course Schedule (#207)

Đề: n khoá học (0..n-1), prerequisites[i] = [a, b] nghĩa là phải học b trước a. Trả True nếu có thể học hết.

Bài này = "DAG có chu kỳ không?". Dùng Kahn's algorithm: nếu có chu kỳ, một số node sẽ không bao giờ có in-degree = 0 → order ngắn hơn n.

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_deg = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)              # b → a (học b trước)
        in_deg[a] += 1
    q = deque([u for u in range(numCourses) if in_deg[u] == 0])
    completed = 0
    while q:
        u = q.popleft()
        completed += 1
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    return completed == numCourses

Time O(V + E).

4.6 Worked Example 9 — Course Schedule II (#210)

Đề: Tương tự #207 nhưng trả về thứ tự học hợp lệ. [] nếu không thể.

Đây chính là Topological Sort. Sửa nhỏ #207:

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_deg = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_deg[a] += 1
    q = deque([u for u in range(numCourses) if in_deg[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    return order if len(order) == numCourses else []

Knowledge Check — Topological Sort

5.1 Union-Find (Disjoint Set Union)

Cấu trúc cho 2 thao tác chính:

• find(x) — trả root của tập chứa x.
• union(a, b) — gộp tập chứa a và b.

Cài đặt với 2 tối ưu

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]    # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

Time O(α(n)) per op (gần như hằng số). Path compression + union by rank đảm bảo độ phức tạp này.

5.2 Worked Example 10 — Number of Provinces

Đề (LeetCode #547): Ma trận isConnected[i][j] = 1 nếu thành phố i và j liên kết trực tiếp. Đếm số "tỉnh" (cluster các thành phố liên thông).

Approach Union-Find

def findCircleNum(isConnected):
    n = len(isConnected)
    dsu = DSU(n)
    for i in range(n):
        for j in range(i+1, n):
            if isConnected[i][j] == 1:
                dsu.union(i, j)
    return sum(1 for i in range(n) if dsu.find(i) == i)

Time O(n² × α(n)) — chi phối bởi việc duyệt ma trận.

Khi nào ưu tiên Union-Find?

• Có nhiều query "u và v cùng component không?" theo thứ tự.
• Khi edges đến dạng stream — không thể build graph đầy đủ trước.
• Bài đếm components, redundant connections, valid tree.

6.1 Dijkstra's Shortest Path — Sử dụng Min-heap (Tuần 9)

Cho graph weighted với cạnh không âm. Tìm shortest path từ source.

Tinh thần

BFS không hoạt động vì cạnh có trọng số khác nhau. Thay queue bằng min-heap — luôn xử lý node có distance nhỏ nhất hiện tại trước.

import heapq
def dijkstra(graph, source, n):
    dist = [float('inf')] * n
    dist[source] = 0
    h = [(0, source)]
    while h:
        d, u = heapq.heappop(h)
        if d > dist[u]: continue                # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(h, (nd, v))
    return dist

Time O((V + E) log V).

7.0 Decision Tree — Khi nào dùng pattern nào?

Tổng kết Tuần 10

Đã học

• Graph fundamentals: directed/undirected, adjacency list/matrix, visited set với mark khi push.
• Grid as graph: 4/8 hướng, in-place mark, multi-source BFS.
• BFS for shortest path: tính chất level-by-level; Word Ladder với generic pattern.
• DFS: connected components, topological sort post-order, 3-color cycle detection.
• Topological Sort: Kahn's BFS với in-degree, Course Schedule I/II.
• Union-Find: path compression + union by rank → O(α(n)) per op.
• Dijkstra preview: kết hợp BFS + Heap (Tuần 9) cho weighted shortest path.

Bài về nhà (12 bài)

1. LeetCode #200 — Number of Islands
2. LeetCode #695 — Max Area of Island
3. LeetCode #994 — Rotting Oranges
4. LeetCode #286 — Walls and Gates
5. LeetCode #127 — Word Ladder (Hard)
6. LeetCode #1091 — Shortest Path in Binary Matrix
7. LeetCode #207 — Course Schedule
8. LeetCode #210 — Course Schedule II
9. LeetCode #547 — Number of Provinces (cả DFS và Union-Find)
10. LeetCode #323 — Number of Connected Components
11. LeetCode #785 — Is Graph Bipartite?
12. LeetCode #743 — Network Delay Time (Dijkstra)