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ị.