Tìm kiếm theo chiều sâu (DFS) cho Đồ thị

Tìm kiếm theo chiều sâu (DFS) là thuật toán duyệt đồ thị. Cho một đỉnh bắt đầu, khi tìm thấy đỉnh kề, nó chuyển sang đỉnh kề đó trước và thử duyệt theo cùng cách.

Nó đi sâu qua toàn bộ độ sâu, bao nhiêu thì bấy nhiêu, sau đó quay lui (backtrack) để về đỉnh trước tìm đường mới.

Để cài đặt DFS lặp, cần dùng cấu trúc dữ liệu Ngăn xếp (Stack). Nếu đệ quy, không cần ngăn xếp bên ngoài, dùng ngăn xếp nội bộ của lời gọi đệ quy.

Đầu vào: Ma trận kề của đồ thị.

 A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0

Đầu ra: Duyệt DFS: C F E B D A

Thuật toán

dfs(vertices, start)

Đầu vào − Danh sách tất cả đỉnh, và nút bắt đầu.

Đầu ra − Duyệt tất cả nút trong đồ thị.

Begin
    ban đầu đặt trạng thái chưa thăm cho tất cả nút
    đẩy start vào ngăn xếp
    while ngăn xếp không rỗng, do
        lấy phần tử từ ngăn xếp gán cho u
        hiển thị nút u
        if u chưa thăm, then
            đánh dấu u là đã thăm
            for all nút i kết nối với u, do
                if đỉnh i chưa thăm, then
                    đẩy đỉnh i vào ngăn xếp
                    đánh dấu đỉnh i là đã thăm
                done
        done
End

Ví dụ (C++)

#include 
#include 
using namespace std;
#define NODE 6
typedef struct node{
    int val;
    int state; //trạng thái
}node;
int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};
void dfs(node *vertex, node start){
    node u;
    stack myStack;
    for(int i = 0; i
Đầu ra
DFS Traversal: C F E B D A