জাভাস্ক্রিপ্টে ব্রেডথ-ফার্স্ট সার্চ (BFS) ট্রাভারসাল

BFS চাইল্ড ভারটেক্সের আগে নেIGHবর ভারটেক্সগুলো ভিজিট করে, এবং সার্চ প্রসেসে একটি কিউ ব্যবহার করা হয়। BFS কীভাবে কাজ করে সেটি নিচে দেওয়া হলো:

এডজেসেন্ট আনভিজিটেড ভারটেক্স ভিজিট করুন। এটিকে ভিজিটেড মার্ক করুন। ডিসপ্লে করুন। কিউতে ইনসার্ট করুন।
যদি কোনো এডজেসেন্ট ভারটেক্স না পাওয়া যায়, কিউ থেকে প্রথম ভারটেক্স রিমুভ করুন।
নিয়ম ১ এবং ২ পুনরাবৃত্তি করুন যতক্ষণ না কিউ খালি হয়।

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

স্টেপ	ট্রাভারসাল	বর্ণনা
১		কিউ ইনিশিয়ালাইজ করুন।
২		আমরা S (স্টার্টিং নোড) ভিজিট করে শুরু করি এবং এটিকে ভিজিটেড মার্ক করি।
৩		তারপর আমরা S-এর একটি আনভিজিটেড এডজেসেন্ট নোড দেখি। এই উদাহরণে, আমাদের তিনটি নোড আছে কিন্তু আলফাবেটিক্যালি আমরা A-কে বেছে নেই, ভিজিটেড মার্ক করি এবং ইনকিউ করি।
৪		পরবর্তী, S-এর আনভিজিটেড এডজেসেন্ট নোড হলো B। আমরা এটিকে ভিজিটেড মার্ক করি এবং ইনকিউ করি।
৫		পরবর্তী, S-এর আনভিজিটেড এডজেসেন্ট নোড হলো C। আমরা এটিকে ভিজিটেড মার্ক করি এবং ইনকিউ করি।
৬		এখন, S-এর কোনো আনভিজিটেড এডজেসেন্ট নোড নেই। তাই, আমরা ডিকিউ করি এবং A পাই।
৭		A- থেকে আমাদের D আছে একটি আনভিজিটেড এডজেসেন্ট নোড হিসেবে। আমরা এটিকে ভিজিটেড মার্ক করি এবং ইনকিউ করি।

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

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

উদাহরণ

BFS(node) {
    // একটি কিউ তৈরি করুন এবং আমাদের ইনিশিয়াল নোডটি সেটিতে যোগ করুন
    let q = new Queue(this.nodes.length);
    let explored = new Set();
    q.enqueue(node);
    // প্রথম নোডকে এক্সপ্লোরড মার্ক করুন
    explored.add(node);
    // আমরা আমাদের কিউ খালি না হওয়া পর্যন্ত চালিয়ে যাব
    while (!q.isEmpty()) {
        let t = q.dequeue();
        // কিউ থেকে বের হওয়া প্রতিটি এলিমেন্ট লগ করুন
        console.log(t);
        // ১. edges অবজেক্টে, আমরা সেসে নোডগুলো খুঁজব যেগুলো এই নোডের সাথে সরাসরি কানেক্টেড।
        // ২. আমরা যে নোডগুলোর ইতিমধ্যে এক্সপ্লোর করা হয়েছে সেগুলো ফিল্টার আউট করব।
        // ৩. তারপর প্রতিটি আনএক্সপ্লোরড নোডকে এক্সপ্লোরড মার্ক করব এবং কিউতে যোগ করব।
        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