Thuật toán DFS (Depth-First Search) là gì? Giải thích dễ hiểu kèm demo trực quan

Thuật toán DFS (Depth-First Search) là gì? Giải thích dễ hiểu kèm demo trực quan

DFS (Depth-First Search) là thuật toán duyệt và tìm kiếm trên đồ thị theo kiểu “đi thật sâu” vào một nhánh trước, chỉ khi không đi được nữa mới quay lui (backtrack) để đi nhánh khác.

Nếu BFS duyệt theo “tầng” (layer) thì DFS duyệt theo “chiều sâu” (depth). DFS thường được cài đặt bằng đệ quy hoặc dùng stack.

DFS giải bài toán gì?

• Duyệt toàn bộ đồ thị (graph / tree).
• Kiểm tra tính liên thông của đồ thị.
• Tìm đường đi (không đảm bảo ngắn nhất như BFS).
• Là nền tảng cho nhiều thuật toán:
  • Topological Sort.
  • Tìm thành phần liên thông (Connected Components).
  • Tìm cầu (Bridge), khớp (Articulation Points).
  • Tìm chu trình (cycle detection).

Ý tưởng chính của DFS

Với cách cài đặt bằng stack (phiên bản demo trong bài):

1. Chọn đỉnh bắt đầu, đánh dấu là đã thăm (visited) và đưa vào stack.
2. Lặp cho đến khi stack rỗng:
   • Lấy đỉnh ở đỉnh stack ra (pop) – gọi là current.
   • Duyệt các hàng xóm (neighbor) của current.
   • Nếu neighbor chưa được thăm:
     • Đánh dấu visited.
     • Lưu “đỉnh trước đó” (previous) để truy vết đường đi.
     • Đưa neighbor vào stack.

DFS không đảm bảo tìm được đường đi ngắn nhất, nhưng lại rất hữu dụng để “khám phá” cấu trúc đồ thị.

Độ phức tạp

• Thời gian: O(V + E) (V là số đỉnh, E là số cạnh).
• Bộ nhớ: O(V) cho stack + visited + previous.

Đồ thị minh họa

Dùng lại đồ thị nhỏ với các đỉnh A → F:

A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E

Đồ thị là vô hướng: có cạnh A – B thì đi được A → B và B → A.

Demo DFS bằng JavaScript (tìm một đường đi từ nguồn đến đích)

Demo dưới đây cho phép chọn đỉnh bắt đầu và đỉnh kết thúc, sau đó chạy DFS (dùng stack) để:

• Hiển thị trạng thái từng đỉnh: đã thăm hay chưa, đỉnh hiện tại.
• Hiển thị stack ở mỗi bước (push / pop).
• Log từng bước: push đỉnh nào, pop đỉnh nào.
• Xây dựng lại một đường đi từ nguồn đến đích (nếu tồn tại).

Phân tích đoạn code DFS

1. DFS dùng stack và log từng bước

var graph = {
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "F"],
    D: ["B"],
    E: ["B", "F"],
    F: ["C", "E"]
};

var nodes = ["A", "B", "C", "D", "E", "F"];

function dfsWithSteps(start, end) {
    var visited = {};
    var prev = {};
    var stack = [];
    var steps = [];

    nodes.forEach(function(n) {
        visited[n] = false;
        prev[n] = null;
    });

    visited[start] = true;
    stack.push(start);

    steps.push({
        type: "push",
        node: start,
        from: null,
        stack: stack.slice(),
        visited: Object.assign({}, visited)
    });

    while (stack.length > 0) {
        var current = stack.pop();

        steps.push({
            type: "pop",
            node: current,
            stack: stack.slice(),
            visited: Object.assign({}, visited)
        });

        if (current === end) {
            break;
        }

        // Duyệt neighbors theo thứ tự đảo ngược để stack xử lý theo thứ tự "tự nhiên"
        var neigh = graph[current].slice().reverse();

        neigh.forEach(function(nei) {
            if (!visited[nei]) {
                visited[nei] = true;
                prev[nei] = current;
                stack.push(nei);

                steps.push({
                    type: "push",
                    node: nei,
                    from: current,
                    stack: stack.slice(),
                    visited: Object.assign({}, visited)
                });
            }
        });
    }

    return {
        steps: steps,
        prev: prev
    };
}

2. Xây dựng lại đường đi từ prev

function buildDfsPath(prev, start, end) {
    var path = [];
    var cur = end;

    while (cur !== null) {
        path.unshift(cur);
        if (cur === start) break;
        cur = prev[cur];
    }

    if (path[0] !== start) return null;
    return path;
}

Khi nào nên dùng DFS?

• Khi cần duyệt toàn bộ đồ thị theo chiều sâu.
• Khi cần phát hiện chu trình, thành phần liên thông, topo sort.
• Khi bài toán có tính chất “quay lui / nhánh cận” (backtracking).

Kết luận

DFS là thuật toán lõi cho rất nhiều bài toán đồ thị và tìm kiếm trạng thái. Dù không đảm bảo đường đi ngắn nhất như BFS, DFS lại rất mạnh khi cần “khám phá sâu” cấu trúc hoặc không gian nghiệm.

Với demo trực quan dùng stack ở trên, từng bước push, pop và đánh dấu visited đều được minh họa rõ ràng, giúp việc nắm bắt DFS trở nên nhẹ nhàng và dễ quan sát.