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

#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ị
}

#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";
     
}