# Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS)

Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) là một thuật toán tìm kiếm/duyệt trên đồ thị.

Xuất phát từ một đỉnh u, thuật toán DFS sẽ thực hiện việc duyệt đồ thị theo chiều sâu (depth-first). Ở mỗi bước, thuật toán sẽ chọn một đỉnh bất kì kề với đỉnh u mà chưa được duyệt. Sau đó, thuật toán sẽ thực hiện việc duyệt DFS một cách đệ quy đối với đỉnh ấy. Quá trình sẽ lặp lại cho đến khi tất cả hàng xóm của u đã được duyệt. Khi này, thuật toán "quay lui" và tiếp tục với các đỉnh hàng xóm chưa được duyệt khác, nếu có.

Ta có một đồ thị vô hướng:

Giả sử ta bắt đầu thực hiện DFS từ đỉnh 1, quá trình của thuật toán sẽ diễn ra như sau: 1 \rightarrow 2 \rightarrow 5 \rightarrow (quay lui về 2) \rightarrow 6 \rightarrow (quay lui về 2) \rightarrow 3 \rightarrow 4 \rightarrow (quay lui về 3) \rightarrow (quay lui về 2) \rightarrow (quay lui về 1).

Khi thực hiện thuật toán DFS, ta nhận thấy mỗi đỉnh của đồ thị sẽ được duyệt nhiều nhất 1 lần, và mỗi cạnh sẽ được duyệt nhiều nhất 2 lần đối với đồ thị vô hướng, hoặc 1 lần đối với đồ thị có hướng.

Tùy vào cách tổ chức đồ thị mà nó sẽ anh hưởng đến độ phức tạp của thuật toán DFS, với các độ phức tạp thời gian O(|V|^2), O(|V| + |E|), O(|V|\times |E|) nếu ta sử dụng ma trận kề, danh sách kề hoặc danh sách cạnh theo thứ tự tương ứng.

Việc cài đặt DFS là một việc vô cùng đơn giản. Một chương trình thực hiện DFS điển hình sẽ sử dụng một mảng giá trị vst chứa n phần tử (n là số lượng đỉnh trong đồ thị) biểu thị nếu đỉnh u đã được duyệt hay chưa, và một danh sách kề adj lưu thông tin về đồ thị:

void dfs(int u){
	if(vst[u]) return;
	vst[u] = 1;

	// xử lí đỉnh u
	
	for(int v : adj[u]){
        dfs(v);
    } 
}

Như đã được nói ở phần stack, ta có thể cài đặt DFS bằng cách sử dụng stack, mặc dù cách cài đặt này không phổ biến bằng cách cài đặt ở trên.

void dfs(int s){
    stack<int> st;
    st.push(s);
    while(st.size()){
        int u = st.top(); st.pop();
        if(vst[u]) continue;
        vst[u] = 1;

        // Xử lí đỉnh u

        for(int v : adj[u]){
            st.push(v);
        }
    }
}