Bốn thuật toán đầu bỏ qua trọng số. Hai thuật toán cuối do trọng số quyết định. Bấm từng thuật toán để xem nó đi trên cùng một đồ thị.
The first four ignore weights. The last two are decided by them. Tap each algorithm to watch it walk the same graph.
Số thứ tự là thứ tự nên học: mỗi thuật toán dựa trên thuật toán trước.
Numbers are a learning order: each builds on the one before.
Chọn một thuật toánPick an algorithm
Cả sáu chạy trên cùng đồ thị 6 đỉnh, 7 cạnh, xuất phát từ A.All six run on the same 6-vertex, 7-edge graph, starting from A.
Chọn cái nào
Which one to use
Trước hết: có thể bạn không cần thuật toán nào
First: you may need none of them
Cấu trúc thực chất là cây có gốc (thư mục, sơ đồ tổ chức): một vòng đệ quy là đủ, không cần visited hay phát hiện chu trình.The structure is really a rooted tree (folders, org charts): a plain recursive walk is enough, no visited set or cycle check.
Dữ liệu nằm trong SQL: WITH RECURSIVE xử lý duyệt phân cấp ở quy mô vừa.Data lives in SQL: WITH RECURSIVE handles hierarchy traversal at moderate scale.
Chỉ hỏi “hai đỉnh có thông nhau không” và cạnh chỉ được thêm: Union-Find, gần O(1) mỗi câu.Only asking “are these connected” and edges are only added: Union-Find, near O(1) per query.
Đã có NetworkX, JGraphT, Boost Graph hoặc Neo4j: dùng thư viện, chỉ tự viết khi đã đo thấy nút thắt.NetworkX, JGraphT, Boost Graph or Neo4j exist: use them, hand-roll only after measuring a bottleneck.
Chỉ cần láng giềng trực tiếp của một đỉnhOnly the direct neighbours of a vertex
Tra danh sách kề, không cần thuật toánAdjacency lookup, no algorithm
Từ đây đi tới được đâu? Có đường không?What can I reach? Is there a path?
DFS — duyệt theo chiều sâuDFS — depth-first search
Duyệt đồ thịTraversal
A B C E F DA B C E F D
Đi một mạch tới cuối nhánh rồi lùi lại. Dùng stack hoặc đệ quy, O(V + E).
Run to the end of a branch, then back up. Stack or recursion, O(V + E).
Dùng choUse for
Sắp xếp topo cho hệ thống build và trình quản lý gói, thành phần liên thông, pha mark của GC, backtracking.Topological sort for builds and package managers, connected components, GC mark phase, backtracking.
ĐượcGain
Bộ nhớ chỉ tỷ lệ với độ sâu; có thứ tự vào/ra cho sắp xếp topo và SCC.Memory scales with depth only; gives entry/exit order for topo sort and SCCs.
MấtLose
Không cho đường ngắn nhất; đệ quy tràn stack ở khoảng 1.000 tầng trong Python.No shortest path; recursion overflows around 1,000 frames in Python.
Chọn DFS là đổi sự đảm bảo đường ngắn nhất lấy bộ nhớ chỉ tỷ lệ với độ sâu và thứ tự vào/ra của từng đỉnh.
Choosing DFS trades the shortest-path guarantee for memory proportional to depth plus entry/exit order for every vertex.
Dấu hiệu nhận biếtRecognition signalBạn cần khám phá trọn một vùng, hoặc cần biết lúc mỗi đỉnh bắt đầu và xong việc.You need to explore a whole region, or know when each vertex starts and finishes.
2
BFS — duyệt theo chiều rộngBFS — breadth-first search
Duyệt đồ thịTraversal
A B C D E FA B C D E F
Loang ra theo từng tầng bằng queue. Đường ít cạnh nhất, O(V + E).
Spread out layer by layer with a queue. Fewest-edges path, O(V + E).
Dùng choUse for
Bạn bè cấp 1–2–3, mê cung dạng lưới, crawler giới hạn độ sâu, flood fill.1st–2nd–3rd-degree connections, grid mazes, depth-limited crawlers, flood fill.
ĐượcGain
Đảm bảo ít cạnh nhất khi mọi cạnh như nhau; thông tin tầng có sẵn.Guaranteed fewest edges when all edges are equal; layers come for free.
MấtLose
Bộ nhớ theo độ rộng tầng: bậc 200 thì tầng 3 tới 8 triệu đỉnh; vô dụng khi trọng số khác nhau.Memory follows layer width: degree 200 means 8 million at layer 3; useless with varying weights.
Chọn BFS là đổi bộ nhớ giữ trọn một tầng biên lấy sự đảm bảo tìm được đường ít cạnh nhất.
Choosing BFS trades memory for a whole frontier layer for a guaranteed fewest-edges path.
Dấu hiệu nhận biếtRecognition signalCâu hỏi có chữ “ít bước nhất”, “cách mấy bậc” hoặc “trong phạm vi N”.The question says “fewest steps”, “how many degrees apart” or “within N”.
3
Phát hiện chu trìnhCycle detection
Kiểm tra cấu trúcStructural check
Có vòng A–B–C–ACycle A–B–C–A
Vô hướng: gặp đỉnh đã thăm không phải cha. Có hướng: cạnh trỏ vào đỉnh “xám” đang trên đường đi.
Undirected: reach a visited vertex that isn’t the parent. Directed: an edge into a “grey” vertex on the current path.
Dùng choUse for
Deadlock trong PostgreSQL, import cycle trong Go, DAG trong Airflow, circular reference trong bảng tính.Deadlocks in PostgreSQL, import cycles in Go, Airflow DAGs, spreadsheet circular references.
ĐượcGain
Tuyến tính; lần ngược parent là in ra chính chu trình làm bằng chứng.Linear; walking parents back prints the actual cycle as evidence.
MấtLose
Áp nhầm quy tắc vô hướng cho đồ thị có hướng là sai; liệt kê mọi chu trình bùng nổ cấp số mũ.Using the undirected rule on a directed graph is wrong; listing all cycles blows up exponentially.
Chọn Union-Find thay DFS là đổi khả năng chỉ ra chu trình và hỗ trợ đồ thị có hướng lấy kiểm tra gần O(1) mỗi khi thêm cạnh.
Choosing Union-Find over DFS trades pointing to the cycle and directed support for a near-O(1) check per added edge.
Dấu hiệu nhận biếtRecognition signalDữ liệu được giả định là cây hoặc DAG, và sai giả định thì hệ thống treo.Your data is assumed to be a tree or DAG, and a broken assumption hangs the system.
4
Kiểm tra hai phíaBipartite check
Kiểm tra cấu trúcStructural check
Không — chu trình lẻ A–B–CNo — odd cycle A–B–C
Tô hai màu sao cho mọi cạnh nối hai màu khác nhau. Thất bại khi và chỉ khi có chu trình lẻ.
Two-colour so every edge joins different colours. Fails exactly when an odd cycle exists.
Dùng choUse for
Ghép ứng viên – vị trí, chia hai ca hoặc hai đội, kiểm tra đồ thị người dùng – sản phẩm.Matching candidates to roles, splitting two shifts or teams, validating user–item graphs.
ĐượcGain
Tuyến tính, trả về luôn cách chia; mở đường cho Hopcroft–Karp O(E·√V).Linear, returns the split itself; unlocks Hopcroft–Karp in O(E·√V).
MấtLose
Chỉ đúng hai màu — ba màu là NP-đầy đủ; một cạnh xung đột hỏng cả kết luận.Two colours only — three is NP-complete; one conflicting edge sinks the verdict.
Chọn mô hình hai phía là đổi sự tổng quát (chỉ hai nhóm) lấy kiểm tra tuyến tính và các thuật toán ghép cặp hiệu quả.
Choosing a bipartite model trades generality (exactly two groups) for a linear check and efficient matching algorithms.
Dấu hiệu nhận biếtRecognition signalBài toán có đúng hai loại đối tượng, hoặc các cặp “phải khác nhóm”.There are exactly two kinds of things, or pairs that “must be in different groups”.
5
Cây khung nhỏ nhất (MST)Minimum spanning tree
Tối ưu theo trọng sốWeighted optimisation
5 cạnh, tổng 135 edges, total 13
V − 1 cạnh nối mọi đỉnh với tổng trọng số nhỏ nhất. Kruskal O(E log E), Prim O(E log V).
V − 1 edges connecting every vertex at the lowest total weight. Kruskal O(E log E), Prim O(E log V).
Dùng choUse for
Kéo cáp, đường ống, lưới điện; phân cụm single-linkage; xấp xỉ TSP trong phạm vi 2 lần tối ưu.Laying cable, pipes, power grids; single-linkage clustering; TSP approximation within 2× optimal.
ĐượcGain
Tham lam mà vẫn tối ưu chứng minh được; trọng số khác nhau thì kết quả duy nhất.Greedy yet provably optimal; distinct weights give a unique result.
MấtLose
Không tối ưu đường giữa hai điểm; đứt một cạnh là mạng tách đôi; chỉ cho đồ thị vô hướng.Doesn’t optimise paths between two points; one cut splits the network; undirected only.
Chọn MST là đổi khả năng dự phòng và đường ngắn giữa hai điểm lấy tổng chi phí xây dựng nhỏ nhất.
Choosing an MST trades redundancy and short point-to-point paths for the lowest total build cost.
Dấu hiệu nhận biếtRecognition signalBạn trả tiền một lần cho mỗi cạnh xây lên, và chỉ cần mọi điểm thông nhau.You pay once per edge you build, and only need everything connected.
6
Đường ngắn nhất (Dijkstra)Shortest path (Dijkstra)
Tối ưu theo trọng sốWeighted optimisation
A–C–E–F = 7A–C–E–F = 7
BFS thay queue bằng priority queue. Trọng số phải không âm, O((V + E) log V).
BFS with a priority queue in place of the queue. Weights must be non-negative, O((V + E) log V).
Dùng choUse for
Định tuyến OSPF/IS-IS, chỉ đường bản đồ (cùng A*), tìm đường trong game, chuyến bay rẻ nhất.OSPF/IS-IS routing, map directions (with A*), game pathfinding, cheapest flights.
ĐượcGain
Tối ưu chứng minh được; một lần chạy cho khoảng cách tới mọi đỉnh; dừng sớm khi lấy được đích.Provably optimal; one run gives distances to every vertex; stops early at the target.
MấtLose
Trọng số âm cho kết quả sai mà không báo lỗi; quy mô châu lục cần tiền xử lý.Negative weights give wrong answers silently; continent scale needs preprocessing.
Chọn Dijkstra là đổi khả năng xử lý trọng số âm lấy tốc độ O((V + E) log V) thay vì O(V·E) của Bellman–Ford.
Choosing Dijkstra trades negative-weight support for O((V + E) log V) instead of Bellman–Ford’s O(V·E).
Dấu hiệu nhận biếtRecognition signalCác cạnh có chi phí khác nhau và câu hỏi là “từ đây tới kia tốn ít nhất bao nhiêu”.Edges cost different amounts and the question is “what’s the least it takes to get there”.
Bảng đánh đổi
Trade-off table
Hai trục quan trọng nhất: có cần trọng số không, và đồ thị có hướng hay vô hướng.
The two axes that matter most: are weights needed, and is the graph directed or undirected.
BFS đánh dấu visited lúc lấy raBFS marking visited on dequeue
Một đỉnh vào queue nhiều lầnA vertex enters the queue many times
Đánh dấu lúc đẩy vàoMark on enqueue
DFS đệ quy trên đồ thị sâuRecursive DFS on a deep graph
Tràn stack ở khoảng 1.000 tầng (Python)Stack overflow near 1,000 frames (Python)
Stack tường minhExplicit stack
Chỉ duyệt từ một đỉnh khi kiểm tra toàn cụcChecking globally from one start vertex
Bỏ qua các thành phần liên thông khácIgnores other connected components
Vòng ngoài lặp qua mọi đỉnh chưa thămOuter loop over every unvisited vertex
Ba câu cần nhớ
Three things to remember
DFS và BFS là hai cách duyệt; bốn thuật toán còn lại là một trong hai cộng thêm một quy tắc — Dijkstra chính là BFS với priority queue.DFS and BFS are the two ways to traverse; the other four are one of them plus a rule — Dijkstra is BFS with a priority queue.
Trọng số chọn thuật toán cho bạn: không trọng số thì BFS, không âm thì Dijkstra, có số âm thì Bellman–Ford.Weights pick the algorithm: unweighted means BFS, non-negative means Dijkstra, negative means Bellman–Ford.
MST tối thiểu tổng chi phí nối mọi điểm, đường ngắn nhất tối thiểu chi phí giữa hai điểm — hai bài khác nhau dù đôi khi trùng đáp án.An MST minimises the cost of connecting everything, a shortest path minimises the cost between two points — different problems, even when the answers coincide.