গ্রাফ অ্যালগরিদম৮ মিনিট পড়া

বিএফএস এবং ডিএফএস পুনর্বিবেচনা (BFS & DFS Revisited)

গ্রাফ অন্বেষণের দুটি উপায় — স্তর অনুযায়ী, অথবা একদম গভীরে গিয়ে

BFS:O(V+E)DFS:O(V+E)space:O(V)

ধরুন আপনি ঢাকার কোনো গলিতে হারিয়ে গেছেন। পথ খোঁজার দুটি কৌশল হতে পারে:

বিএফএস (BFS বা Breadth-First Search) — আপনি আপনার বন্ধুদের সব দিকে একইসাথে পাঠালেন। প্রথমে তারা এক ধাপ দূরের প্রতিটি জায়গা চেক করবে। তারপর দুই ধাপ দূরের জায়গাগুলো। তারপর তিন। অর্থাৎ আপনি পুকুরে ঢিল ছোড়ার মতো স্তরে স্তরে (level by level) খুঁজবেন।

ডিএফএস (DFS বা Depth-First Search) — আপনি একটি রাস্তা বেছে নেবেন এবং সেটা যতটা দূর যায় ততটা যাবেন। যদি রাস্তা বন্ধ পান? তবে পিছিয়ে এসে শেষ মোড় থেকে অন্য রাস্তা চেষ্টা করবেন। আপনি ছড়ানোর আগে গভীরে যাবেন।

উভয় কৌশলই প্রতিটি পৌঁছানো যায় এমন জায়গা ঠিক একবার পরিদর্শন করবে। কিন্তু তারা যে ক্রমে (order) পৌঁছায় তা সম্পূর্ণ ভিন্ন — এবং এই ক্রমই নির্ধারণ করে কোন অ্যালগরিদমটি কোন সমস্যার জন্য সবচেয়ে উপযুক্ত।

ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search)

বিএফএস একটি কিউ (queue) (আগে আসলে আগে যাবে) ব্যবহার করে। আপনি শুরুর নোডটি কিউতে রাখবেন, সেটিকে পরিদর্শিত (visited) হিসেবে চিহ্নিত করবেন। এরপর বারবার কিউ থেকে একটি একটি করে নোড বের করবেন এবং তার সমস্ত অপরিবর্তিত প্রতিবেশীকে কিউতে যুক্ত করবেন।

যেহেতু নোডগুলো শুরু থেকে দূরত্বের ক্রমানুসারে প্রক্রিয়া করা হয়, বিএফএস স্বাভাবিকভাবেই ওজনহীন গ্রাফে (unweighted graph) ক্ষুদ্রতম পথ খুঁজে বের করে। বিএফএস যখন প্রথমবার কোনো নোডে পৌঁছায়, তখন সেটি সবচেয়ে কম সংখ্যক রাস্তা ব্যবহার করেই পৌঁছায়।

সাধারণ ব্যবহার: ওজনহীন গ্রাফে ক্ষুদ্রতম পথ বের করা, লেভেল-অর্ডার ট্রাভার্সাল (level-order traversal), দ্বিপাক্ষিকতা (bipartiteness) পরীক্ষা (২-রঙ করা), এবং সংযুক্ত অংশগুলো (connected components) খুঁজে বের করা।

ডেপথ-ফার্স্ট সার্চ (Depth-First Search)

ডিএফএস একটি স্ট্যাক (stack) ব্যবহার করে — এটি সরাসরি স্ট্যাক হতে পারে অথবা রিকার্শনের (recursion) মাধ্যমে কল স্ট্যাক হতে পারে। আপনি শুরুর নোডটিকে স্ট্যাকে রাখবেন, তারপর সবসময় সদ্য আবিষ্কৃত অপরিবর্তিত নোডটি প্রক্রিয়া করবেন।

ডিএফএস প্রতিটি নোডকে একটি আবিষ্কারের সময় (discovery time) (কখন এটি প্রথমবার পরিদর্শিত হয়েছিল) এবং একটি শেষ করার সময় (finish time) (কখন এর সমস্ত বংশধরকে পুরোপুরি অন্বেষণ করা হয়েছিল) দেয়। এই টাইমস্ট্যাম্পগুলো গ্রাফের গঠন প্রকাশ করে।

সাধারণ ব্যবহার: টপোলজিক্যাল সর্ট (topological sort), সাইকেল শনাক্তকরণ (cycle detection), দৃঢ়ভাবে সংযুক্ত অংশগুলো (strongly connected components) খুঁজে বের করা (যেমন টারজানের অ্যালগরিদম), এবং সেতু (bridges) ও সংযোগ বিন্দু (articulation points) শনাক্ত করা।

বিএফএস এবং ক্ষুদ্রতম পথ (BFS and Shortest Paths)

ওজনহীন গ্রাফে, বিএফএস গ্যারান্টি দেয় যে যখন নোড v প্রথমবার কিউ থেকে বের করা হয়, তখন dist[v] উৎস থেকে এর সঠিক ক্ষুদ্রতম দূরত্ব ধারণ করে। কারণ কী? কারণ বিএফএস d+1 দূরত্বের কোনো নোড প্রক্রিয়া করার আগে d দূরত্বের সমস্ত নোড প্রক্রিয়া করে। d+1 দৈর্ঘ্যের যেকোনো পথকে প্রথমেই d দূরত্বের একটি নোডের মধ্য দিয়ে যেতে হবে।

ডিএফএস টাইমস্ট্যাম্প এবং এগুলো যা জানায় (DFS Timestamps and What They Tell You)

ডিএফএস টাইমস্ট্যাম্পগুলো বন্ধনী উপপাদ্য (parenthesis theorem) মেনে চলে: যেকোনো দুটি নোড u এবং v এর জন্য, তাদের সক্রিয় সময়কাল (disc[u] থেকে fin[u] এবং disc[v] থেকে fin[v]) হয় সম্পূর্ণভাবে একটির ভেতরে আরেকটি থাকে অথবা সম্পূর্ণ আলাদা থাকে — কখনও আংশিক ওভারল্যাপ করে না। এর মানে হলো:

ব্যাক এজ (Back edge) (স্ট্যাকে থাকা পূর্বপুরুষের দিকে) → সাইকেল শনাক্ত হয়েছে
ছোট হতে থাকা ফিনিশ টাইম → ডিরেক্টেড অ্যাসাইক্লিক গ্রাফের (DAG) টপোলজিক্যাল ক্রম
লো-লিংক মান (low-link values) (টারজান-এর অ্যালগরিদম থেকে) → দৃঢ়ভাবে সংযুক্ত অংশ (SCCs) এবং সেতু (bridges)

বাইপারটাইট শনাক্তকরণ (Bipartiteness Check)

একটি গ্রাফ বাইপারটাইট হবে যদি আপনি প্রতিটি নোডকে লাল বা নীল রঙ করতে পারেন যাতে কোনো দুটি প্রতিবেশী নোডের রঙ এক না হয়। বিএফএস এটিকে সহজ করে তোলে: শুরুর নোডটি লাল রঙ করুন, এর প্রতিবেশীদের নীল রঙ করুন, তাদের প্রতিবেশীদের লাল রঙ করুন, এবং এভাবেই চলতে থাকুন। যদি কখনো কোনো নোডকে ইতিমধ্যে থাকা রঙের চেয়ে ভিন্ন রঙে রাঙাতে হয়, তবে গ্রাফটি বাইপারটাইট নয় (এটিতে একটি বিজোড়-দৈর্ঘ্যের সাইকেল রয়েছে)।

দ্রষ্টব্য: বিএফএস = কিউ ব্যবহার করে, ক্ষুদ্রতম পথ খোঁজে। ডিএফএস = স্ট্যাক (বা রিকার্শন) ব্যবহার করে, গ্রাফের গঠন নির্ণয় করে। যখন আপনি নিশ্চিত নন কোনটি ব্যবহার করবেন: সবচেয়ে ছোট পথ দরকার? বিএফএস ব্যবহার করুন। গ্রাফের সম্পূর্ণ গঠন বুঝতে হবে? ডিএফএস ব্যবহার করুন।

বিএফএস (ক্ষুদ্রতম পথ) এবং ডিএফএস (সাইকেল শনাক্তকরণ)

from collections import deque

def bfs_shortest(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def dfs_has_cycle(graph, n):
    # 0=unvisited, 1=in-stack, 2=done
    color = [0] * n
    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if color[v] == 1:
                return True   # back edge = cycle
            if color[v] == 0 and dfs(v):
                return True
        color[u] = 2
        return False
    return any(dfs(u) for u in range(n) if color[u] == 0)

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
print(bfs_shortest(graph, 0))  # {0:0, 1:1, 2:1, 3:2}

cyclic = [[1], [2], [0]]       # 0->1->2->0
print(dfs_has_cycle(cyclic, 3))  # True