Chuyển tới nội dung chính
Z Graph & Pathfinding

Trình trực quan hóa Tìm kiếm theo chiều sâu (DFS)

Tìm kiếm theo chiều sâu tương tác trên lưới ô vuông — vẽ tường, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình khám phá đào sâu. Chạy ngay trong trình duyệt.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

Mã giả

Cách dùng

  1. 1 Vẽ tường bằng cách nhấp và kéo chuột; kéo điểm bắt đầu màu xanh hoặc điểm đích màu đỏ để di chuyển chúng.
  2. 2 Nhấn Play để xem DFS đào sâu theo một đường đi trước khi quay lui.
  3. 3 Dùng Maze để tạo chướng ngại vật ngay lập tức, hoặc Step để chạy từng nút một.
  4. 4 Đường đi mà DFS tìm được sẽ tới đích nhưng thường không phải là đường ngắn nhất.

Vì sao dùng công cụ này

  • Xem DFS dấn sâu theo một hướng duy nhất và chỉ quay lui khi bị mắc kẹt.
  • Hiểu vì sao DFS không đảm bảo tìm ra đường đi ngắn nhất.
  • So sánh cách đào sâu của DFS với các vòng lan tỏa đều của BFS và cách tìm mục tiêu của A*.
  • Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

Câu hỏi thường gặp

Tìm kiếm theo chiều sâu (depth-first search) là gì?

DFS khám phá một đồ thị bằng cách đi sâu nhất có thể theo từng nhánh trước khi quay lui, thường sử dụng ngăn xếp (stack) hoặc đệ quy.

Độ phức tạp thời gian của DFS là bao nhiêu?

O(V + E) — giống như BFS, nó xét mỗi đỉnh và mỗi cạnh đúng một lần.

DFS có tìm ra đường đi ngắn nhất không?

Không. DFS tìm ra một đường đi nếu tồn tại, nhưng nó đi theo bất kỳ nhánh nào nó gặp trước, nên kết quả thường dài hơn đường đi ngắn nhất. Hãy dùng BFS, Dijkstra, hoặc A* để tìm đường đi ngắn nhất.

DFS phù hợp cho những bài toán nào?

Sắp xếp tô pô (topological sorting), phát hiện chu trình, tìm thành phần liên thông, tạo mê cung, và bất kỳ bài toán nào cần khám phá toàn bộ cấu trúc thay vì tìm mục tiêu gần nhất.

Trình trực quan hóa Tìm kiếm theo chiều sâu (DFS) là gì?

Trình trực quan hóa Tìm kiếm theo chiều sâu (DFS) mô phỏng cách DFS khám phá một lưới ô vuông bằng cách đi sâu nhất có thể theo một nhánh trước khi quay lui, sử dụng cấu trúc ngăn xếp (stack). Nó tìm ra một đường đi tới đích, nhưng khác với BFS, đường đi đó thường không phải là ngắn nhất.

Tính năng

Hoạt ảnh từng bước

Xem quá trình duyệt đi sâu và quay lui dọc theo từng nhánh.

Độ phức tạp

Thời gian: O(V + E). Không gian: O(V) cho ngăn xếp / đệ quy.

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

graph 1–2, 1–3, 2–4, 3–4; start 1

Output

visit order: 1 → 2 → 4 → 3 (deep, then backtrack)

Trường hợp sử dụng

  1. 1

    Phát hiện chu trình

    Xem cách DFS tìm ra các cạnh ngược (back edge) cho biết sự tồn tại của chu trình.

  2. 2

    Sắp xếp tô-pô

    Hiểu cách DFS được dùng để sắp xếp thứ tự các đỉnh của một DAG.

  3. 3

    Thành phần liên thông

    Khám phá toàn bộ khả năng tiếp cận từ một đỉnh xuất phát.

Tóm tắt

Công cụ trực quan hóa DFS của Zerethon mô phỏng thuật toán tìm kiếm theo chiều sâu trên đồ thị ngay trong trình duyệt, đi sâu nhất có thể theo từng nhánh trước khi quay lui, sử dụng ngăn xếp hoặc đệ quy. DFS chạy với thời gian O(V + E) và không gian O(V). Thuật toán này là nền tảng của phát hiện chu trình, sắp xếp tô-pô và kiểm tra tính liên thông.

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

Tài liệu tham khảo

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa Tìm kiếm theo chiều sâu (DFS) chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Graph Algorithms →

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Dùng thử Zerethon miễn phí