Thuật toán 5 — Đồ thị: BFS, DFS, đường đi & thành phần liên thông

Có một loại bài toán mà mảng, dict hay cây đều bó tay: khi thứ quan trọng nhất không phải là từng đối tượng, mà là quan hệ giữa các đối tượng. Ai chuyển tiền cho ai? Task nào phải chạy trước task nào? Hai bản ghi khách hàng này có thực sự là cùng một người? Những câu hỏi này không phải về giá trị, mà về kết nối — và cấu trúc dữ liệu sinh ra để mô tả kết nối chính là đồ thị (graph).

Đồ thị là công cụ nền tảng của phân tích mạng lưới trong ngân hàng: lần theo dòng tiền qua các tài khoản trung gian, phát hiện vòng tiền khép kín, gom các bản ghi rải rác về cùng một thực thể, và điều phối hàng trăm task phụ thuộc lẫn nhau trong một pipeline dữ liệu. Bài này xây từ khái niệm đến ba thuật toán bạn sẽ dùng nhiều nhất — duyệt (BFS/DFS), đường đi ngắn nhất, và sắp xếp topo — kèm code minh hoạ Python và use case thực tế.

Bài này giả định bạn đã quen với Cấu trúc dữ liệu cơ bản (list, dict, set, queue) và Trees & heaps — vì đồ thị là tổng quát hoá của cây, còn Dijkstra dựa trực tiếp trên heap.

1. Đồ thị là gì?

Một đồ thị gồm hai thành phần:

• Đỉnh (vertex / node): một thực thể — khách hàng, tài khoản, task, trạm.
• Cạnh (edge): một quan hệ giữa hai đỉnh — giao dịch chuyển tiền, phụ thuộc task, tuyến đường.

Ký hiệu toán học: G = (V, E), với V là tập đỉnh và E là tập cạnh. Đồ thị có vài biến thể quan trọng, và chọn đúng biến thể là bước mô hình hoá đầu tiên:

• Có hướng (directed) vs vô hướng (undirected): cạnh "A chuyển tiền cho B" có hướng (A → B khác B → A). Cạnh "A và B là bạn bè trên mạng xã hội" thường vô hướng. Trong ngân hàng, dòng tiền gần như luôn có hướng.
• Có trọng số (weighted) vs không trọng số: cạnh có thể mang một con số — số tiền giao dịch, khoảng cách, độ trễ. Nếu chỉ quan tâm "có kết nối hay không", đồ thị là không trọng số.
• Có chu trình vs không chu trình: nếu tồn tại đường đi xuất phát từ một đỉnh rồi quay về chính nó (A → B → C → A), đồ thị có chu trình (cyclic). Một đồ thị có hướng không chu trình gọi là DAG (Directed Acyclic Graph) — nền tảng của mọi pipeline điều phối.

Biểu diễn: danh sách kề vs ma trận kề

Có hai cách lưu đồ thị trong bộ nhớ, và lựa chọn giữa chúng ảnh hưởng lớn đến hiệu năng.

Danh sách kề (adjacency list) — với mỗi đỉnh, lưu danh sách các đỉnh kề nó. Trong Python, cách tự nhiên nhất là một dict ánh xạ đỉnh → danh sách hàng xóm:

# (minh hoạ) Đồ thị có hướng bằng danh sách kề
graph = {
    "KH_A": ["TK_1", "TK_2"],
    "TK_1": ["TK_3"],
    "TK_2": ["TK_3"],
    "TK_3": ["KH_A"],   # cạnh này tạo thành một chu trình!
}

Ma trận kề (adjacency matrix) — một bảng V × V, ô [i][j] = 1 (hoặc trọng số) nếu có cạnh từ i đến j, ngược lại là 0.

Khi nào dùng cái nào?

Hầu hết đồ thị thực tế trong ngân hàng đều thưa — một tài khoản chỉ giao dịch với vài chục đối tác chứ không phải với toàn bộ vài triệu tài khoản. Vì vậy danh sách kề là mặc định. Ma trận kề chỉ hợp lý khi đồ thị nhỏ và đặc, hoặc khi bạn cần phép nhân ma trận (ví dụ đếm số đường đi độ dài k).

2. Duyệt đồ thị: BFS và DFS

Trước khi làm bất cứ điều gì tinh vi, bạn cần duyệt — thăm mọi đỉnh có thể tới được từ một điểm xuất phát. Có hai chiến lược nền tảng, và gần như mọi thuật toán đồ thị khác là biến thể của hai cái này.

BFS — Duyệt theo chiều rộng

BFS (Breadth-First Search) thăm đồ thị theo tầng: trước hết là điểm xuất phát, rồi tất cả hàng xóm trực tiếp (khoảng cách 1 cạnh), rồi hàng xóm của hàng xóm (khoảng cách 2 cạnh), và cứ thế. Nó dùng một queue (hàng đợi) — vào trước ra trước — và một tập visited để không thăm lại.

Điểm mấu chốt: trong đồ thị không trọng số, BFS tự động cho ra đường đi ngắn nhất theo số cạnh, vì nó khám phá các đỉnh đúng theo thứ tự khoảng cách tăng dần.

# (minh hoạ) BFS trên danh sách kề, trả về khoảng cách theo số cạnh
from collections import deque

def bfs_distances(graph, start):
    visited = {start}
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()          # lấy đầu hàng đợi (FIFO)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist

Chi tiết dễ sai: phải đánh dấu visited ngay khi đưa vào queue, không phải khi lấy ra. Nếu chờ đến lúc lấy ra mới đánh dấu, cùng một đỉnh có thể bị đẩy vào queue nhiều lần trước khi được xử lý.

DFS — Duyệt theo chiều sâu

DFS (Depth-First Search) đi sâu hết một nhánh trước khi quay lui. Nó dùng một stack (vào sau ra trước) — hoặc đơn giản là ngăn xếp lời gọi hàm khi viết đệ quy.

# (minh hoạ) DFS đệ quy và DFS lặp bằng stack
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()              # lấy đỉnh stack (LIFO)
        if node not in visited:
            visited.add(node)
            stack.extend(graph.get(node, []))
    return visited

Lưu ý thực tế: DFS đệ quy dễ đọc nhưng nguy hiểm trên đồ thị lớn — Python giới hạn độ sâu đệ quy (mặc định khoảng 1000). Với đồ thị hàng triệu đỉnh có nhánh dài, hãy dùng phiên bản lặp bằng stack để tránh RecursionError.

Chọn cái nào? BFS cho đường đi ngắn nhất và khám phá theo tầng (bán kính lan truyền, số bước từ một tài khoản đến tài khoản khác). DFS cho phát hiện chu trình, sắp xếp topo, và khám phá thành phần liên thông. Cả hai đều có độ phức tạp O(V + E) — mỗi đỉnh và mỗi cạnh được xử lý đúng một lần.

3. Đường đi ngắn nhất

Không trọng số: BFS là đủ

Nếu mọi cạnh "nặng như nhau" (chỉ đếm số bước), BFS ở trên đã giải xong bài toán đường đi ngắn nhất. Muốn dựng lại chính đường đi (không chỉ độ dài), lưu thêm một dict parent ánh xạ mỗi đỉnh về đỉnh mà từ đó ta khám phá ra nó, rồi truy ngược từ đích về nguồn.

Có trọng số không âm: Dijkstra

Khi cạnh có trọng số — số tiền, khoảng cách, chi phí — BFS không còn đúng, vì đường đi "ít cạnh nhất" chưa chắc "tổng trọng số nhỏ nhất". Thuật toán kinh điển là Dijkstra, áp dụng khi mọi trọng số không âm.

Ý tưởng: luôn mở rộng đỉnh gần nguồn nhất trong số các đỉnh chưa xử lý. Để tìm nhanh đỉnh này, ta dùng hàng đợi ưu tiên (min-heap) — chính là cấu trúc heapq đã học ở Trees & heaps. Với mỗi hàng xóm, nếu đi qua đỉnh hiện tại cho đường ngắn hơn đã biết, ta cập nhật (relax) và đẩy vào heap.

# (minh hoạ) Dijkstra bằng heapq — trọng số không âm
import heapq

def dijkstra(graph, start):
    # graph: dict {node: [(neighbor, weight), ...]}
    dist = {start: 0}
    pq = [(0, start)]                    # (khoảng_cách, đỉnh)
    while pq:
        d, node = heapq.heappop(pq)      # đỉnh gần nguồn nhất
        if d > dist.get(node, float("inf")):
            continue                     # bản ghi cũ đã lỗi thời, bỏ qua
        for neighbor, weight in graph.get(node, []):
            nd = d + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    return dist

Vì heapq của Python không hỗ trợ decrease-key, ta dùng thủ thuật phổ biến: cứ đẩy bản ghi mới vào heap, và khi lấy ra một bản ghi có khoảng cách lớn hơn giá trị tốt nhất đã biết (d > dist[node]), ta bỏ qua nó. Độ phức tạp là O((V + E) log V) — rất tốt cho đồ thị thưa.

Khi trọng số âm (ví dụ mô hình hoá hoàn tiền/hoa hồng): Dijkstra sai, phải dùng Bellman-Ford (O(V·E), còn phát hiện được chu trình âm). Khi cần tìm đường tới một đích cụ thể và có "gợi ý khoảng cách" (heuristic), A* nhanh hơn Dijkstra nhờ ưu tiên hướng về đích.

4. Thành phần liên thông & phát hiện chu trình

Thành phần liên thông (connected components)

Một thành phần liên thông là một cụm đỉnh mà bất kỳ hai đỉnh nào trong cụm đều có đường đi tới nhau, nhưng tách biệt với phần còn lại. Đếm và phân tách thành phần liên thông là bước đầu tiên để gom cụm một mạng lớn: chạy BFS/DFS lặp lại, mỗi lần bắt đầu từ một đỉnh chưa thăm sẽ khoanh vùng đúng một thành phần.

Phát hiện chu trình (cycle detection)

Với đồ thị có hướng, một chu trình là đường đi khép kín A → B → C → A. Trong dòng tiền, chu trình thường là dấu hiệu rửa tiền vòng (round-tripping): tiền quay về gần nơi xuất phát sau khi qua nhiều lớp trung gian. Cách phát hiện bằng DFS dùng ba trạng thái màu cho mỗi đỉnh:

# (minh hoạ) Phát hiện chu trình trong đồ thị có hướng (DFS 3 màu)
def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2         # chưa thăm / đang trên stack / xong
    color = {node: WHITE for node in graph}

    def visit(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True              # gặp lại đỉnh đang trên stack → chu trình
            if color.get(neighbor, WHITE) == WHITE and visit(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[n] == WHITE and visit(n) for n in graph)

Nguyên lý: nếu trong lúc đi sâu ta gặp một đỉnh đang màu xám (đang nằm trên đường đi hiện tại), tức là ta vừa đóng một vòng — có chu trình.

Union-Find: gom nhóm cực nhanh

Với đồ thị vô hướng, có một cấu trúc chuyên dụng để trả lời "hai đỉnh này có cùng cụm không?" nhanh gần như tức thời: Union-Find (Disjoint Set Union — DSU). Nó lưu mỗi cụm dưới dạng một cây, với hai tối ưu kinh điển: path compression (nén đường — khi tìm gốc thì gắn thẳng các nút trên đường về gốc) và union by rank/size (gộp cây thấp vào cây cao). Kết hợp cả hai, mỗi thao tác gần như là hằng số (chính xác là O(α(n)), với α là hàm Ackermann nghịch — thực tế coi như hằng số).

# (minh hoạ) Union-Find với path compression + union by rank
class UnionFind:
    def __init__(self, items):
        self.parent = {x: x for x in items}
        self.rank = {x: 0 for x in items}

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # nén đường
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # đã cùng cụm (nếu đang thêm cạnh → chu trình)
        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

Union-Find là công cụ tiêu chuẩn cho entity resolution — gom các bản ghi rải rác về cùng một thực thể (xem phần use case) — và phát hiện chu trình khi xây dần đồ thị vô hướng.

5. Sắp xếp topo trên DAG

Trên một DAG, sắp xếp topo (topological sort) cho ra một thứ tự tuyến tính các đỉnh sao cho: nếu có cạnh A → B thì A luôn đứng trước B. Đây chính là câu trả lời cho câu hỏi "chạy các task theo thứ tự nào để không task nào chạy trước khi phụ thuộc của nó xong".

Thuật toán trực quan nhất là Kahn (BFS-based):

1. Tính bậc vào (in-degree) — số cạnh đi vào — cho mọi đỉnh.
2. Đưa mọi đỉnh có in-degree = 0 (không phụ thuộc gì) vào queue.
3. Lần lượt lấy một đỉnh ra, thêm vào kết quả; với mỗi cạnh đi ra u → v, giảm in-degree của v đi 1; nếu in-degree của v về 0 thì đẩy v vào queue.

# (minh hoạ) Sắp xếp topo bằng thuật toán Kahn — kiêm phát hiện chu trình
from collections import deque

def topological_sort(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] = indegree.get(neighbor, 0) + 1
            indegree.setdefault(node, indegree.get(node, 0))

    queue = deque([n for n, d in indegree.items() if d == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(indegree):
        raise ValueError("Đồ thị có chu trình — không thể sắp xếp topo")
    return order

Một điểm rất tiện: Kahn tự động phát hiện chu trình. Nếu cuối cùng số đỉnh trong kết quả nhỏ hơn tổng số đỉnh, nghĩa là có những đỉnh mãi không về in-degree 0 — chúng nằm trong một chu trình. Đây chính xác là lý do Airflow từ chối một DAG nếu bạn vô tình tạo vòng lặp phụ thuộc.

Có thể thay deque bằng min-heap để chọn đỉnh nhỏ nhất theo thứ tự từ điển ở mỗi bước, khi cần một thứ tự topo xác định (deterministic).

6. Use case thực tế

6.1. Phát hiện mạng mule bằng đồ thị

Trong chống rửa tiền (AML) và gian lận, mule account là các tài khoản trung gian dùng để chuyển tiếp tiền bẩn, che giấu nguồn gốc. Nhìn từng giao dịch riêng lẻ thì mọi thứ có vẻ bình thường; chỉ khi dựng cả mạng lưới mới lộ ra cấu trúc bất thường.

Mô hình hoá: đỉnh là khách hàng và tài khoản, cạnh có hướng là giao dịch chuyển tiền (trọng số = số tiền). Trên đồ thị này:

• Phát hiện vòng tiền (cycle detection): tiền đi A → B → C → A là dấu hiệu điển hình của round-tripping.
• Gom cụm (community / connected components): một cụm tài khoản chỉ giao dịch nội bộ với nhau và ít liên hệ ra ngoài, đặc biệt nếu vừa mở đồng loạt, là ứng viên smurfing.
• Trung tâm (centrality): một tài khoản nhận từ rất nhiều nguồn rồi dồn ra một điểm — bậc vào/ra cao bất thường — là ứng viên fan-in/fan-out điển hình của mule.

Sơ đồ dưới đây minh hoạ một cụm với vòng tiền khép kín (TK_A → TK_B → TK_C → TK_A):

Ba tài khoản tô đỏ tạo thành một chu trình — thứ mà has_cycle phát hiện, còn Union-Find gom chúng vào cùng một cụm để điều tra viên xem xét. Đây là nội dung sâu hơn ở AML — phân tích mạng & công nghệ và FRAML/phát hiện mule.

6.2. Entity resolution bằng Union-Find

Cùng một khách hàng có thể xuất hiện nhiều lần: "Nguyễn Văn A", "NGUYEN VAN A", cùng CMND nhưng khác số điện thoại... Mỗi cặp bản ghi "khớp" (cùng CMND, hoặc cùng số điện thoại + ngày sinh) là một cạnh vô hướng. Chạy union() trên mọi cạnh khớp, rồi các bản ghi có cùng gốc find() chính là cùng một thực thể. Union-Find gom hàng triệu bản ghi thành các cụm thực thể gần như tức thời — nền tảng của bước ghép định danh trong AML.

6.3. Sắp xếp topo cho pipeline dữ liệu

Đây là ứng dụng bạn gặp mỗi ngày nếu làm data engineering. Một Airflow DAG chính là đồ thị có hướng không chu trình: mỗi task là một đỉnh, mỗi quan hệ task_a >> task_b là một cạnh. Scheduler chạy sắp xếp topo để xác định thứ tự thực thi và biết những task nào có thể chạy song song (các đỉnh cùng "tầng"). Nếu bạn vô tình tạo vòng phụ thuộc, Airflow báo lỗi khi parse — chính là bước kiểm tra chu trình của Kahn. Chi tiết ở Airflow — DAG & Task.

Điều tương tự đúng với dbt: mỗi lần model B dùng ref('A'), dbt tạo cạnh A → B, dựng nên DAG toàn dự án, rồi topo sort để chạy các model đúng thứ tự phụ thuộc — bạn không bao giờ phải tự khai báo "chạy A trước B".

6.4. Định tuyến & luồng tiền

Dijkstra và các biến thể trả lời "đường rẻ nhất / nhanh nhất từ A đến B": định tuyến thanh toán qua các mạng trung gian với phí khác nhau, hay tìm đường lan truyền rủi ro ngắn nhất trong mạng liên ngân hàng.

Thực tế: đừng viết lại từ đầu

Với công việc thăm dò, thư viện networkx dựng đồ thị và chạy sẵn BFS/DFS, Dijkstra, thành phần liên thông, topo sort, centrality... chỉ với vài dòng — lý tưởng để phân tích trên vài chục nghìn đến vài trăm nghìn đỉnh trong bộ nhớ. Khi mạng vượt quy mô đó (hàng chục triệu đỉnh, cập nhật liên tục), người ta chuyển sang graph database chuyên dụng (như Neo4j) — chủ đề bàn kỹ trong AML — công nghệ.

7. Ghi nhớ

• Đồ thị = đỉnh + cạnh dùng khi cái quan trọng là quan hệ, không phải giá trị. Xác định sớm: có hướng không? có trọng số không? có thể có chu trình không?
• Danh sách kề (dict của Python) là mặc định vì đồ thị thực tế hầu hết thưa; ma trận kề chỉ hợp với đồ thị nhỏ và đặc.
• BFS duyệt theo tầng → đường đi ngắn nhất theo số cạnh (không trọng số); DFS đi sâu → hợp cho chu trình, topo sort, thành phần liên thông. Cả hai O(V + E).
• Đánh dấu visited khi đưa vào queue, không phải khi lấy ra. DFS đệ quy dễ tràn stack trên đồ thị lớn — dùng bản lặp.
• Dijkstra + heapq cho đường đi ngắn nhất khi trọng số không âm — O((V+E) log V). Có trọng số âm → Bellman-Ford; có heuristic → A*.
• Phát hiện chu trình = dấu hiệu round-tripping trong dòng tiền (DFS 3 màu). Union-Find gom cụm và làm entity resolution gần như hằng số nhờ path compression + union by rank.
• Sắp xếp topo (Kahn) xếp thứ tự chạy trên DAG và tự phát hiện chu trình — chính là cơ chế của Airflow và dbt.
• Thăm dò nhanh: networkx. Quy mô lớn: graph database.

Bài tiếp theo — Quy hoạch động (Dynamic Programming) — chuyển từ "khám phá cấu trúc" sang "tối ưu bằng cách tái sử dụng kết quả con", một tư duy bổ trợ trực tiếp cho các bài toán đường đi và lập lịch.