Thứ Tư, 30 Tháng Mười Một 2022
Trang chủLập trìnhCTDL & Thuật toánGiải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)

Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)

DANH SÁCH BÀI VIẾT
Tìm hiểu thuật toán Quy hoạch động
Tìm hiểu về Hàm đệ quy
Thuật toán tìm kiếm nhị
Tìm hiểu về Thuật toán quay lui (Backtracking)
Tìm hiểu thuật toán Loang
Tìm hiểu thuật toán chia để trị
Tìm hiểu thuật toán tham lam trong lập trình
Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)
Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search)
Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)

Bài viết này chúng ta sẽ tìm hiểu về giải thuật tìm kiếm theo chiều sâu DFS, tiếp tục theo dõi các bài viết sau mình sẽ có các bài toán áp dụng giải thuật này như duyệt đồ thị, duyệt cây, tìm đường đi ngắn nhất, dài nhất trên cây.

XÊM THÊM: Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search)

Giải thuật duyệt chiều sâu DFS

Giải thuật tìm kiếm theo chiều sâu (Depth First Search – viết tắt là DFS), còn được gọi là giải thuật tìm kiếm ưu tiên chiều sâu, là giải thuật duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.

Xuất phát từ một đỉnh bất kì, nếu trên dữ liệu cây ta sẽ duyệt xuất phát từ nút gốc(root), từ đỉnh này ta duyệt tìm kiếm đỉnh con có đường đi với đỉnh đó(trên cây thì là các nút con), khi tìm được đỉnh con giải thuật ngay lập tức chuyển qua đỉnh con đó và đánh dấu đỉnh đã được duyệt qua, có thể sử dụng mảng nhưng tối ưu nhất là sử dụng stack để đánh dấu, giải thuật tiếp tục thực hiện lặp cho tới khi nút đó không còn nút con nào. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước và tiếp tục thực hiện tìm kiếm các đỉnh con còn lại của đỉnh đó.

Nếu thực hiện trên cây không nhất thiết là cần phải đánh dấu nút đã duyệt qua, vì mỗi nút cha sẽ có các nút con theo một quy luật rồi. Trên đồ thị thì nó liên kết một cách lộn xộn, vì thế các đỉnh con sẽ có thể lại liên kết lại tới các đỉnh đã được duyệt qua trước đó, việc đánh dấu để tránh duyệt qua một đỉnh nhiều lần.

Mình vẽ hình mình họa duyệt đồ thị theo chiều sâu như sau:

Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)

Trong hình minh họa trên, giải thuật tìm kiếm theo chiều sâu đầu tiên duyệt từ đỉnh A tới B tới D tới C……sau đó C đường đi tới đỉnh A nhưng vì A là đỉnh gốc tức là đỉnh đã được duyệt qua, vì thế giải thuật sẽ duyệt tới đỉnh F.

C đã hết đường đi, quay lại 1 bước trước đó tức là đỉnh D, tiếp tục thực hiện ta tìm thấy đường đi từ D tới E…..Tất cả các đỉnh đã được duyệt, lúc này giải thuật kết thúc.

Duyệt trên cây cũng tương tự như vậy, mình có thể vẽ lại hình minh họa như sau:

Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)

Tóm cái váy lại, duyệt theo chiều sâu nó giống như việc ta đi trên một con đường mà chúng ta bị mù đường vậy á. Cứ gặp đường rẽ nào trước là ta sẽ đi đường rẽ đó trước, đi đến lúc nào đường rẽ đó hết đường thì ta quay lại chỗ rẽ và đi con đường kia.

Minh họa giải thuật

Lý thuyết là như vậy, bây giờ chúng ta cùng làm các bài tập cho giải thuật DFS.

Mình sẽ làm 2 bài toán là duyệt đồ thị và tìm kiếm đường đi dài nhất từ 1 đỉnh u tới một đỉnh v.

Trong 2 bài tập dưới đây mình sử dụng cách nhập đồ thị là nhập vào ma trận đồ thị, có thể bạn quên ma trận đồ thị là như thế nào thì đọc lại lý thuyết hoặc xem hình minh họa dưới đây để nhớ lại nhé.

Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search)

Duyệt đồ thị giải thuật DFS

Với vị dụ này chỉ đơn giản là chúng ta duyệt và in ra thứ tự duyệt của các đỉnh sử dụng giải thuật DFS.

#include <iostream>
#include <algorithm>
using namespace std;
bool dd[1000]; //Mảng đánh dấu đỉnh ma trận
int dem=1, n;
int a[1000][1000];  //Ma trận đồ thị
int b[1000];  //Mảng để lưu thứ tự duyệt đồ thị


//Hàm duyệt đồ thị sử dụng giải thuật DFS
void duyetDoThi(int i)
{
//Vòng for để duyệt qua tất cả các đỉnh
   for(int j=1;j<=n;j++) 
    {
        if(a[i][j] != 0 && dd[j]==0)//Neus có đường đi từ đỉnh i tới đỉnh j và đỉnh j chưa đươc duyệt
        {
        	dd[j ]= 1; //Đánh dấu đỉnh j được duyệt
        	b[dem++] = j; //Cho đỉnh j vào mảng b để lát nữa ta in ra thứ tự duyệt
            duyetDoThi(j); //đệ quy với đỉnh tiếp theo
        }
    }
}


//Hàm in thứ tự duyệt đồ thị
void inDoThi(){
	for(int i = 0;i<n;i++) cout<<b[i]<<" ";
}

int main()
{
  cout<<"nhap so dinh: "; cin>>n;
    cout<<"Nhap ma tran do thi: \n";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
             cin>>a[i][j];
    cout<<"Ma tran do thi: \n";
    for(int i=1;i<=n;i++)
    {
     for(int j=1;j<=n;j++)
     cout<<a[i][j]<<"  "; cout<<endl;
    }
    
    
    cout<<"\n\nDuyet do thi: ";
    b[0] = 1; //Lấy đỉnh 1 là đỉnh gốc nên ta gắn b 0 là đỉnh 1 để lát nữa ta in ra thứ tự duyệt đồ thị
    dd[1] = 1;//Đánh dấu đỉnh 1 đã được duyệt
    duyetDoThi(1); //Gọi duyệt đồ thị
	inDoThi();    //in ra thứ tự duyệt đồ thị
}

Tìm đường đi dài nhất trong đồ thị

Với ví dụ này ta sẽ nhập vào ma trận đồ thị, và 2 đỉnh và v. Sau đó tìm đường đi dài nhất từ tới v sử dụng giải thuật DFS kết hợp với thuật toán quay lui(Backtracking).

#include <iostream>
#include <algorithm>
using namespace std;
bool dd[1000], tt = 0; //Mảng đánh dấu tối đa  1000 đỉnh
int dem=1,dem2, n;// dem sử dụng để đếm số bước đi của  đường đi hiện tai, dem2 để lưu số bước của đường đi dài nhát trước đó
int a[1000][1000]; //Mảng để lưu mảng đồ thị
int b[1000], c[1000]; //Mảng c để lưu đường đi dài nhất tìm được tạm thời, mảng b sử dụng trong qua trình tìm 1 đường đi
int u,v; //2 đỉnh u và v
 
//Hàm tìm đường đi dài nhất
void duongdidainhat(int i)
{
    dd[i]=1; //Đánh dấu đỉnh i đã đi qua
 
//Nếu đinh i chính bằng v  tức là từ đỉnh u ta đã đi tới v
    if(i==v)
    {
        tt=1;
    //Phần này chính là vét cạn đó, ta tìm tất cả đường đi rồi so sánh lấy được đường đi dài nhất
      //Nếu đường đi hiện tại tìm được lớn hơn đường đi dài nhất ban đầu
        if(dem > dem2)
        {
          //Gắn đường đi dài nhất bằng đường đi tìm được, gắn lại biến đếm
            for(int j=0;j<dem;j++) c[j]=b[j]; dem2 = dem;
        }
    }
//Nếu chưa tới đỉnh v ta tiếp tục duyệt các đỉnh chưa đi qua
    else for(int j=0;j<n;j++) 
    {
        if(a[i][j] != 0 && dd[j]==0)//Kiểm tra xem giữa 2 đỉnh có tồn tại đường đi không, và đỉnh đó đã đi qua trước đó chưa
        {
            b[dem++] = j; //Tăng biến đếm bước đi lên 1, đồng thời gắn đường đi tại đỉnh j
            duongdidainhat(j); //duyệt đỉnh j tiếp tục tìm kiếm đường đi
            dem--; dd[j]=0;//Thoát khỏi hàm quay lui, lúc này hàm quay lui sẽ lùi về 1 bước phía trước, và tìm kiếm 1 đường đi khác có thể sảy ra.....ta trừ đi biến đếm 1 đơn vị và gắn lại đỉnh đó là chưa đi qua
        }
    }
}
 
//Hàm hiển thị đường đi
void induongdi()
{
    for(int i = 0;i<dem2; i++) cout<<c[i]<<" ";
}
int main()
{
  cout<<"nhap so dinh: "; cin>>n;
    cout<<"Nhap ma tran do thi: \n";
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
             cin>>a[i][j];
    cout<<"Ma tran do thi: \n";
    for(int i=0;i<n;i++)
    {
     for(int j=0;j<n;j++)
     cout<<a[i][j]<<"  "; cout<<endl;
    }
    cout<<"Nhap dinh u "; cin>>u;
    cout<<"Nhap dinh v "; cin>>v;
    b[0]=u;
    duongdidainhat(u);
    if(tt) induongdi(); else cout<<"Kg ton tai duong di tu u toi v";
     
}

Cảm ơn bạn đã đọc bài viết chúc bạn học tốt!

[Xem tất cả bài viết chủ đề C/C++ tại đây]

5 1 Bỏ phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x