7-Laboratoriya jumısı. Tema : Shuqırlıq boyınsha izlew algoritmı (dfs)

7-Laboratoriya jumısı.
Tema :Shuqırlıq boyınsha izlew algoritmı (DFS).
Shuqırlıq boyınsha izlew (anglichan Depth-first search, DFS) graflar teoriyasınıń eń áhmiyetli algoritmlarınan biri. Shuqırlıq boyınsha izlew algoritmı strategiyası onıń atına uyqas túrde grafta shuqırlıq boyınsha qansha barıw múmkin bolsa sonsha júredi, jol qolmaǵanǵa shekem. Algoritm rekursiv kóriniste boladı : qaralıp atırǵan ushtan shıǵıwshı barlıq ushlardi kórip shıǵamız. Eger bul qır ele kórilmegen ushqa alıp barsa, izlew sol kórilmegen ush arqalı dawam ettiriledi hám oǵan qońsılas bolǵan ushlar kórip shıǵıladı. Eger kórilgen ushtan shıǵıwshı hám ele kórilmegen uchqa alıp baratuǵın qır qolmasa ol halda keyin qaytıw júz beredi. Kórilgen ushqa qaysı ush arqalı kelgen bolsa tap sol uchqa qaytarıladı hám ol arqalı qalǵan qırlar kóriliwi dawam ettiriledi. Aqir aqıbette dáslep izlew baslanǵan ushqa qaytıp keledi hám odan da shıǵıwda berilgen graf bólegi arqalı tolıq ótip bolinǵan boladı. Eger bunnan keyin kórilmegen qandayda bir ush bolsa izlewdi sol ush arqalı dawam ettiriw kerek.
B
1

2

4

5

3

6
ul anıq mısalda kórip shıǵayıq, bizge tómendegishe graf berilgen:

Bul grafni shuqırlıq boyınsha izlew tártibinde ótip shıǵamız, onıń ushın belgilewler kiriteyik:

• 
  Házir biz turǵan úsh.
  

− Kelilgen (kórilgen) biraq ele aktiv ush, yaǵnıy odan ele artqa qaytilmagan.

−Ele kórilmegen ush

−O

dan shiǵip ketilgen ush.



−Házir qaralıp atńrǵan qir

Grafti shuqırlıq boyınsha izlewdi 1-ushtan baslaymız hám qońsılaslardı nomerleri kishi tártipte kórip shıǵamız. Qırlardı qanday tártipte kóriwdiń áhmiyeti joq.

1. 
   1-ushtan baslaymız. Dáslep ekinshi ush penen baylanıstıratuǵın qır arqalı ótemiz:
   

4

4

4

4

2) 2-ushten shıǵıwshı ush joq, sol sebepli odan keyin basıp yaǵnıy 1-uchga qaytamız.

3) 1-ushtan shıǵıwshı qır arqalı 3-uchqa ótemiz.

4) 3 - ushten 4-uchqa ótemiz:



5) 4 - ushten 2-uchqa ótetuǵın qırdı qaraymız, lekin 2-ush qashannan berli kórilgen, sol sebepli ol boyınsha ótpeymiz hám keyin basıp qaytamız:

6) 3-uch dan navbatdagi qirra orqali 5 uchga o’tamiz:



7) 5-uchdan chiquvchi va 4-uchga olib boruvchii qirrani qaraymiz, lekin 4-uch allaqachon ko’rilgan.




Natijada barcha uchlar va barcha qirralar ko’rib chiqiladi. Demak algoritmning usumiy ishlash vaqti O(n+m). Bu yerda n – uchlar soni, m – qirralar soni.