ব্রেডথ ফার্স্ট সার্চ অ্যালগরিদম – Breadth-first search

আমাদের বাস্তব  জীবনের বেশির ভাগ সমস্যাকে গ্রাফ আকারে রিপ্রেজেন্ট করা যায়। এরপর গ্রাফ সার্চ করে সমস্যার সমাধান করা যায়। গ্রাফ সার্চ করার অনেক গুলো পদ্ধতি রয়েছে। সহজ একটা পদ্ধিতি হচ্ছে ব্রেডথ ফার্স্ট সার্চ। Breadth মানে আমরা ধরব কাছে বা পাশে।

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

ব্রেডথ ফার্স্ট সার্চে গ্রাফের ইনিশিয়াল নড বা রুট নড থেকে আমরা সার্চ শুরু করি। এরপর সার্চ করি হচ্ছে রুট নডের সাথে যে সব নড কানেক্টেড, সেগুলো এভাবে প্রথম লেভেলে সার্চ করি, এরপর দ্বিতীয় লেভেল এভাবে শেষ পর্যন্ত।

ব্রেডথ ফার্স্ট সার্চ করার জন্য Queue নামক ডেটা স্ট্র্যাকচার ব্যবহার করা হয়। কিউ হচ্ছে First In First Out ডেটা স্ট্র্যাকচার। মানে হচ্ছে কিউতে আমরা সবার আগে যে ডেটা ঢুকাবো, ঐটাই প্রথমে বের করব। যেমন টিকেট কাটার লাইন। লাইন বা কিউর সবার আগে যে থাকে, সেই সবার আগে টিকেট কিনে বের হয়ে যায়।

নিচের অ্যানিমেশনটা দেখি, ব্রেডথ ফার্স্ট সার্চ কিভাবে হয়, তার ভিজুয়াল চিত্রঃ

Breadth-first search Traversal:

আমরা ব্রেডথ ফার্স্ট সার্চ এই গ্রাফটা ভ্রমণ করব। এ জন্য প্রথমে আমরা রুট নড দিয়ে শুরু করব। যেমন 1 হচ্ছে আমাদের রুট নড। এটাকে কিউতে ঢুকাবো। তাহলে কিউতে থাকে শুধু 1।

এবার 1 ভিজিট করে এর সাথে কানেক্টেড নড গুলো কিউতে ঢুকাবো। 2,3,4 এবং কিউ থেকে 1 রিমুভ করব। তাহলে কিউতে থাকবে 2,3,4।

কিউর নিয়ম হচ্ছে যে আগে কিউতে ঢুকবে, আমরা তাকে সুযোগ দিব। যেহেতু কিউতে 2 আগে আছে, তাহলে আমরা দুই এর সাথে কানেক্টেড নড গুলোর ভিজিট করব। দুই এর সাথে কানেক্টেড হচ্ছে 1 এবং 5। 1 যেহেতু আমরা একবার ভিজিট করে ফেলছি, তাই আমরা 1 এ আর ভিজিট করব না। সুতরাং আমরা যে সব নড ভিজিট করে ফেলছি, তার লিস্ট রাখতে হচ্ছে। আমরা অ্যারে বা যে কোন লিস্টে ভিজিটেড নড গুলো রাখতে পারি।

আমাদের কিউতে 5 ঢুকাবো এবং কিউ থেকে ২ বের করে দিব। তাহলে আমাদের কিউতে থাকবে 3,4,5।

কিউতে এখন সামনে রয়েছে 3। তাই আমরা তিন এর সাথে যে সব নড কানেক্টেড 3 এর সাথে কানেক্টেড 1,6,7। যেহেতু 1 এর আগে একবার ভিজিট করা হয়েছে, তাই আমরা কিউতে 1 কে ঢুকাবো না। বাকি থাকে 6,7, এগুলো আমরা কিউতে ঢুকাবো। কিউ থেকে 3 বের করে দিব। তাহলে আমাদের কিউতে থাকবে 4,5,6,7।

এবার কিউতে আগে রয়েছে 4। চারের সাথে কানেক্টেড হচ্ছে 1 এবং 8। যেহেতু 1 আমাদের ভিজিটেড লিস্টে রয়েছে, তাই আমরা শুধু 8 কে কিউতে ঢুকাবো এবং 4 কে কিউ থেকে বের করব। এভাবে বাকি নড গুলো ভিজিট করব।

ব্রেডথ ফার্স্ট সার্চ ভ্রমন করার পর যেসব নড আমরা ভিজিট করেছি, সেগুলো হবে আমাদের আউটপুট। যেমন প্রথমে আমরা 1 ভিজিট করেছি, এরপর 2, এরপর 3 … এভাবে 10 পর্যন্ত। তাহলে আমাদের আউটপুট হবে 1,2,3….10 যে নড আগে ভিজিট করেছি, সেটা থাকবে আগে।

ব্রেডথ ফার্স্ট সার্চ এর ব্যবহারঃ অনেক জায়গায় ব্রেডথ ফার্স্ট সার্চ অ্যালগরিদম ব্যবহার করা যায়। আমরা সিম্পল একটা ব্যবহারের কথা চিন্তা করি। যেমন আমরা উপরের গ্রাফটির কথাই চিন্তা করি। আমাদেরকে গ্রাফটি দিয়ে বলা হল এই গ্রাফে 7 আছে কিনা। তখন আমরা সার্চ করতে থাকব। এক সময় 7 পেয়ে যাবো। তখন আমারা উত্তর দিব, হ্যা, এই গ্রাফে 7 রয়েছে। আর যখনই আমরা 7 পেয়ে যাবো, তখনই আমরা সার্চ বন্ধ করে দিব। মানে হচ্ছে আমরা 7 এর পর আর কোন সার্চ করব না। গ্রাফটি দিয়ে আমাদের যদি জিজ্ঞেস করত গ্রাফে 1 আছে কিনা জানাতে, তখন আমরা প্রথম নডই দেখব 1। তখন সাথে সাথেই বলব, হ্যা, এক রয়েছে এবং সেখানেই আমরা সার্চ বন্ধ করব।

কিউতে কোন ডেটা ঢুকানোকে আমরা বলি Enqueue। আর কিউ থেকে কোন ডেটা বের করাকে আমরা বলি Dequeue। ব্রেডথ ফার্স্ট সার্চ অ্যালগরিদমের সুডোকোড নিচে দেওয়া হলো। সোর্সঃ উইকিপিডিয়া।

Breadth-First-Search(Graph, root):

    for each node n in Graph:
        n.distance = INFINITY
        n.parent = NIL

    create empty queue Q

    root.distance = 0
    Q.enqueue(root)

    while Q is not empty:
        current = Q.dequeue()
        for each node n that is adjacent to current:
            if n.distance == INFINITY:
                n.distance = current.distance + 1
                n.parent = current
                Q.enqueue(n)

এক বইতে এক রকম করে এই সুডোকোড লেখা হয়, মূল কনসেফট একই রকম।

কমপ্লেক্সিটি: ব্রেডথ ফার্স্ট সার্চ করার সময় আমরা প্রতিটি নড [V] একবার এবং প্রতিটা এজ [E] এ একবার গিয়েছি, তাই কমপ্লেক্সিটি হবে O(V+E)।

কমপ্লিটনেসঃ ব্রেডথ ফার্স্ট সার্চ কমপ্লিট যদি ফিনিট সংখ্যক নড থাকে।