BFS-Түвшний нэвтрэлт

Түвшний нэвтрэлт(BFS-Breadth first search) гэх алгоритмын тухай бичих болно. Жишээ бодлого дээр ярилцъя. Бидэнд нэг граф өгөгдсөн байгаа гэж бодъё. Тэгээд нэг хүсэлт байгаа тэр нь хоёр орой өгөгдөх ба энэ хоёр оройн хооронд хамгийн багадаа хэдэн ширхэг оройгоор дамжин очих вэ? гэдгийг олох юм. Бид одоо X гэсэн орой дээр байгаа. Y орой хүрэх хамгийн богино замыг олцгооё. Бид X орой дээр 0 зам туулж ирсэн гэж үзэж болох юм. Мөн энэ оройг 0-р түвшин гэж үзье. Тэгвэл 1 гэсэн түвшинтэй орой гэж ямар оройг хэлэх вэ? Энэ оройнууд бол X оройтой шууд ирмэгээр холбогдсон оройнууд юм. Тэгвэл 1-р түвшинтэй орой дээр 1 гэсэн зам туулж ирнэ. Тэгвэл 2-р түвшин гэдэг нь 1-р түвшний оройтой шууд ирмэгээр холбогдсон оройнууд байх юм. Энэд нэг анхаарах зүйл байгаа нь 1-р түвшинтэй оройнуудтай 0-р түвшний орой холбогдсон байгаа ба бид энэ оройг 2-р түвшин гэж хэлэх нь буруу юм. Тиймээс өмнө нь ирээгүй орой буюу шинэ оройд л түвшний утга өгөх нь зүйтэй. Энэ мэтчилэн бид X орой буюу 0-р түвшнээс Y орой таартал түвшинг нэмсээр байх болно. Ингээд Y орой дээр ирэх үед энэ түвшин нь X оройгоос Y орой хүртэлх хамгийн бага замын урт байх юм. Энгийнээр төсөөлбөл бид графын ирмэгүүдийг хоолой гэж төсөөлье. Тэгвэл бид X оройгоос ус асгасан гэж үзье. Энэ ус нь эхлээд X оройгоос гарсан бүх хоолойгоор урсана. Дараа нь тэр оройнуудаас гарсан хоолойнуудаар урсана. Ямар нэг орой дээр ус анх удаа ирж байгаа бол X оройгоос ирж болох хамгийн бага зам туулж ирсэн гэсэн үг. Харин анх удаа биш бол энэ орой дээр ус аль хэдийнээ ирж амжсан тул энэ явалт нь ашиггүй. Гол санаа нь нэг нэг түвшнээр ахиж байгаад оршино. Кодыг нь хэрхэн бичих вэ? Бид queue гэсэн бүтцийг ашиглан бичнэ(Яагаад vector эсвэл өөр бүтэц биш вэ?). Queue нь хос байх ба эхнийх нь одоо явж байгаа оройг харин дараагийнх нь одоо явж байгаа түвшинг авна. Queue-д хамгийн эхлээд X, 0 гэсэн хосыг нэмж өгнө. Бид queue-ын хамгийн эхний элементийг авах буюу X, 0 гэсэн хосыг авна. Энэ нь X орой дээр хамгийн багадаа 0 гэсэн утгаар ирж чадсан гэж үзэж байгаа тул X оройг ирсэн гэж тэмдэглэнэ. Дахиж энэ оройгоос явах шаардлагагүй(ус урсгах шаардлагагүй. Усаа хэмнэ). Харин дараа нь бид X оройтой шууд ирмэгээр холбогдсон бүх оройг queue-д нэмж өгөх ба нэмэхдээ эхний утга нь тэр орой харин хоёр дахь утга нь 1 байх болно. Учир нь энэ оройнуудын түвшин 1. Ингээд энэ оройгоос бүгд урсаж чадсан. Дараагийн түвшинлүү орох ёстой тул үүнийг queue-ээс хасах хэрэгтэй. Харин дараа нь давталт эхнээсээ эхэлнэ. 1-р түвшинтэй хамгийн эхний орой гарж ирнэ. Энэ оройтой шууд холбогдсон өмнө нь очоогүй бүх оройг 2 гэсэн утгатай хос болгон queue-д нэмнэ. Тэгээд үүнийг хасаад. Дараагийн 1-р түвшний оройруу шилжинэ. Гэх мэт Y оройтой таартал явах юм. Энэ алгоритм нь өгөгдсөн оройгоос бүх холбоотой орой хүртэлх хамгийн богино замыг олж байгаа юм. Доорх код нь энэ хаяг дээр байгаа болно.

1. //Түвшний нэвтрэлт. BFS  
2. #include <queue>  
3. #include <iostream>  
4. using namespace std;  
5.       
6.     int n, m;   // оройн тоо, ирмэгийн тоо  
7.     bool vis[50000];    // ирсэн ирээгүйг хадгалах массив.  
8.     vector<int> adj[50000];   // графын мэдээллийг хадгалах вектор.  
9.     queue< pair<int,int> > q;   // bfs явах queue  
10.   
11. int main() {  
12.     cin >> n >> m;  // орой, ирмэгийн тоонуудыг унших.  
13.   
14.     for(int i = 1; i <= m; i++) {  
15.         int u, v;   // i-р ирмэгийг тодорхойлох 2 орой.  
16.         // u болон v орой холбогддог гэсэн утгатай тул  
17.         cin >> u >> v;  
18.         adj[u].push_back( v );  
19.         adj[v].push_back( u );  
20.     }  
21.     int x, y;   // x-ээс y хүртэл  
22.       
23.     cin >> x >> y;  // хүсэлтээ унших  
24.   
25.     q.push( make_pair( x, 0 ) );    // анх x оройдээр 0 утгаар  
26.   
27.     while( !q.empty() ) {   // хоосон биш л бол үргэлжилнэ.  
28.         int nowU = q.front().first; // одоо явж байгаа орой.  
29.         int nowW = q.front().second;    // одоо явж байгаа оройн түвшин  
30.           
31.         vis[nowU] = 1;  // nowU оройг ирсэн гэж тэмдэглэнэ.  
32.   
33.         if( nowU == y ) {  
34.             // nowU орой нь бидний хайсан Y орой бол энэ хүрээд зогсоно.  
35.             cout << nowW << endl;   // хамгйин бага зардал.  
36.             return 0;   // программыг зогсоож болно гэсэн үг юм.  
37.         }  
38.   
39.         q.pop();    // дараагийн элемэнтээс явах ёстой тул үүнийг устгана.  
40.   
41.         for(int i = 0; i < adj[nowU].size(); i++) {  
42.             int v = adj[nowU][i];   // одоо байгаа оройтой шууд ирмэгээр холбогдсон орой.  
43.             if( !vis[v] ) { // v орой тэмдэглэгдээгүй бол очиж ёстой.  
44.                 q.push( make_pair( v, nowW+1 ) );   // энэ оройдээр одоо байгаа  
45.                                                     // түвшиндээр нэмэх нь 1-ээр ирнэ.  
46.             }  
47.         }  
48.     }  
49.     cout << "Ochih bolomjgui!\n";     // хэрвээ бүрэн зогсоогүй бол очиж   
50.                                     // чадаагүй буюу очих боломжгүй гэсэн үг.  
51.     return 0;  
52. }