Simple BFS (Tìm kiếm theo chiều rộng)

BFS:


#include <iostream>
#include <queue>
#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;

// khai bao cac mang can thiet
int color[MAX], back[MAX];
queue<int> qlist;

void PrintPath(int u, int v, int back[])
{
if(u == v){
cout << v << " ";
}
else{
// dua vao nut cha de tim duong di ngan nhat.
PrintPath(u, back[v], back);
cout << v << " ";
}
}

void BFS(int start, int finish)
{
//khoi tao gia tri cho cac phan tu trong 2 mang color[], back[].
for(int i=0; i<V; i++){
// color = 0: chua di qua lan nao.
// color = 1: da di qua 1 lan.
// color = 2: tat ca dinh ke da duoc danh dau.
color[i] = 0;
back[i] = -1;
}
// bat dau tai dinh start
color[start] = 1;
qlist.push(start); // them start vao hang doi
while(!qlist.empty()){ // kiem tra neu queue khac rong
int u = qlist.front(); // lay gia tri phan tu dau tien trong queue
qlist.pop(); // bo ra phan tu dau tien
// tim dinh ke chua di qua lan nao
for(int v=0; v<V; v++){
if(Array[u][v] != 0 && color[v] == 0){
color[u] = 1;
back[v] = u; // luu lai nut cha cua dinh v
qlist.push(v); // them dinh v vao queue
}
}
// da duyet het dinh ke cua dinh u
color[u] = 2;
}
PrintPath(start, finish, back); // in ket qua.
}

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

return 0;
}

Advertisements

One thought on “Simple BFS (Tìm kiếm theo chiều rộng)

  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