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

DFS সিবলিং ভারটেক্সের আগে চাইল্ড ভারটেক্সগুলো ভিজিট করে; অর্থাৎ, এটি ব্রেডথ এক্সপ্লোর করার আগে যেকোনো নির্দিষ্ট পাথের ডেপথ ট্রাভার্স করে। এই অ্যালগরিদম বাস্তবായন করার সময় সাধারণত একটি স্ট্যাক (প্রোগ্রামের কল স্ট্যাক রিকারসন মাধ্যমে) ব্যবহার করা হয়।

DFS কীভাবে কাজ করে সেটি নিচে দেওয়া হলো:

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

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

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

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

উদাহরণ

DFS(node) {
    // একটি স্ট্যাক তৈরি করুন এবং আমাদের ইনিশিয়াল নোডটি সেটিতে যোগ করুন
    let s = new Stack(this.nodes.length);
    let explored = new Set();
    s.push(node);
    // প্রথম নোডকে এক্সপ্লোরড মার্ক করুন
    explored.add(node);
    // আমরা আমাদের স্ট্যাক খালি না হওয়া পর্যন্ত চালিয়ে যাব
    while (!s.isEmpty()) {
        let t = s.pop();
        // স্ট্যাক থেকে বের হওয়া প্রতিটি এলিমেন্ট লগ করুন
        console.log(t);
        // ১. edges অবজেক্টে, আমরা সেসে নোডগুলো খুঁজব যেগুলো এই নোডের সাথে সরাসরি কানেক্টেড।
        // ২. আমরা যে নোডগুলোর ইতিমধ্যে এক্সপ্লোর করা হয়েছে সেগুলো ফিল্টার আউট করব।
        // ৩. তারপর প্রতিটি আনএক্সপ্লোরড নোডকে এক্সপ্লোরড মার্ক করব এবং স্ট্যাকে পুশ করব।
        this.edges[t]
        .filter(n => !explored.has(n))
        .forEach(n => {
            explored.add(n);
            s.push(n);
        });
    }
}

খুব সহজ ছিল। আমরা সত্যিকারের কিউকে স্ট্যাক দিয়ে রিপ্লেস করলাম এবং বাড়ি, DFS পেয়ে গেলাম। এই দুটির মধ্যে সেটাই একমাত্র পার্থক্য। DFS রিকারসন দিয়েও বাস্তবায়ন করা যায়। কিন্তু এই কেসে সেটি এড়ানো ভালো কারণ বড় গ্রাফ মানে কল স্ট্যাক ট্র্যাক রাখতে এক্সট্রা মেমোরি লাগবে।

আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:

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.DFS("A");

আউটপুট

এটি নিচের আউটপুট দেবে।

A D E F B G C