Tìm kiếm theo chiều sâu
Bách khoa toàn thư mở Wikipedia
Tìm kiếm theo chiều sâu (tiếng Anh: depth-first search) là một thuật toán tìm kiếm trên cây.
[sửa] Giả mã
Cài đặt thuật toán Tìm kiếm theo chiều sâu DFS trên cơ sở Ngôn ngữ lập trình C++:
bool *unchecked = new bool[số đỉnh của đồ thị];
for(int i = 0; i < số đỉnh của đồ thị; i++)
unchecked[i] = true;
connectedSpaceDFS(bool *&unchecked, int index)
{
if(index > 0 && index <số đỉnh của đồ thị)
{
unchecked[index-1] = false;
for(int i = 0; i < số đỉnh của đồ thị; i++)
if(matrix[index-1][i] != 0)
if(unchecked[i] == true)
connectedSpaceDFS(unchecked, i+1);
}
}
Bài toán sử dụng phép đệ quy trong đó matrix là ma trận kề tương ứng của đồ thị.
