Граф - 2 Нэвтрэлт

За анхан шатны хүмүүст Граф - 1 пост тусалсан боловуу. Одоо графын хамгийн суурь техник, мөн хамгийн хүчтэй 2 зүйлийг үзнэ. Түвшний нэвтрэлт, Гүний нэвтрэлт.
Энэ удаагийхаа постоор Түвшний нэлтрэлтийг тайлбарлана.

Түвшний Нэвтрэлт (BFS):

Бидэнд дурын граф өгөгдсөн байгаа, мэдээж компьютертээ дүрсэлцэн байгаа. Тэгвэл графын Үндэс буюу ямар нэгэн оройг Графын анхны 1-р түвшин гэж үзээд Графаа доош зурсан мэтээр дүрслэе. Тэгвэл 2-р түвшин нь 1-р түвшний оройнуудын хөрш оройнууд, 3-р түвшин 2-р түвшин дэх оройнуудын хөрш оройнууд болно. Тэгвэл Түвшний нэвтрэлт нь энэ үүсгэсэн түвшин болгон дээр өөрийн боловсруулалтаа хийхийг хэлж байгаа юм.

Дээрх Графын хувьд

1-р түвшинд 1 дугаартай орой,

2-р түвшинд 2, 3, 4 дугаартай оройнууд,

3-р түвшинд 5, 6, 7, 8 дугаартай оройнууд,

4-р түвшинд 9, 10, 11, 12 дугаартай оройнууд байна.

Одоо Түвшний нэвтрэлт нийх алгоритмаа тайлбайрлая:
Энд би Дараалал гэдэг үгийг хэрэглэх ба Дараалал гэдэгт зүгээр массив ч байдаг юмуу, нэг тийм тоонууд хадгалах өгөгдөлийн бүтэц байгаа гээд ойлгоорой.

1. Дараалалд Графын 1-р түвшний оройг хий.

2. Дарааллын хамгийн эхний элементийг С гэе, мөн дарааллаасаа энэ С оройгоо хасна,

- Өмнө нь очоогүй, С-н бүх хөрш оройнуудыг Дараалалдаа араас нь нэмнэ.

3. Хэрэв дараалал хоосон байвал Түвшний нэвтрэлт нийгдэж дууссан,

4. Хэрэв дараалал хоосон биш байвал 2-р алхамаас дахин хий.

За ер нь хар үгээр шууд хэлвэл, Дараалалд тухайн түвшиндэх бүх оройн бүх хөршүүдийг хадгалаад, уг түвшний оройгоо дарааллаас хасаад яваад байх нь байна. Мэдээж орой болгоноо очсон бол очсон гэж тэмдэглэж явах ёстой. Доорх зурагт үзүүлснээр, хараар очсон оройгоо тэмдэглээд, саарлаар Дараалалд нэмэх оройнуудаа бэлдэж байна.

Дараалал гээд байгаа зүйл маань дараах үйлдлийг хийдэг байх хэрэгтэй.

Элемент нэмдэг (араас нь)

Элемент хасдаг (хамгийн урд байгаа элементийг хасна)

Тэгвэл энэ Дарааллыг массив төрлөөр хийвэл яах вэ?

Массив-д элемент нэмэх үйлдэл O(N)-д, за яахав бидэнд нэмэх үйлдэлийг Дарааллын араас нь нэмээд явах болохоор O(1)-д гэсэн үг.

Массиваас элемент хасах үйлдэл O(N)-д. N орой бүр дээр элемент хасах үйлдлээ O(N)-д хийх юм бол Түвшний Нэвтрэлтийг O(N^2)-д хийхнээ.

Одоо арай өөр өгөгдлийн бүтэц сонирхоё:

Дараалал (Queue):

Queue өгөгдлийн бүтэцийг нэг тийм машин явдаг хонгилтой зүйрлдээ!. Хонгилруу хамгийн эхэнд орсон машин хамгийн эхэнд л нөгөө талаар гарч ирдэг. Энэ яг л тийм зүйл хийдэг өгөгдлийн бүтэц. Тэгэхээр жишээ нь 3, 5, 6 гэсэн 3-н тоог Queue-рүү хийхэд хэзээ ч 5 гэсэн элементрүү хандуулж чадахгүй, Queue-н хийж чаддаг зүйл бол:

Элемент нэмэх O(1)

Элемент хасах (хамгийн урд байгаа элементийг хасах) O(1)

Хэмгийн урд байгаа элементийг авах O(1)

За тэгэхээр яг бидэнд хэрэгтэй өгөгдлийн бүтэц мөн байна. Queue-н тусламжтайгаар бид Түвшний нэвтрэлтээ O(N)-д хэрэгжүүлж чадахнээ.

Одоогийн бараг бүх програмчлалын хэлнүүд Queue өөр бусад хэрэгтэй өгөгдлийн бүтцүүдийг шууд ашиглахаар хэрэгжүүлээд сан нээгээд өгцөн байгаа учир Queue мэтийн өгөгдлийн бүтцүүдийг хэрэгжүүлэхэд санаа зовох хэрэггүй(Гэхдээ сонирхож, өөрөө бичиж үзэх л хэрэгтэй).

C++ хэл дээ queue сан байгаа.

Жишээ бодлого: N оройтой, M ирмэгтэй чиглэлгүй, жингүй, цикл агуулаагүй граф өгөгдөв. A оройгоос тодорхой тооны орой дамжин В орой руу хүрч чадах эсэхийг тогтоо?
А юмуу, В-гээс түвшний нэвтрэлт хийхэд бодогдоно.

Бодолт:

/*
input: 
      N<=100 M<=100
      1. x y
      . ..
      n. x y
      a b
output: YES or NO
*/
/*
input:
      5 3
      1 2
      2 3
      4 2
      1 5
output:
       NO
input:
      4 3
      1 2
      2 3
      3 4
      1 4
output:
       YES
*/
#include<cstdio>
#include<queue>
#include<vector>
#define Max 101
using namespace std;
vector<int>v[Max];
bool visited[Max];//i-r oroi deer ochson esehiig temdeglene
queue<int>q;//daraallaa zarlaj baina, queue<TORORL>NER;
int n, m, a, b;
int main(int argc, char *argv[]) {
   scanf("%d%d", &n, &m);
   while(m--){
       int x, y;
       scanf("%d%d", &x, &y);
       x--,--y;
       v[x].push_back(y);
       v[y].push_back(x);
   }
   scanf("%d%d", &a, &b);
   a--,--b;
   q.push(a);// Daraalald element nemj baina
   while(q.size()){// end herev daraalal hooson bish baival TRUE, ugui bol FALSE butsaadag
       int sz = q.size();
       //end tuvshin yavj baigaa
       while(sz--){
           int temp = q.front();//daraalliin ehnii gishuund handaj baina O(1)
           visited[temp]=1;//temp oroig ashiglatsan gej temdeglej baina
           q.pop();//daraallaas element hasaj baina O(1)
           for(int i=0; i<v[temp].size(); i++)//temp oroin horshuudiig avah gej bn
               if(!visited[ v[temp][i] ])//medeej temp-n horsh oroi deer zochloogui baih yostoi
                   q.push(v[temp][i]);// daraalal element nemj baina O(1)
       }
   }
   if(visited[b])printf("YES\n");
   else printf("NO\n");
system("pause");
return 0;
}

За асуух юмаа доор бичээд асуугаарай. Хэрэв ойлгосон бол дээрх бодлогыг өргөтгөж, А В орой холбогдсон бол хоорондох зайг олоорой?