জাভাস্ক্রিপ্টে ব্রেডথ-প্রথম অনুসন্ধান ট্রাভার্সাল

BFS শিশু শীর্ষবিন্দুগুলি দেখার আগে প্রতিবেশী শীর্ষস্থানগুলি পরিদর্শন করে এবং অনুসন্ধান প্রক্রিয়ায় একটি সারি ব্যবহার করা হয়৷ একটি BFS কিভাবে কাজ করে তা নিচে দেওয়া হল -

• সংলগ্ন অপ্রদর্শিত শীর্ষবিন্দুতে যান। এটি পরিদর্শন হিসাবে চিহ্নিত করুন। এটি প্রদর্শন করুন। এটি একটি সারিতে ঢোকান৷
• কোন সন্নিহিত শীর্ষবিন্দু পাওয়া না গেলে, সারি থেকে প্রথম শীর্ষটি সরান৷
• সারি খালি না হওয়া পর্যন্ত নিয়ম 1 এবং নিয়ম 2 পুনরাবৃত্তি করুন৷

আসুন BFS ট্রাভার্সাল কিভাবে কাজ করে তার একটি দৃষ্টান্ত দেখি:

ধাপ	Traversal	বিবরণ
1	৷	সারিটি শুরু করুন৷
2	৷	আমরা S পরিদর্শন করে শুরু করি (স্টার্টিং নোড) এবং এটিকে পরিদর্শন করা হিসাবে চিহ্নিত করুন।
3	৷	তারপর আমরা S থেকে একটি অনাদর্শিত সংলগ্ন নোড দেখতে পাই এই উদাহরণে, আমাদের তিনটি নোড আছে কিন্তু বর্ণানুক্রমিকভাবে আমরা A, বেছে নিই এটিকে পরিদর্শন করা হিসাবে চিহ্নিত করুন এবং সারিবদ্ধ করুন৷
4	৷	এরপর, S থেকে অনাভিজিট সংলগ্ন নোড হল B . আমরা এটিকে পরিদর্শন করা হিসাবে চিহ্নিত করি এবং সারিবদ্ধ করি৷
5	৷	এরপর, S থেকে অনাভিজিট সংলগ্ন নোড হল C . আমরা এটিকে পরিদর্শন করা হিসাবে চিহ্নিত করি এবং সারিবদ্ধ করি৷
6	৷	এখন, S কোন অদর্শিত সংলগ্ন নোড ছাড়া বাকি আছে. সুতরাং, আমরা সারিবদ্ধ করি এবং A খুঁজে পাই .
7	৷	থেকে A আমাদের D আছে একটি unvisited সংলগ্ন নোড হিসাবে. আমরা এটিকে পরিদর্শন করা হিসাবে চিহ্নিত করি এবং সারিবদ্ধ করি৷

এই পর্যায়ে, আমাদের কাছে কোন অচিহ্নিত (অভিজিট করা) নোড নেই। কিন্তু অ্যালগরিদম অনুযায়ী আমরা সমস্ত অনাবিষ্কৃত নোডগুলি পাওয়ার জন্য ডিকিউ করতে থাকি। যখন সারি খালি হয়ে যায়, তখন প্রোগ্রামটি শেষ হয়৷

চলুন দেখি কিভাবে আমরা জাভাস্ক্রিপ্টে এটি বাস্তবায়ন করতে পারি।

উদাহরণ

BFS(node) {
   // Create a Queue and add our initial node in it
   let q = new Queue(this.nodes.length);
   let explored = new Set();
   q.enqueue(node);

   // Mark the first node as explored explored.
   add(node);

   // We'll continue till our queue gets empty
   while (!q.isEmpty()) {
      let t = q.dequeue();

      // Log every element that comes out of the Queue
      console.log(t);

      // 1. In the edges object, we search for nodes this node is directly connected to.
      // 2. We filter out the nodes that have already been explored.
      // 3. Then we mark each unexplored node as explored and add it to the queue.
      this.edges[t]
      .filter(n => !explored.has(n))
      .forEach(n => {
         explored.add(n);
         q.enqueue(n);
      });
   }
}

আপনি −

উদাহরণ

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.BFS("A");

আউটপুট

এটি −

A
C
B
D
G
E
F