برنامه جستجوی سطحی ( bfs ) به کمک صف

[parvin_nik11]

کسی این برنامه رو داره یا اینکه کتابی رو که اینو داشته باشه می شناسین؟

[max_15s]

اول یه ماتریس مجاورت برای گراف می گیری می ریزی توی g

بعد یه آرایه visited تعیین می کنی که هر وقت با گره ای ملاقات کردی مقدار متناظر با اون گره رو یک می کنی



یک گره رو انتخاب می کنی ( مثلا اینجا با گره صفر شروع کرده) و اون رو ملاقات می کنی و در صف می گذاری و تا زمانی که صف خالی بشه (front==rear) از صف گره بر میداری و تمام گره هایی که با اون در ارتباط هستند (از روی ماتریس مجاورت) رو به شرطی که ملاقاتشون نکرده باشی در صف می گذاری

برای جستجو یا هر چیز دیگه می تونی شرط جستجو رو توی قسمت اضافه کردن گره ها به صف قرار بدی که اینجا گره اول رو در نظر نمی گیره (البته می تونی ویزیتد اول رو یک نکنی تا دو باره خونه اول رو هم چک کنه ) ویا می تونی هنگام خوندن گره ها از صف شرط رو چک کنی (علامت گذاشتم کجا)



برای درخت ها هم می تونی توی کتاب ساختمان داده پیدا کنی ولی خلاصه اینکه به جای عضو فرزندان گره رو توی صف می گذاری





int g[100][100];
int visited[100];
int q[100];
int front=-1, rear=-1,n,k;

visited[0] = 1;
q[++rear] = 0;
while( front != rear){
k = q[++front];
//here <- Controls conditional branching.
for(int i = 0; i < n; i++)
if(g[k][i] == 1)
if(visited[i] == 0){
visited[i] = 1;
q[++rear] = i;
}
}

[hamhik]

کتاب درس و کنکور کارشناسی ارشد ساختمان داده نوشته آقای مقسمی