ডেপথ ফার্স্ট সার্চ (DFS), ব্রেডথ ফার্স্ট সার্চ (BFS)

ডেপথ ফার্স্ট সার্চ (DFS)

ডেপথ ফার্স্ট সার্চ (DFS) একটি গ্রাফ বা ট্রির জন্য একটি সার্চ অ্যালগরিদম, যা একসাথে যতটা সম্ভব গভীরে চলে যায়, যতক্ষণ না এটি আর এগিয়ে যেতে পারে, তারপর ব্যাকট্র্যাক করে। এটি গাছ বা গ্রাফের সমস্ত নোড পরিদর্শন করতে ব্যবহৃত হয়।

বৈশিষ্ট্য

• স্ট্যাক ব্যবহৃত হয়: এটি স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করে (ইমপ্লিমেন্টেশন রিকার্সিভ হতে পারে)।
• গভীর অনুসন্ধান: এটি প্রথমে একটি শাখার শেষে পৌঁছাতে চেষ্টা করে এবং তারপর অন্যান্য শাখাগুলির দিকে চলে যায়।
• অপারেশন: নোড পরিদর্শন করার পর, নোডটির অঙ্গসংযোগগুলোতে চলে যায়।

অ্যালগরিদম

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start, end=' ')
        
        for neighbor in self.graph.get(start, []):
            if neighbor not in visited:
                self.dfs(neighbor, visited)

# উদাহরণ ব্যবহার
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)
g.add_edge(2, 6)

print("DFS traversal starting from node 0:")
g.dfs(0)

ব্রেডথ ফার্স্ট সার্চ (BFS)

ব্রেডথ ফার্স্ট সার্চ (BFS) একটি গ্রাফ বা ট্রির জন্য একটি সার্চ অ্যালগরিদম, যা প্রথমে স্তরভিত্তিকভাবে সমস্ত নোড পরিদর্শন করে। এটি প্রথমে সব নিকটবর্তী নোডগুলো পরিদর্শন করে এবং পরে তাদের পরবর্তী স্তরের নোডগুলোতে চলে যায়।

বৈশিষ্ট্য

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

অ্যালগরিদম

from collections import deque

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

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

# উদাহরণ ব্যবহার
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)
g.add_edge(2, 6)

print("\nBFS traversal starting from node 0:")
g.bfs(0)

সারসংক্ষেপ

DFS:

• গভীর অনুসন্ধান করে।
• স্ট্যাক ব্যবহার করে।
• নোডগুলোর গভীরতর স্তরে যায়।

BFS:

• স্তরভিত্তিক অনুসন্ধান করে।
• কিউ ব্যবহার করে।
• নিকটবর্তী নোডগুলো আগে পরিদর্শন করে।

এই অ্যালগরিদমগুলো বিভিন্ন অ্যাপ্লিকেশনে ব্যবহৃত হয়, যেমন shortest path calculation, connectivity checking, এবং গাছের স্ট্রাকচারে কাজ করার জন্য।