DFS এবং BFS সার্চ টেকনিকস

DFS (Depth-First Search) এবং BFS (Breadth-First Search) সার্চ টেকনিকস

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

১. Depth-First Search (DFS) - গভীরতা-প্রথম অনুসন্ধান

DFS হল একটি অনুসন্ধান পদ্ধতি, যেখানে প্রথমে গভীরভাবে একে একে নোডগুলো পরিদর্শন করা হয়। এটি পাথের গভীরে চলে যায় এবং যতক্ষণ না এটি একটি শেষ নোড (leaf node) বা dead end পায়, ততক্ষণ পরবর্তী নোড বা পথের দিকে এগোয় না। যখন এটি dead end এ পৌঁছায়, তখন এটি পূর্ববর্তী অবস্থায় ফিরে আসে এবং অন্য একটি পথ অনুসন্ধান শুরু করে।

DFS এর কার্যপ্রণালী:

1. DFS শুরু হয় একটি রুট নোড থেকে।
2. রুট থেকে শুরু করে যতক্ষণ না এটি একটি leaf node বা unvisited node পায়, ততক্ষণ গভীরে চলে যায়।
3. যদি একটি নোডের সব সন্তান নোড পরিদর্শিত হয়ে থাকে, তখন এটি ব্যাকট্র্যাকিং করে পূর্ববর্তী নোডে ফিরে আসে এবং অন্য একটি সম্ভাব্য পথ অনুসন্ধান শুরু করে।

DFS এর সুবিধা:

• মেমরি ব্যবহার কম (বস্তুত, শুধুমাত্র একটি পথ অনুসরণ করে মেমরি ব্যবহার হয়)।
• একটি solution path খুঁজে পাওয়ার সম্ভাবনা বেশি যদি solution পথ গভীরতা অনুযায়ী থাকে।

DFS এর সীমাবদ্ধতা:

• অনন্ত বা বড় গ্রাফের জন্য উপযুক্ত নয় যদি গ্রাফ সঠিকভাবে সীমাবদ্ধ না থাকে।
• এটি মাধ্যমিক বা দীর্ঘ পাথ পছন্দ করতে পারে, যা সমস্যায় ফেলা যেতে পারে।

DFS এর উদাহরণ:

ধরা যাক, আমাদের একটি গ্রাফ রয়েছে:

A → B → D
↓     ↓
C → E

এখানে, আমরা A থেকে DFS অনুসন্ধান শুরু করি। DFS অনুসরণ করবে:

• A → B → D → (ব্যাকট্র্যাক) → C → E।

DFS প্রোগ্রাম (পাইথন উদাহরণ):

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)  # current node
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# উদাহরণ গ্রাফ
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

dfs(graph, 'A')

আউটপুট:

A
B
D
C
E

২. Breadth-First Search (BFS) - প্রস্থ-প্রথম অনুসন্ধান

BFS হল একটি অনুসন্ধান পদ্ধতি, যেখানে প্রথমে প্রস্থে অনুসন্ধান শুরু করা হয়, অর্থাৎ একটি নোডের সব সন্তান নোড একসাথে পরিদর্শন করা হয়, তারপর তাদের সন্তানেরা পরিদর্শন করা হয়। এটি নোডের স্তর অনুসারে অনুসন্ধান করে।

BFS এর কার্যপ্রণালী:

1. BFS একটি রুট নোড থেকে শুরু হয়।
2. প্রথমে রুট নোডের সকল সরাসরি সন্তান পরিদর্শন করা হয়।
3. এরপর প্রতিটি স্তরের নোড পরবর্তী স্তরের নোডগুলোকে পরিদর্শন করে।

BFS এর সুবিধা:

• শুধুমাত্র প্রথম সমাধান খুঁজে বের করা হলে এটি দ্রুত কাজ করে, কারণ এটি প্রথমে একে একে নোডের স্তর অনুসরণ করে।
• এটি সবচেয়ে সংক্ষিপ্ত পথ (shortest path) খুঁজে বের করতে পারে, যদি গ্রাফের সব edge এর ওজন সমান থাকে।

BFS এর সীমাবদ্ধতা:

• এটি বেশি মেমরি ব্যবহার করতে পারে, কারণ সমস্ত নোড একত্রে পরিদর্শন করতে হয়।
• সঠিকভাবে সমাধান খুঁজে বের করতে আরও বেশি মেমরি প্রয়োজন হতে পারে।

BFS এর উদাহরণ:

ধরা যাক, আমাদের একই গ্রাফ আছে:

A → B → D
↓     ↓
C → E

এখানে, আমরা A থেকে BFS অনুসন্ধান শুরু করি। BFS অনুসরণ করবে:

• A → B → C → D → E।

BFS প্রোগ্রাম (পাইথন উদাহরণ):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)  # current node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# উদাহরণ গ্রাফ
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

bfs(graph, 'A')

আউটপুট:

A
B
C
D
E

DFS এবং BFS এর মধ্যে পার্থক্য

সারসংক্ষেপ

DFS এবং BFS দুটি গ্রাফ বা ট্রি অনুসন্ধান কৌশল যা সম্পূর্ণ ভিন্ন অর্ডারে নোডগুলো পরিদর্শন করে:

• DFS গভীরতা অনুসারে কাজ করে, প্রথমে একটি পথ অনুসরণ করে যতক্ষণ না এটি একটি শাখার শেষ পায় এবং তারপর ব্যাকট্র্যাকিং করে অন্য পথ অনুসন্ধান করে।
• BFS প্রস্থ অনুসারে কাজ করে, একেকটি স্তরের সমস্ত নোড একসাথে পরিদর্শন করে।

এগুলো দুটোই গ্রাফ বা ট্রি সমস্যার সমাধান করতে গুরুত্বপূর্ণ, এবং প্রয়োগের ক্ষেত্রে প্রতিটি পদ্ধতির সুবিধা এবং সীমাবদ্ধতা রয়েছে।