Depth-First Search (DFS)

Depth-First Search (DFS) হলো একটি গ্রাফ বা ট্রি অনুসন্ধান অ্যালগরিদম, যা প্রথমে একটি শাখার শেষ পর্যন্ত অনুসন্ধান করে এবং তারপর ফিরে এসে অন্য শাখার দিকে অগ্রসর হয়। এটি মূলত Stack ডেটা স্ট্রাকচার ব্যবহার করে, যেখানে একটি নোড পরিদর্শন করার পর তার সব অবাঞ্ছিত (unvisited) সন্তান নোডগুলোকে স্ট্যাকের উপরে রাখা হয়।

DFS এর কাজের ধাপ:

1. একটি নোড নির্বাচন করে পরিদর্শন করুন এবং তার পরবর্তী (child) নোডে যান।
2. প্রতিটি নোড পরিদর্শনের সময় স্ট্যাকে রাখুন।
3. যদি কোনো নোডের সব সন্তান নোড পরিদর্শন করা হয়ে যায়, তাহলে আগের নোডে ফিরে যান।
4. এভাবে প্রতিটি নোড পরিদর্শন করুন যতক্ষণ না সমস্ত নোড পরিদর্শিত হয়।

উদাহরণ কোড (Python):

def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# গ্রাফটি
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited = set()
dfs(graph, 'A', visited)
Copy

এই কোডটি A নোড থেকে শুরু করে প্রতিটি নোডে DFS অনুসরণ করে চলে। প্রতিটি নোড একবার করে পরিদর্শন করা হবে।

DFS এর ব্যবহার:

• সাইকেল ডিটেকশন
• টপোলজিক্যাল সাজানো
• গেমের বিভিন্ন স্তরের সমাধান
• পথের খোঁজ

Breadth-First Search (BFS)

Breadth-First Search (BFS) হলো একটি গ্রাফ বা ট্রি অনুসন্ধান অ্যালগরিদম, যা প্রথমে একটি নির্দিষ্ট নোড থেকে শুরু করে তার আশেপাশের নোডগুলোকে পরিদর্শন করে এবং এরপর পর্যায়ক্রমে আরো দূরের নোডগুলোতে অগ্রসর হয়। এটি Queue ডেটা স্ট্রাকচার ব্যবহার করে, যেখানে প্রথমে প্রবেশ করা নোডটি প্রথমে বের হয়।

BFS এর কাজের ধাপ:

1. একটি নোড নির্বাচন করে পরিদর্শন করুন এবং তাকে কিউতে যুক্ত করুন।
2. কিউ থেকে প্রথম নোডটি বের করে তার সমস্ত অবাঞ্ছিত শিশু নোডগুলোকে কিউতে যোগ করুন।
3. প্রতিটি নোড পরিদর্শন করার পর কিউ থেকে সরিয়ে নিন।
4. এই প্রক্রিয়া চলতে থাকে যতক্ষণ না সমস্ত নোড পরিদর্শিত হয়।

উদাহরণ কোড (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# গ্রাফটি
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')
Copy

এই কোডটি A নোড থেকে শুরু করে প্রতিটি নোডে BFS অনুসরণ করে চলে এবং পরম্পরাগতভাবে নোডগুলো পরিদর্শন করা হয়।

BFS এর ব্যবহার:

• পথ খোঁজার সমস্যা (Shortest Path Problem)
• সামাজিক নেটওয়ার্ক বিশ্লেষণ
• গেম তত্ত্ব
• ওয়েব ক্রলিং

DFS এবং BFS এর তুলনা

DFS এবং BFS উভয়ই গ্রাফ ও ট্রি অনুসন্ধানে ব্যবহৃত হয় তবে বিভিন্ন ক্ষেত্রে এদের ব্যবহার ও কার্যকারিতা ভিন্ন।