{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 if ((graph[st][r]!=0) (!visited[r])) DFS(r); |
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARIBu sahifa navigatsiya:
- {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
- if ((graph[st][r]!=0) (!visited[r])) DFS(r);
28-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.
99
#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);
|
| |
