Thuật Toán Tìm Kiếm Theo Chiều Sâu DFS

THUẬT TOÁN DUYỆT CHIỀU SÂU DFS

Thuật toán DFS (Depth First Search) là thuật toán tìm kiếm theo chiều sâu bắt đầu từ một đỉnh bất kì trong một đồ thì vô hướng, có hướng hoặc trong một cây.

Thuật Toán Tìm Kiếm Theo Chiều Sâu DFS

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• DFS: duyệt theo chiều sâu bắt đầu từ đỉnh u.
• Nếu tồn tại đỉnh v trong danh sách kề adj[u] của đỉnh u chưa được thăm thì tiến hành thăm v sau đó duyệt chiều sâu với đỉnh v
• Nếu tất cả các đỉnh kề với u đã được thăm thì DFS quay trở lại đỉnh x mà từ đó thăm u để tiến hành thăm các đỉnh khác kề với x mà chưa được thăm. Lúc này đỉnh u được gọi là đã duyệt xong
• Thuật toán được code trên ngôn ngữ C++

VÍ DỤ:

CODE MẪU:

	#include<iostream>
	#include<vector>
	#include<stack>
	#include<list>
	using namespace std;
	void dfs(vector<list<int>> adj) {
	stack<int> S; // Ngăn xếp lưu các đỉnh sẽ được duyệt tiếp theo
	vector<bool> visited(adj.size()); // Đánh dấu các đỉnh đã duyệt
	S.push(1); // Bắt đầu từ đỉnh số 1
	while(!S.empty()) {
	int u = S.top(); // Gán u cho đỉnh trên cùng của stack
	// Kiểm tra xem u đã được duyệt chưa
	if (!visited[u]) {
	visited[u] = 1;
	cout << u << endl;
	}
	// Kiểm tra danh sách kề của u
	if (!adj[u].empty()) {
	int v = adj[u].front();
	adj[u].pop_front();
	if (!visited[v]) {
	S.push(v);
	}
	} else {
	S.pop();
	}
	}
	}
	int main() {
	int n = 7; // số đỉnh
	vector<list<int>> adj; //adj[i] là danh sách lưu các đỉnh kề của i
	adj.resize(n + 1);
	adj[1].push_back(3);
	adj[1].push_back(6);
	adj[3].push_back(4);
	adj[3].push_back(7);
	adj[6].push_back(2);
	adj[6].push_back(3);
	adj[6].push_back(4);
	adj[4].push_back(5);
	adj[4].push_back(7);
	adj[2].push_back(4);
	adj[2].push_back(5);
	dfs(adj);
	}

view raw DFS.cpp hosted with ❤ by GitHub

Kết quả: 1 3 4 5 7 6 2

LỜI KẾT

Trên đây mình đã chia sẻ những hiểu biết của mình về DFS. Nếu có gì sai sót các bạn có thể để lại comment ở bên dưới để mình chỉnh sửa. Cảm ơn các bạn đã đọc bài viết !

Đánh Giá Bài Viết: