BFS(Breadth First Search) Algorithm(Part-2)

Posted By 2 years ago

ধরা যাক এ গ্রাফে 1 কে source node। প্রথম পর্যায়ে যখন এ নোড ভিজিটেড হবে তখন এর colorহবে grey.এবং যখন এর child node গুলো ভিজিটেড হয়নি।তখন Queue তে থাকবে শুধু 1।
এরপর নিম্নের অপারেশন গুলো ঘটবে।

QUEUE: 1

1.distance = 0
1.parent = NULL

এরপর 1 এর child node গুলো ভিজিট হবে।তখন গ্রাফের অবস্থা হবে এরূপ

এবং QUEUE থেকে 1 বের হয়ে এর বাচ্চারা প্রবেশ করবে।প্রত্যেক নোডই তাদের বাচ্চাদের Queue তে প্রবেশ করিয়ে নিজে বের হয়ে যাবে।
এবং parent এ parent এর নাম বসে যাবে।এবং distance এ বসবে এর parent এর distance যোগ ১।
এবং নিম্নের অপারেশন গুলো ঘটবে।

QUEUE: 2,3,4

2.distance = 0 + 1 = 1
2.parent = 1

3.distance = 0 + 1 = 1
3.parent = 1

4.distance = 0 + 1 = 1
4.parent = 1

এরপর 2,3,4 এর child node গুলো ভিজিট হবে।এবং 2,3,4 QUEUE থেকে বের হয়ে যাবে।এবং প্রবেশ করবে 5,6,7,8 নোডগুলো।এক্ষেত্রে 3 এর কোন child node নেই।তাই 3 নোড ও কালো রঙ ধারণ করবে।
এবং নিম্নের অপারেশন গুলো ঘটবে।

QUEUE: 5,6,7,8

5.distance = 1 + 1 = 2
5.parent = 2

6.distance = 1 + 1 = 2
6.parent = 2

7.distance = 1 + 1 = 2
7.parent = 4

8.distance = 1 + 1 = 2
8.parent = 4

অনুরূপ 5,6,7,8 এর child node গুলো ভিজিট হবে। 5,6,7,8 QUEUE থেকে বের হয়ে যাবে।এবং প্রবেশ করবে 9,10,11,12 নোডগুলো।
এবং অপারেশন গুলো হবে নিম্নরূপ।

QUEUE: 9,10,11,12

9.distance = 2 + 1 = 3
9.parent = 5

10.distance = 2 + 1 = 3
10.parent = 5

11.distance = 2 + 1 = 3
11.parent = 7

12.distance = 2 + 1 = 3
12.parent = 7

যেহেতু 9,10,11,12 এর কোন child node নেই।তাই এরা বের হয়ে যাওয়ার পর QUEUE খালি হয়ে যাবে

এবং BFS চালানো শেষ হবে।এবং আমরা source node থেকে প্রতিটি নোড এর দূরত্ব পাবো।