Đồ thị (Graphs)

Đồ thị mô hình hóa các mối quan hệ và kết nối, từ mạng xã hội đến bản đồ đường đi đến chuỗi phụ thuộc. Tệp này trình bày cách biểu diễn, BFS, DFS, đường đi ngắn nhất, sắp xếp tô pô, và các thành phần liên thông, với các mẫu duyệt và tìm đường chủ đạo trong các bài toán phỏng vấn về đồ thị.

• Ta đã trình bày lý thuyết đồ thị ở chương 12 (ma trận kề, Laplacian, tính chất phổ) và chương 13 (cây, tính phẳng, tô màu). Ở đây ta tập trung vào các mẫu thuật toán: cách duyệt, tìm kiếm, và tối ưu trên đồ thị bằng code.

• Hai thuật toán đồ thị nền tảng là BFS và DFS. Hầu như mọi bài toán về đồ thị đều quy về một trong hai, có thể với các biến thể. Nắm vững hai thuật toán này và bạn có thể giải đại đa số các bài toán về đồ thị.

Các cách Biểu diễn Đồ thị

• Danh sách kề (Adjacency list): với mỗi node, lưu một danh sách các hàng xóm của nó. Không gian: \(O(|V| + |E|)\). Tốt nhất cho đồ thị thưa (hầu hết đồ thị thực tế).

# Đồ thị vô hướng
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# Từ danh sách cạnh
def build_graph(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # bỏ dòng này nếu là có hướng
    return graph

• Ma trận kề (Adjacency matrix): ma trận \(n \times n\) với \(A[i][j] = 1\) nếu cạnh \((i, j)\) tồn tại. Không gian: \(O(|V|^2)\). Tốt nhất cho đồ thị dày đặc hoặc khi bạn cần tra cứu cạnh \(O(1)\).

• Khi nào dùng cái nào: danh sách kề cho hầu hết mọi thứ. Ma trận chỉ khi đồ thị dày đặc (\(|E| \approx |V|^2\)) hoặc bạn cần kiểm tra sự tồn tại cạnh trong thời gian hằng số.

Mẫu: BFS (Breadth-First Search — Tìm kiếm theo chiều rộng)

• BFS khám phá các node theo từng cấp dùng một hàng đợi. Nó là thuật toán lựa chọn cho:
  • Đường đi ngắn nhất trong đồ thị không trọng số
  • Duyệt level-order
  • Tìm các thành phần liên thông
  • Bất kỳ bài toán nào hỏi "số bước tối thiểu"

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

• Quan trọng: thêm vào visited khi đưa vào hàng đợi (enqueuing), không phải khi lấy ra (dequeuing). Nếu bạn đánh dấu đã thăm khi lấy ra, cùng một node có thể được đưa vào hàng đợi nhiều lần từ các node trước khác nhau, lãng phí thời gian và có thể gây kết quả sai.

Dễ: Số lượng Hòn đảo (Number of Islands)

• Bài toán: cho một lưới 2D với '1' (đất) và '0' (nước), đếm số lượng hòn đảo.

• Mẫu: duyệt qua lưới. Khi thấy một '1', BFS/DFS để đánh dấu mọi ô đất liên thông là đã thăm. Mỗi lần bắt đầu BFS là một hòn đảo.

from collections import deque

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                # BFS để đánh dấu toàn bộ hòn đảo
                queue = deque([(r, c)])
                grid[r][c] = '0'  # đánh dấu đã thăm
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count

• Cạm bẫy: khuôn mẫu directions = [(0,1),(0,-1),(1,0),(-1,0)] cho các hàng xóm 4-hướng trên lưới được dùng trong hầu hết mọi bài toán về lưới. Hãy nhớ nó. Đối với 8-hướng, thêm các đường chéo.

• Cạm bẫy: sửa đổi lưới đầu vào (grid[r][c] = '0') tránh cần một tập visited riêng. Điều này chấp nhận được trong phỏng vấn nhưng hãy nói rõ về sự đánh đổi (làm thay đổi đầu vào).

Trung bình: Cam thối (Rotting Oranges)

• Bài toán: cam tươi bị thối nếu kề với cam thối. Trả về thời gian tối thiểu cho đến khi mọi cam đều thối (hoặc -1 nếu không thể).

• Mẫu: BFS đa nguồn. Bắt đầu với mọi cam thối ban đầu trong hàng đợi đồng thời. Mỗi cấp BFS là một bước thời gian.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    time = 0
    while queue and fresh > 0:
        time += 1
        for _ in range(len(queue)):
            cr, cc = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return time if fresh == 0 else -1

• Hiểu biết then chốt: BFS đa nguồn xử lý mọi nguồn đồng thời. Điều này cho khoảng cách ngắn nhất từ bất kỳ nguồn nào, đó chính xác là "mất bao lâu cho đến khi quả cam tươi cuối cùng thối."

Mẫu: DFS (Depth-First Search — Tìm kiếm theo chiều sâu)

• DFS khám phá càng sâu càng tốt trước khi quay lui. Nó dùng một ngăn xếp (tường minh hoặc ngăn xếp lời gọi qua đệ quy). DFS là lựa chọn cho:
  • Phát hiện chu trình
  • Sắp xếp tô pô (topological sorting)
  • Các thành phần liên thông
  • Quay lui / tìm kiếm toàn bộ
  • Tìm đường có ràng buộc

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited)

Trung bình: Lịch học (Course Schedule) — Phát hiện Chu trình

• Bài toán: cho \(n\) khóa học và các điều kiện tiên quyết, xác định xem có thể hoàn thành mọi khóa học không (nghĩa là không có phụ thuộc vòng tròn).

• Mẫu: phát hiện chu trình trong đồ thị có hướng. Dùng DFS với ba trạng thái: chưa thăm, đang xử lý (trên đường đi DFS hiện tại), và đã hoàn thành.

def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # 0 = chưa thăm, 1 = đang xử lý, 2 = đã hoàn thành
    state = [0] * num_courses

    def has_cycle(node):
        if state[node] == 1:
            return True   # cạnh ngược → chu trình
        if state[node] == 2:
            return False  # đã khám phá hoàn toàn

        state[node] = 1  # đánh dấu đang xử lý
        for neighbour in graph[node]:
            if has_cycle(neighbour):
                return True
        state[node] = 2  # đánh dấu đã hoàn thành
        return False

    for course in range(num_courses):
        if has_cycle(course):
            return False
    return True

• Tại sao ba trạng thái: hai trạng thái (đã thăm/chưa thăm) không thể phân biệt "tôi đang khám phá node này" với "tôi đã khám phá xong node này." Tìm thấy một node đang được khám phá (state = 1) nghĩa là ta đã tìm thấy một chu trình. Tìm thấy một node đã được khám phá hoàn toàn (state = 2) chỉ là một cạnh chéo, không phải chu trình.

Trung bình: Lịch học II (Course Schedule II) — Sắp xếp Tô pô

• Bài toán: trả về một thứ tự khóa học hợp lệ (thứ tự tô pô).

• Mẫu (Thuật toán Kahn — dựa trên BFS): bắt đầu với các node không có cạnh vào (bán bậc vào — indegree — bằng 0). Xử lý chúng, giảm bán bậc vào của các hàng xóm. Lặp lại.

from collections import deque

def find_order(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                queue.append(neighbour)

    return order if len(order) == num_courses else []  # [] = có chu trình

• Cạm bẫy: nếu kết quả có ít node hơn đồ thị, một chu trình tồn tại (bán bậc vào của vài node không bao giờ giảm về 0).

Đường đi Ngắn nhất

Thuật toán Dijkstra

• Tìm đường đi ngắn nhất từ một nguồn đến mọi node khác trong đồ thị có trọng số không âm. Dùng hàng đợi ưu tiên (min-heap).

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbour, weight), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # mục cũ trong heap

        for neighbour, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbour]:
                dist[neighbour] = new_dist
                heapq.heappush(heap, (new_dist, neighbour))

    return dist

• Thời gian: \(O((|V| + |E|) \log |V|)\) với heap nhị phân.

• Cạm bẫy: dòng if d > dist[node]: continue là thiết yếu. Thiếu nó, bạn xử lý các mục heap cũ, có thể làm giảm hiệu năng xuống \(O(|V|^2)\).

• Cạm bẫy: Dijkstra không hoạt động với trọng số âm. Nếu một cạnh có trọng số âm, giả định tham lam (một khi node được chốt, khoảng cách của nó là tối ưu) sẽ bị phá vỡ. Hãy dùng Bellman-Ford thay thế.

Khó: Network Delay Time

• Bài toán: cho \(n\) node và các cạnh có hướng có trọng số, tìm thời gian để một tín hiệu đến được mọi node từ một nguồn. Trả về -1 nếu không phải mọi node đều đến được.

def network_delay(times, n, k):
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))

    dist = dijkstra(graph, k)
    max_time = max(dist.values())
    return max_time if max_time < float('inf') else -1

Các Thành phần Liên thông Mạnh (Strongly Connected Components)

• Trong một đồ thị có hướng, một thành phần liên thông mạnh (SCC) là một tập hợp các node tối đại nơi mọi node đều có thể đi đến mọi node khác.

• Thuật toán Kosaraju: (1) DFS trên đồ thị gốc, ghi lại thứ tự kết thúc. (2) Chuyển vị đồ thị (đảo ngược mọi cạnh). (3) DFS trên đồ thị đã chuyển vị theo thứ tự kết thúc ngược. Mỗi cây DFS ở bước 3 là một SCC.

• Khi nào dùng: tìm các phụ thuộc vòng tròn, 2-SAT, cô đặc một đồ thị có hướng thành một DAG các SCC.

---

Tóm tắt các Cạm bẫy Thường gặp

Cạm bẫy	Ví dụ	Sửa
Đánh dấu đã thăm khi lấy khỏi hàng đợi	Cùng node được đưa vào hàng đợi nhiều lần	Đánh dấu đã thăm khi đưa vào hàng đợi
Hai trạng thái trong đồ thị có hướng	Không phân biệt được cạnh ngược với cạnh chéo	Dùng ba trạng thái: chưa thăm/đang xử lý/xong
Dijkstra với trọng số âm	Đường đi ngắn nhất sai	Dùng Bellman-Ford
Quên if d > dist[node]: continue	Xử lý các mục heap cũ	Luôn bỏ qua nếu khoảng cách hiện tại tệ hơn
Kiểm tra biên lưới	Index ngoài phạm vi	0 <= nr < rows and 0 <= nc < cols
Không xét trường hợp biên time=0	Cam thối: không có cam tươi	Kiểm tra fresh == 0 trước BFS
Xây đồ thị có hướng thành vô hướng	Môn tiên quyết chỉ đi một chiều	Chỉ thêm cạnh một hướng

---

Bài tập Tự luyện (NeetCode)

Các Mẫu BFS

• Number of Islands — BFS/DFS trên lưới
• Rotting Oranges — BFS đa nguồn
• Clone Graph — BFS + bản băm để nhân bản
• Pacific Atlantic Water Flow — BFS từ cả hai đại dương
• Word Ladder — BFS trên đồ thị ẩn

Các Mẫu DFS

• Max Area of Island — DFS với đếm diện tích
• Course Schedule — phát hiện chu trình trong đồ thị có hướng
• Course Schedule II — sắp xếp tô pô
• Number of Connected Components — DFS hoặc Union-Find
• Graph Valid Tree — liên thông + không có chu trình

Đường đi Ngắn nhất

• Network Delay Time — Dijkstra
• Cheapest Flights Within K Stops — BFS biến thể/Bellman-Ford với ràng buộc
• Swim in Rising Water — tìm kiếm nhị phân + BFS hoặc Dijkstra trên lưới

Nâng cao

• Alien Dictionary — sắp xếp tô pô từ thứ tự ký tự