Simple DFS (Tìm kiếm theo chiều sâu)

DFS:


#include <iostream>
#define MAX 100
using namespace std;

int Array[MAX][MAX] = {
{0, 2, 1, 0, 0, 3},
{2, 0, 0, 0, 0, 5},
{1, 0, 0, 1, 3, 0},
{0, 0, 1, 0, 2, 0},
{0, 0, 3, 2, 0, 3},
{3, 5, 0, 0, 3, 0}
};
int V = 6;
int TIME = 0;
int color[MAX], times[MAX], back[MAX];

void Visit(int u)
{
color[u] = 1;
TIME++;
times[u] = TIME;
for(int v = 0; v < V; v++){
if(Array[u][v] != 0 && color[v] == 0){
back[v] = u;
times[v] = times[u] + 1;
Visit(v);
}
}
color[u] = 2;
}

void DFS()
{
for(int i=0; i<V; i++){
color[i] = 0;
back[i] = times[i] = -1;
}
for(int i=0; i<V; i++){
if(color[i] == 0){
Visit(i);
}
}
}

void PrintPath(int start, int finish)
{
if(start == finish){
cout << finish << " ";
}
else{
if(back[finish] == -1){
cout << "Khong co duong di \n";
}
else{
PrintPath(start, back[finish]);
cout << finish << " ";
}
}
}

int main()
{
int start, finish;
cout << "Nhap dinh bat dau: ";
cin >> start;
cout << "Nhap dinh ket thuc: ";
cin >> finish;
DFS();
PrintPath(start, finish);

/*
Input:
- start = 0, finish = 5
Output:
0 1 5
*/

return 0;
}

Advertisements

One thought on “Simple DFS (Tìm kiếm theo chiều sâu)

  1. Pingback: Artificial intelligence | David Ng

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s