মিনিমাম স্প্যানিং ট্রি (MST)
মিনিমাম স্প্যানিং ট্রি (MST) হলো একটি সংযুক্ত ওজনযুক্ত গ্রাফের একটি উপগ্রাফ যা সমস্ত নোডকে সংযুক্ত করে এবং এর মোট ওজন সর্বনিম্ন হয়। এটি বিভিন্ন বাস্তব জীবনের অ্যাপ্লিকেশন যেমন নেটওয়ার্ক ডিজাইন, রুটিং, এবং ক্লাস্টারিংয়ের জন্য গুরুত্বপূর্ণ।
MST এর প্রধান অ্যালগরিদম
- প্রিমের অ্যালগরিদম (Prim's Algorithm)
- ক্রুস্কাল-এর অ্যালগরিদম (Kruskal's Algorithm)
এখন এই অ্যালগরিদম দুটি সম্পর্কে বিস্তারিত আলোচনা করা যাক।
১. প্রিমের অ্যালগরিদম
প্রিমের অ্যালগরিদম একটি প্রক্রিয়া যার মাধ্যমে একটি নোড থেকে শুরু করে MST তৈরি করা হয়। এটি কেবলমাত্র সেই প্রান্তগুলি বিবেচনা করে যা বর্তমানে MST-তে নেই এবং MST-তে যুক্ত করার জন্য সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করে।
অ্যালগরিদমের পদক্ষেপ:
- একটি শুরু নোড চয়ন করুন।
- MST-তে নোড যোগ করুন এবং তাদের সংযুক্ত প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্ত চয়ন করুন।
- নোড যোগ করতে থাকুন যতক্ষণ না সব নোড MST-তে যুক্ত হয়।
উদাহরণ (Python Implementation):
import heapq
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, weight):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append((weight, v))
self.graph[v].append((weight, u))
def prim_mst(self, start):
visited = set()
min_heap = [(0, start)] # (weight, vertex)
mst_weight = 0
mst_edges = []
while min_heap:
weight, u = heapq.heappop(min_heap)
if u not in visited:
visited.add(u)
mst_weight += weight
mst_edges.append((weight, u))
for edge in self.graph[u]:
if edge[1] not in visited:
heapq.heappush(min_heap, edge)
return mst_weight, mst_edges
# উদাহরণ ব্যবহার
g = Graph()
g.add_edge('A', 'B', 1)
g.add_edge('A', 'C', 3)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 4)
g.add_edge('C', 'D', 2)
mst_weight, mst_edges = g.prim_mst('A')
print(f"Minimum Spanning Tree Weight: {mst_weight}")
print("Edges in MST:", mst_edges)
২. ক্রুস্কাল-এর অ্যালগরিদম
ক্রুস্কাল-এর অ্যালগরিদম MST তৈরি করার একটি জনপ্রিয় পদ্ধতি। এটি সমস্ত প্রান্তগুলোকে তাদের ওজন অনুযায়ী সাজিয়ে রেখে MST তৈরির প্রক্রিয়া সম্পন্ন করে। এটি সেই প্রান্তগুলো চয়ন করে, যেগুলো সাইকেল তৈরি করে না।
অ্যালগরিদমের পদক্ষেপ:
- সমস্ত প্রান্তগুলোকে ওজন অনুসারে সাজান।
- ছোট থেকে বড় প্রান্তগুলো নির্বাচন করতে থাকুন, যতক্ষণ না MST পূর্ণ হয়।
- সাইকেল তৈরি হচ্ছে কিনা তা নিশ্চিত করতে ইউনিয়ন-ফাইন্ড (Union-Find) ডেটা স্ট্রাকচার ব্যবহার করুন।
উদাহরণ (Python Implementation):
class Graph:
def __init__(self):
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append((weight, u, v))
def find(self, parent, u):
if parent[u] == u:
return u
return self.find(parent, parent[u])
def union(self, parent, rank, u, v):
root_u = self.find(parent, u)
root_v = self.find(parent, v)
if root_u != root_v:
if rank[root_u] > rank[root_v]:
parent[root_v] = root_u
elif rank[root_u] < rank[root_v]:
parent[root_u] = root_v
else:
parent[root_v] = root_u
rank[root_u] += 1
def kruskal_mst(self):
self.edges.sort() # Sort edges by weight
parent = {}
rank = {}
for weight, u, v in self.edges:
parent[u] = u
parent[v] = v
rank[u] = 0
rank[v] = 0
mst_weight = 0
mst_edges = []
for weight, u, v in self.edges:
if self.find(parent, u) != self.find(parent, v):
self.union(parent, rank, u, v)
mst_weight += weight
mst_edges.append((weight, u, v))
return mst_weight, mst_edges
# উদাহরণ ব্যবহার
g = Graph()
g.add_edge('A', 'B', 1)
g.add_edge('A', 'C', 3)
g.add_edge('B', 'C', 1)
g.add_edge('B', 'D', 4)
g.add_edge('C', 'D', 2)
mst_weight, mst_edges = g.kruskal_mst()
print(f"Minimum Spanning Tree Weight: {mst_weight}")
print("Edges in MST:", mst_edges)
সারসংক্ষেপ
- মিনিমাম স্প্যানিং ট্রি (MST) একটি গুরুত্বপূর্ণ সমস্যা, যা বিভিন্ন অ্যালগরিদম ব্যবহার করে সমাধান করা হয়, যেমন প্রিমের এবং ক্রুস্কাল-এর অ্যালগরিদম।
- প্রিমের অ্যালগরিদম: স্থানীয়ভাবে সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করে MST তৈরি করে।
- ক্রুস্কাল-এর অ্যালগরিদম: সমস্ত প্রান্তগুলোকে সাজিয়ে রেখে সাইকেল তৈরি না হওয়া নিশ্চিত করে MST তৈরি করে।
মিনিমাম স্প্যানিং ট্রির এই অ্যালগরিদমগুলো নেটওয়ার্ক ডিজাইন, কম্পিউটার নেটওয়ার্কিং, এবং টেলিকমিউনিকেশন সিস্টেমে প্রয়োগ হয়।
