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

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

Posted By 1 year 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 থেকে প্রতিটি নোড এর দূরত্ব পাবো।

Blog Topics
  • PHP (php: Hypertext preprocessor)

    8 Article
  • Agile

    2 Article
  • Freelancing

    3 Article
  • JavaScript

    7 Article
  • AngularJs

    1 Article
  • Programming Language C

    22 Article
  • Object Oriented Programming(C++)

    1 Article
  • Algorithm Design

    14 Article
  • Subject

    Python

    682 Article
  • Computer

    756 Article
  • Subject

    Technology Tips & Tricks

    3 Article