Depth First Search (DFS) | 🇻🇳

Tham khảo từ Depth First Search | CP-Algorithms

Depth First Search hay DFS là một giải thuật cơ bản và quan trọng trong lý thuyết đồ thị. DFS là nền tảng để xây dựng nên các giải thuật quan trọng khác như tìm đường đi, tìm thành phần liên thông, cây khung, chu trình, luồng, cặp ghép, …

Giải thuật DFS tìm ra các đường đi theo thứ tự từ đỉnh nguồn $u$ tới mọi đỉnh khác. Trên đồ thị cây, giữa 2 đỉnh bất kì chỉ có 1 đường đi đơn duy nhất do đó DFS tìm ra đường đi ngắn nhất giữa 2 đỉnh trên cây.

Độ phức tạp của giải thuật DFS là $O(m + n)$ với $n$ là số đỉnh và $m$ là số cạnh trên đồ thị.

Giải thuật DFS

Ý tưởng đơn giản của DFS là duyệt lần lượt từng đỉnh trên đồ thị, tới đỉnh nào đánh dấu lại đỉnh đó đã được duyệt và tiếp tục duyệt các đỉnh liền kề tiếp theo, quay lui khi đã duyệt xong các đỉnh.

Hiện thực giải thuật bằng kỹ thuật đệ quy quay lui đơn giản hoặc sử dụng stack.

Implementation

Hiện thực đơn giản nhất cho DFS như sau:

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> visited;

void dfs(int v) {
	visited[v] = true;
	for (int u : adj[v]) {
		if (!visited[u])
			dfs(u);
    }
}

Mở rộng DFS: lưu thêm thời gian thăm đỉnh vào / ra dùng cho việc kiểm tra thứ tự thăm đỉnh ở một số giải thuật khác.

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<int> color;

vector<int> time_in, time_out;
int dfs_timer = 0;

void dfs(int v) {
	time_in[v] = dfs_timer++;
	color[v] = 1;
	for (int u : adj[v])
		if (color[u] == 0)
			dfs(u);
	color[v] = 2;
	time_out[v] = dfs_timer++;
}

Ứng dụng của DFS

Một số ứng dụng của giải thuật DFS:

Tìm đường đi từ đỉnh nguồn $u$ tới mọi đỉnh trong đồ thị.
Kiểm tra cha của các đỉnh trên đồ thị cây: sử dụng thời gian duyệt đỉnh vào/ra trên cây khi duyệt để xác định cặp đỉnh $u,v$ có quan hệ tiền bối / hậu bối của nhau hay không. Chi tiết có thể xem trong bài viết tìm cha chung gần nhất trên cây LCA.
Tìm tổ tiên chung gần nhất (LCA: lowest common ancestor) trên cây.
Topological sorting.
Kiểm tra và tìm chu trình trong đồ thị.
Tìm thanh phần liên thông mạnh trong đồ thị có hướng.
Tìm cầu trong đồ thị vô hướng.

Practice Problems

Xem một số bài trên vnspoj

Tutorial SPOJ

Giải thuật DFS

Implementation

Ứng dụng của DFS

Practice Problems