|
Grafda oʻtish boʻyi boʻyicha qidiruv (DFS) algoritmi
|
| bet | 6/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MIGrafda oʻtish boʻyi boʻyicha qidiruv (DFS) algoritmi
Grafda oʻtish boʻyi boʻyicha qidiruv (DFS) - bu graf uchlaridan oʻtishning rekursiv algoritmi. Agar boʻyi boʻyicha birinchi qidirish usuli nosimmetrik tarzda bajarilgan boʻlsa (grafning uchlari darajalar boʻyicha koʻrib chiqilgan boʻlsa), unda bu usul iloji boricha chuqurroq harakat qilishni oʻz ichiga oladi. Keyingi rivojlanishning mumkin emasligi shundan iboratki, keyingi qadam harakatlanishning bir nechta variantiga ega boʻlgan (ulardan biri toʻliq oʻrganib chiqilgan), ilgari tashrif buyurgan uch oxirgisiga oʻtish boʻladi.
Algoritm qanday ishlashini aniq bir misol yordamida koʻrib chiqamiz. Quyidagi yoʻnaltirilmagan bogʻlangan grafda jami 5 ta uch mavjud. Avval siz boshlangʻich uchni tanlashingiz kerak. Qaysi uch tanlangan boʻlsa ham, har qanday holatda ham graf toʻliq oʻrganib chiqiladi, chunki yuqorida aytib oʻtilganidek, bu bitta yoʻnaltirilmagan bogʻlangan graf. Oʻtish 1 tugundan boshlasin, u holda qarab chiqilgan tugunlar ketma-ketligi tartibi quyidagicha boʻladi: 1 2 3 5 4. Agar ijro, masalan, 3 tugundan boshlangan boʻlsa, u holda oʻtish tartibi boshqacha boʻladi: 3 2 1 5 4.
DFS algoritmi rekursiyaga asoslangan, ya‘ni oʻtish funksiyasi oʻzini bajarilayotganda chaqiradi, bu esa kodni umuman ixcham qiladi.
Algoritmning psevdokodi quyidagicha
11-rasm. BFS algoritmi jarayonida graf uchlarini koʻrish
DFS funksiya sarlavhasi (st)
Chiqish (st)
visited[st] ← tashrif buyurgan;
r = 1 uchun n gacha
Agar (graph[st, r] ≠ 0) va (visited[r] tashrif buyurilmagan) boʻlsa, u holda DFS (r)
Bu yerda DFS (deep-first search) - bu funksiya nomi. Uning yagona parametri st - dasturning asosiy qismidan argument sifatida uzatiladigan boshlangʻich uchdir. Mantiqiy qiymatlarni qabul qiladigan massivning har bir elementiga oldindan false (yolgʻon, 0) qiymat beriladi, ya‘ni uchlarning har biri dastlab tashrif buyurilmagan deb yoziladi.
Ikki oʻlchovli graph massivi grafning qoʻshnilik matritsasi. Natijalar oxirgi satrda toʻplanishi kerak. Agar qoʻshnilik matritsasining elementi, qandaydir bosqichda, 1 ga teng boʻlsa (0 emas) va matritsaning tekshirilgan ustuni bilan bir xil songa ega boʻlgan uchga tashrif buyurilmagan boʻlsa, unda funksiya rekursiv ravishda takrorlanadi. Aks holda, funksiya rekursiyaning oldingi bosqichiga qaytadi
#include
using namespace std;
const int n=5;
int i, j;
bool *visited=new bool[n];
//qoʻshnilik grafi
int graph[n][n] =
{ {0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0}
};
//boʻyi boʻyicha izlash
void DFS(int st)
{
int r;
cout<visited[st]=true;
for (r=0; r<=n; r++)
if ((graph[st][r]!=0) && (!visited[r]))
DFS(r);
}
int main()
{
int start;
cout<<"Qoʻshnilik matritsasi: “<for(i-0;i{
visited[i]=false;
for(j=0;jcout<<” ”<cout<}
Cout<<”Boshlangʻich uchni kiriting: >> "; cin>>start;
// tashrif buyurilgan uchlar massivi
bool *vis=new bool[n];
cout<<" Oʻtish tartibi: ";
100 DFS(start-1);
delete []visited;
system("pause>>void");
return 0;
}
|
| |
