Prim's Algorithm এবং Kruskal's Algorithm

Prim's Algorithm এবং Kruskal's Algorithm দুইটি জনপ্রিয় অ্যালগরিদম যা মিনিমাম স্প্যানিং ট্রি (MST) খুঁজে বের করতে ব্যবহৃত হয়। একটি গ্রাফে MST হল এমন একটি সাবগ্রাফ যা সকল নোডকে সংযুক্ত করে এবং তার মোট ওজন সর্বনিম্ন। এই দুটি অ্যালগরিদমের কার্যপদ্ধতি এবং তাদের মধ্যে পার্থক্য নিচে আলোচনা করা হলো।

Prim's Algorithm

Prim's Algorithm একটি ডিরেক্টেড বা আন্ডিরেক্টেড গ্রাফ থেকে MST তৈরি করতে ব্যবহৃত হয়। এটি একটি গ্রাফের একটি স্টার্টিং নোড থেকে শুরু করে ধাপে ধাপে MST তৈরি করে।

কাজের প্রক্রিয়া:

1. শুরু করুন: একটি নোড (যেকোনো একটি) নির্বাচন করুন এবং এটিকে MST-তে যুক্ত করুন।
2. নতুন নোড নির্বাচন করুন: MST-তে অন্তর্ভুক্ত করা নোডগুলোর সাথে সংযুক্ত নোডগুলির মধ্যে সর্বনিম্ন ওজনের এজ বেছে নিন এবং সেই নোডটিকে MST-তে যুক্ত করুন।
3. পুনরাবৃত্তি করুন: ধাপে ধাপে ২ নম্বর পদ্ধতিটি পুনরাবৃত্তি করুন যতক্ষণ না সমস্ত নোড MST-তে অন্তর্ভুক্ত না হয়।

টাইম কমপ্লেক্সিটি:

• অ্যাডজেসেন্সি ম্যাট্রিক্স: O(V^2)
• অ্যাডজেসেন্সি লিস্ট এবং মিন-হিপ: O(E log V)

উদাহরণ:

import heapq

def prim(graph):
    start_node = 0  # Starting from node 0
    visited = set()
    min_heap = [(0, start_node)]  # (weight, node)
    mst = []

    while min_heap:
        weight, node = heapq.heappop(min_heap)
        if node not in visited:
            visited.add(node)
            mst.append((weight, node))

            for neighbor, edge_weight in graph[node]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (edge_weight, neighbor))

    return mst

Kruskal's Algorithm

Kruskal's Algorithm মিনিমাম স্প্যানিং ট্রি খুঁজে বের করতে একটি গ্রাফের এজগুলোর উপর ভিত্তি করে কাজ করে। এটি সমস্ত এজকে তাদের ওজনের ক্রম অনুযায়ী সাজায় এবং নোডগুলিকে সংযুক্ত করে MST তৈরি করে।

কাজের প্রক্রিয়া:

1. এজগুলোকে সাজান: সমস্ত এজগুলোকে তাদের ওজনের বৃদ্ধি ক্রম অনুযায়ী সাজান।
2. MST তৈরি করুন: নিচ থেকে শুরু করে, সর্বনিম্ন ওজনের এজ থেকে শুরু করে, যদি ঐ এজটি নোডগুলির মধ্যে লুপ তৈরি না করে, তবে এটি MST-তে যুক্ত করুন।
3. পুনরাবৃত্তি করুন: এই প্রক্রিয়াটি চলতে থাকে যতক্ষণ না MST সম্পূর্ণ হয়।

টাইম কমপ্লেক্সিটি:

• O(E log E) (এজগুলো সাজাতে সময় লাগে)

উদাহরণ:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(graph):
    edges = sorted(graph['edges'], key=lambda x: x[2])  # Sorting edges by weight
    disjoint_set = DisjointSet(graph['vertices'])
    mst = []

    for u, v, weight in edges:
        if disjoint_set.find(u) != disjoint_set.find(v):
            disjoint_set.union(u, v)
            mst.append((u, v, weight))

    return mst

Prim's Algorithm vs Kruskal's Algorithm

সারসংক্ষেপ

Prim's এবং Kruskal's অ্যালগরিদম উভয়ই মিনিমাম স্প্যানিং ট্রি তৈরি করতে ব্যবহৃত হয়, তবে তাদের কাজ করার পদ্ধতি ভিন্ন। Prim's Algorithm নোডের ভিত্তিতে কাজ করে এবং Kruskal's Algorithm এজগুলোর ভিত্তিতে কাজ করে। নির্বাচনের প্রক্রিয়া এবং টাইম কমপ্লেক্সিটিও তাদের মধ্যে পার্থক্য সৃষ্টি করে। বিভিন্ন সমস্যার জন্য উভয় অ্যালগরিদমই কার্যকর।