ব্রেডথ-ফার্স্ট সার্চ#

ব্রেডথ-ফার্স্ট সার্চ হলো গ্রাফে সার্চ করার মৌলিক এবং অপরিহার্য অ্যালগরিদমগুলোর মধ্যে একটি।

এই অ্যালগরিদম যেভাবে কাজ করে, তার ফলস্বরূপ ব্রেডথ-ফার্স্ট সার্চের মাধ্যমে যেকোনো নোডে পাওয়া পাথটি সেই নোডের শর্টেস্ট পাথ হয়, অর্থাৎ আনওয়েটেড গ্রাফে সবচেয়ে কম সংখ্যক এজ বিশিষ্ট পাথ।

অ্যালগরিদমটি $O(n + m)$ সময়ে কাজ করে, যেখানে $n$ হলো ভার্টেক্সের সংখ্যা এবং $m$ হলো এজের সংখ্যা।

অ্যালগরিদমের বর্ণনা#

অ্যালগরিদমটি ইনপুট হিসেবে একটি আনওয়েটেড গ্রাফ এবং সোর্স ভার্টেক্স $s$-এর আইডি নেয়। ইনপুট গ্রাফটি ডিরেক্টেড বা আনডিরেক্টেড হতে পারে, অ্যালগরিদমের জন্য এটি কোনো বিষয় নয়।

অ্যালগরিদমটি গ্রাফে আগুন ছড়িয়ে পড়ার মতো করে বোঝা যায়: শূন্যতম ধাপে শুধুমাত্র সোর্স $s$-এ আগুন জ্বলছে। প্রতিটি ধাপে, প্রতিটি ভার্টেক্সে জ্বলতে থাকা আগুন তার সমস্ত প্রতিবেশীতে ছড়িয়ে পড়ে। অ্যালগরিদমের একটি ইটারেশনে, “আগুনের বলয়” প্রস্থে এক একক প্রসারিত হয় (এ কারণেই অ্যালগরিদমের এই নাম)।

আরও সুনির্দিষ্টভাবে, অ্যালগরিদমটি নিম্নরূপ বর্ণনা করা যায়: একটি কিউ $q$ তৈরি করুন যেটিতে প্রসেস করার জন্য ভার্টেক্সগুলো থাকবে এবং একটি বুলিয়ান অ্যারে $used[]$ তৈরি করুন যা প্রতিটি ভার্টেক্সের জন্য নির্দেশ করে যে এটি আলোকিত (বা ভিজিটেড) হয়েছে কি না।

প্রথমে, সোর্স $s$-কে কিউতে পুশ করুন এবং $used[s] = true$ সেট করুন, এবং অন্য সমস্ত ভার্টেক্স $v$-এর জন্য $used[v] = false$ সেট করুন। তারপর, কিউ খালি না হওয়া পর্যন্ত লুপ চালান এবং প্রতিটি ইটারেশনে কিউয়ের সামনে থেকে একটি ভার্টেক্স পপ করুন। এই ভার্টেক্স থেকে বের হওয়া সমস্ত এজ ইটারেট করুন এবং যদি এই এজগুলোর কোনোটি এমন ভার্টেক্সে যায় যেগুলো ইতিমধ্যে আলোকিত হয়নি, তাহলে সেগুলোতে আগুন ধরিয়ে দিন এবং কিউতে রাখুন।

ফলস্বরূপ, কিউ খালি হয়ে গেলে, “আগুনের বলয়” সোর্স $s$ থেকে পৌঁছানো যায় এমন সমস্ত ভার্টেক্স ধারণ করে, এবং প্রতিটি ভার্টেক্সে সম্ভাব্য সবচেয়ে সংক্ষিপ্ত পথে পৌঁছানো হয়েছে। আপনি শর্টেস্ট পাথের দৈর্ঘ্যও হিসাব করতে পারেন (এর জন্য শুধু পাথের দৈর্ঘ্যের একটি অ্যারে $d[]$ বজায় রাখা প্রয়োজন) এবং সেই সাথে এই সমস্ত শর্টেস্ট পাথ পুনরুদ্ধারের জন্য তথ্য সংরক্ষণ করতে পারেন (এর জন্য “প্যারেন্ট”-এর একটি অ্যারে $p[]$ বজায় রাখা প্রয়োজন, যা প্রতিটি ভার্টেক্সের জন্য সেই ভার্টেক্সটি সংরক্ষণ করে যেটি থেকে আমরা এখানে পৌঁছেছি)।

ইমপ্লিমেন্টেশন#

আমরা বর্ণিত অ্যালগরিদমের কোড C++ এবং Java-তে লিখছি।

C++

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

Java

ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adjacency list representation

int n; // number of nodes
int s; // source vertex


LinkedList<Integer> q = new LinkedList<Integer>();
boolean used[] = new boolean[n];
int d[] = new int[n];
int p[] = new int[n];

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.isEmpty()) {
    int v = q.pop();
    for (int u : adj.get(v)) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

যদি আমাদের সোর্স থেকে কোনো ভার্টেক্স $u$-তে শর্টেস্ট পাথ পুনরুদ্ধার ও প্রদর্শন করতে হয়, তাহলে নিম্নলিখিত উপায়ে তা করা যেতে পারে:

C++

if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";
}

Java

if (!used[u]) {
    System.out.println("No path!");
} else {
    ArrayList<Integer> path = new ArrayList<Integer>();
    for (int v = u; v != -1; v = p[v])
        path.add(v);
    Collections.reverse(path);
    for(int v : path)
        System.out.println(v);
}

BFS-এর অ্যাপ্লিকেশন#

  • আনওয়েটেড গ্রাফে একটি সোর্স থেকে অন্যান্য ভার্টেক্সে শর্টেস্ট পাথ বের করা।

  • $O(n + m)$ সময়ে একটি আনডিরেক্টেড গ্রাফের সমস্ত কানেক্টেড কম্পোনেন্ট বের করা: এর জন্য, আমরা প্রতিটি ভার্টেক্স থেকে BFS চালাই, তবে পূর্ববর্তী রানে ইতিমধ্যে ভিজিটেড হয়ে যাওয়া ভার্টেক্সগুলো বাদ দিই। এভাবে, আমরা প্রতিটি ভার্টেক্স থেকে স্বাভাবিক BFS চালাই, কিন্তু প্রতিবার নতুন কানেক্টেড কম্পোনেন্ট পেলে $used[]$ অ্যারে রিসেট করি না, এবং মোট রানিং টাইম তখনও $O(n + m)$ থাকে ($used []$ অ্যারে শূন্য না করে গ্রাফে একাধিক BFS চালানোকে ব্রেডথ-ফার্স্ট সার্চের সিরিজ বলা হয়)।

  • কোনো সমস্যা বা গেমের সবচেয়ে কম সংখ্যক মুভে সমাধান বের করা, যদি গেমের প্রতিটি স্টেটকে গ্রাফের একটি ভার্টেক্স হিসেবে এবং এক স্টেট থেকে অন্য স্টেটে ট্রানজিশনকে গ্রাফের এজ হিসেবে উপস্থাপন করা যায়।

  • ০ বা ১ ওয়েট বিশিষ্ট গ্রাফে শর্টেস্ট পাথ বের করা: এর জন্য স্বাভাবিক ব্রেডথ-ফার্স্ট সার্চে সামান্য পরিবর্তন প্রয়োজন: $used[]$ অ্যারে বজায় রাখার পরিবর্তে, আমরা এখন পরীক্ষা করব ভার্টেক্সের দূরত্ব বর্তমানে পাওয়া দূরত্বের চেয়ে কম কি না, তারপর বর্তমান এজের ওয়েট যদি শূন্য হয়, তাহলে এটিকে কিউয়ের সামনে যোগ করি, অন্যথায় কিউয়ের পেছনে যোগ করি। এই পরিবর্তন 0-1 BFS আর্টিকেলে আরও বিস্তারিত ব্যাখ্যা করা হয়েছে।

  • ডিরেক্টেড আনওয়েটেড গ্রাফে শর্টেস্ট সাইকেল বের করা: প্রতিটি ভার্টেক্স থেকে ব্রেডথ-ফার্স্ট সার্চ শুরু করুন। বর্তমান ভার্টেক্স থেকে সোর্স ভার্টেক্সে ফিরে যাওয়ার চেষ্টা করা মাত্রই, আমরা সোর্স ভার্টেক্সকে ধারণ করে এমন শর্টেস্ট সাইকেল পেয়ে গেছি। এই পয়েন্টে আমরা BFS বন্ধ করতে পারি এবং পরবর্তী ভার্টেক্স থেকে নতুন BFS শুরু করতে পারি। এরকম সমস্ত সাইকেল থেকে (প্রতিটি BFS থেকে সর্বোচ্চ একটি) সবচেয়ে ছোটটি বেছে নিন।

  • প্রদত্ত ভার্টেক্স জোড়া $(a, b)$-এর মধ্যে যেকোনো শর্টেস্ট পাথে অবস্থিত সমস্ত এজ বের করা। এর জন্য, দুটি ব্রেডথ-ফার্স্ট সার্চ চালান: একটি $a$ থেকে এবং একটি $b$ থেকে। ধরি $d_a []$ হলো প্রথম BFS ($a$ থেকে) থেকে প্রাপ্ত শর্টেস্ট দূরত্বের অ্যারে এবং $d_b []$ হলো $b$ থেকে দ্বিতীয় BFS থেকে প্রাপ্ত শর্টেস্ট দূরত্বের অ্যারে। এখন প্রতিটি এজ $(u, v)$-এর জন্য সহজেই পরীক্ষা করা যায় যে সেই এজটি $a$ ও $b$-এর মধ্যে কোনো শর্টেস্ট পাথে আছে কি না: শর্ত হলো $d_a [u] + 1 + d_b [v] = d_a [b]$।

  • প্রদত্ত ভার্টেক্স জোড়া $(a, b)$-এর মধ্যে যেকোনো শর্টেস্ট পাথে অবস্থিত সমস্ত ভার্টেক্স বের করা। এটি সম্পন্ন করতে, দুটি ব্রেডথ-ফার্স্ট সার্চ চালান: একটি $a$ থেকে এবং একটি $b$ থেকে। ধরি $d_a []$ হলো প্রথম BFS ($a$ থেকে) থেকে প্রাপ্ত শর্টেস্ট দূরত্বের অ্যারে এবং $d_b []$ হলো $b$ থেকে দ্বিতীয় BFS থেকে প্রাপ্ত শর্টেস্ট দূরত্বের অ্যারে। এখন প্রতিটি ভার্টেক্সের জন্য সহজেই পরীক্ষা করা যায় যে এটি $a$ ও $b$-এর মধ্যে কোনো শর্টেস্ট পাথে আছে কি না: শর্ত হলো $d_a [v] + d_b [v] = d_a [b]$।

  • আনওয়েটেড গ্রাফে সোর্স ভার্টেক্স $s$ থেকে টার্গেট ভার্টেক্স $t$-এ জোড় দৈর্ঘ্যের শর্টেস্ট ওয়াক বের করা: এর জন্য, আমাদের একটি সহায়ক গ্রাফ তৈরি করতে হবে, যার ভার্টেক্সগুলো হলো স্টেট $(v, c)$, যেখানে $v$ - বর্তমান নোড, $c = 0$ বা $c = 1$ - বর্তমান প্যারিটি। মূল গ্রাফের যেকোনো এজ $(u, v)$ এই নতুন গ্রাফে দুটি এজে পরিণত হবে: $((u, 0), (v, 1))$ এবং $((u, 1), (v, 0))$। এরপর আমরা শুরু ভার্টেক্স $(s, 0)$ থেকে শেষ ভার্টেক্স $(t, 0)$-এ শর্টেস্ট ওয়াক বের করতে BFS চালাই।
    লক্ষ্য করুন: এই আইটেমে “পাথ"-এর পরিবর্তে “ওয়াক” শব্দটি ব্যবহার করা হয়েছে কারণ ওয়াকের দৈর্ঘ্য জোড় করতে পাওয়া ওয়াকে ভার্টেক্স পুনরাবৃত্তি হতে পারে। জোড় দৈর্ঘ্যের শর্টেস্ট পাথ বের করার সমস্যাটি ডিরেক্টেড গ্রাফে NP-Complete, এবং আনডিরেক্টেড গ্রাফে লিনিয়ার টাইমে সমাধানযোগ্য, তবে অনেক বেশি জটিল পদ্ধতিতে।

প্র্যাকটিস প্রবলেম#