মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)

মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree - MST) হলো একটি গ্রাফের বিশেষ একটি সাবগ্রাফ যা সকল ভেরটেক্সকে অন্তর্ভুক্ত করে এবং তার এজগুলোর মোট ওজন সর্বনিম্ন। এটি একটি সংযুক্ত (Connected) এবং অপ্রতিনিধিত্বমূলক (Acyclic) গ্রাফ তৈরি করে, যেখানে কোন সাইকেল থাকে না। MST বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়, যেমন নেটওয়ার্ক ডিজাইন, রাস্তার পরিকল্পনা, এবং গাছের কাঠামো তৈরি করার জন্য।

মিনিমাম স্প্যানিং ট্রির বৈশিষ্ট্য:

1. সংযুক্ত গ্রাফ: MST-এ সকল ভেরটেক্স অন্তর্ভুক্ত থাকে এবং এটি একটি সংযুক্ত গ্রাফ হয়।
2. অপ্রতিনিধিত্বমূলক: MST-তে কোন সাইকেল নেই; অর্থাৎ, এটি একটি গাছ (Tree)।
3. কম ওজন: MST-তে যে সমস্ত এজ থাকে, তাদের মোট ওজন সর্বনিম্ন হয়।

মিনিমাম স্প্যানিং ট্রি তৈরি করার অ্যালগরিদম

MST তৈরি করার জন্য প্রধানত দুটি অ্যালগরিদম ব্যবহৃত হয়:

১. প্রাইম'স অ্যালগরিদম (Prim’s Algorithm)

প্রাইম'স অ্যালগরিদম একটি পদ্ধতি যা একটি শুরু নোড থেকে শুরু করে পর্যায়ক্রমে গ্রাফের নিকটতম নোডের এজগুলি বেছে নিয়ে MST তৈরি করে।

কাজের ধাপ:

1. একটি সূচনালগ্ন নোড নির্বাচন করুন এবং সেটিকে MST-তে যুক্ত করুন।
2. বর্তমান MST-তে নিকটতম নোডের এজ নির্বাচন করুন এবং নতুন নোডকে MST-তে যুক্ত করুন।
3. এই প্রক্রিয়া পুনরাবৃত্তি করুন যতক্ষণ না সব নোড যুক্ত হয়।

টাইম কমপ্লেক্সিটি: O(E log V) (যেখানে E হল এজের সংখ্যা এবং V হল ভেরটেক্সের সংখ্যা)।

প্রাইম'স অ্যালগরিদমের উদাহরণ:

import heapq

def prims_algorithm(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]  # (weight, vertex)

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)

        if vertex not in visited:
            visited.add(vertex)
            mst.append((weight, vertex))

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

    return mst

# উদাহরণ গ্রাফ
graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'D': 4, 'C': 2},
    'C': {'A': 3, 'B': 2, 'D': 5},
    'D': {'B': 4, 'C': 5}
}

print(prims_algorithm(graph, 'A'))

২. ক্রুসকাল'স অ্যালগরিদম (Kruskal’s Algorithm)

ক্রুসকাল'স অ্যালগরিদম সমস্ত এজকে তাদের ওজনের উপর ভিত্তি করে সাজিয়ে গ্রাফের MST তৈরি করে। এটি ইউনিয়ন-ফাইন্ড পদ্ধতি ব্যবহার করে সাইকেল প্রতিরোধ করে।

কাজের ধাপ:

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

টাইম কমপ্লেক্সিটি: O(E log E) বা O(E log V)।

ক্রুসকাল'স অ্যালগরিদমের উদাহরণ:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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 kruskals_algorithm(graph):
    edges = [(weight, u, v) for u in graph for v, weight in graph[u].items()]
    edges.sort()  # Sort edges by weight
    disjoint_set = DisjointSet(len(graph))
    mst = []

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

    return mst

# উদাহরণ গ্রাফ
graph = {
    0: {1: 10, 2: 6, 3: 5},
    1: {0: 10, 3: 15},
    2: {0: 6, 3: 4},
    3: {0: 5, 1: 15, 2: 4}
}

print(kruskals_algorithm(graph))

মিনিমাম স্প্যানিং ট্রির ব্যবহার:

1. নেটওয়ার্ক ডিজাইন: কম্পিউটার নেটওয়ার্ক বা যোগাযোগ নেটওয়ার্ক ডিজাইন করতে।
2. রাস্তার পরিকল্পনা: শহরের রাস্তা পরিকল্পনায় কার্যকর।
3. বিদ্যুৎ বিতরণ: বিদ্যুৎ লাইন স্থাপন করার সময় মিনিমাম কেবল ব্যবহারের জন্য।
4. গ্রাফিক্স: গ্রাফিক্সের জন্য চিত্র এবং জাল তৈরি করতে।

উপসংহার

মিনিমাম স্প্যানিং ট্রি গ্রাফ থিওরি ও অ্যাপ্লিকেশনগুলির একটি গুরুত্বপূর্ণ অংশ। প্রাইম'স এবং ক্রুসকাল'স অ্যালগরিদমগুলি খুবই জনপ্রিয় এবং কার্যকরী MST তৈরি করার জন্য ব্যবহৃত হয়। বিভিন্ন ক্ষেত্রে এই অ্যালগরিদমগুলির ব্যবহার একটি কার্যকর এবং অর্থনৈতিক সমাধান প্রদান করে।

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 এজগুলোর ভিত্তিতে কাজ করে। নির্বাচনের প্রক্রিয়া এবং টাইম কমপ্লেক্সিটিও তাদের মধ্যে পার্থক্য সৃষ্টি করে। বিভিন্ন সমস্যার জন্য উভয় অ্যালগরিদমই কার্যকর।

মিনিমাম স্প্যানিং ট্রি (MST)

মিনিমাম স্প্যানিং ট্রি (MST) হলো একটি সংযুক্ত ওজনযুক্ত গ্রাফের একটি উপগ্রাফ যা সমস্ত নোডকে সংযুক্ত করে এবং এর মোট ওজন সর্বনিম্ন হয়। এটি বিভিন্ন বাস্তব জীবনের অ্যাপ্লিকেশন যেমন নেটওয়ার্ক ডিজাইন, রুটিং, এবং ক্লাস্টারিংয়ের জন্য গুরুত্বপূর্ণ।

MST এর প্রধান অ্যালগরিদম

1. প্রিমের অ্যালগরিদম (Prim's Algorithm)
2. ক্রুস্কাল-এর অ্যালগরিদম (Kruskal's Algorithm)

এখন এই অ্যালগরিদম দুটি সম্পর্কে বিস্তারিত আলোচনা করা যাক।

১. প্রিমের অ্যালগরিদম

প্রিমের অ্যালগরিদম একটি প্রক্রিয়া যার মাধ্যমে একটি নোড থেকে শুরু করে MST তৈরি করা হয়। এটি কেবলমাত্র সেই প্রান্তগুলি বিবেচনা করে যা বর্তমানে MST-তে নেই এবং MST-তে যুক্ত করার জন্য সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করে।

অ্যালগরিদমের পদক্ষেপ:

1. একটি শুরু নোড চয়ন করুন।
2. MST-তে নোড যোগ করুন এবং তাদের সংযুক্ত প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্ত চয়ন করুন।
3. নোড যোগ করতে থাকুন যতক্ষণ না সব নোড 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 তৈরির প্রক্রিয়া সম্পন্ন করে। এটি সেই প্রান্তগুলো চয়ন করে, যেগুলো সাইকেল তৈরি করে না।

অ্যালগরিদমের পদক্ষেপ:

1. সমস্ত প্রান্তগুলোকে ওজন অনুসারে সাজান।
2. ছোট থেকে বড় প্রান্তগুলো নির্বাচন করতে থাকুন, যতক্ষণ না MST পূর্ণ হয়।
3. সাইকেল তৈরি হচ্ছে কিনা তা নিশ্চিত করতে ইউনিয়ন-ফাইন্ড (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 তৈরি করে।

মিনিমাম স্প্যানিং ট্রির এই অ্যালগরিদমগুলো নেটওয়ার্ক ডিজাইন, কম্পিউটার নেটওয়ার্কিং, এবং টেলিকমিউনিকেশন সিস্টেমে প্রয়োগ হয়। 

ইউনিয়ন-ফাইন্ড অ্যালগরিদম (Union-Find Algorithm) বা ডিসজন্ট সেট (Disjoint Set) ডেটা স্ট্রাকচার হল এমন একটি পদ্ধতি যা বিভিন্ন উপাদানের মধ্যে সংগঠন এবং সংযুক্তির কার্যকরী পরিচালনা করতে ব্যবহৃত হয়। এটি সাধারণত গ্রাফের বিভিন্ন সমস্যা সমাধানে ব্যবহৃত হয়, বিশেষত যেগুলি সংযোগ বা গঠনের সাথে সম্পর্কিত।

ইউনিয়ন-ফাইন্ডের মূল কাজ

ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার প্রধানত দুটি মৌলিক কাজ সমর্থন করে:

1. ফাইন্ড (Find): একটি উপাদানের রুট প্রতিনিধির সন্ধান করা। এটি যাচাই করে যে কোনও দুটি উপাদান একই গোষ্ঠীর অংশ কিনা।
2. ইউনিয়ন (Union): দুটি উপাদানকে একত্রিত করে একটি নতুন গোষ্ঠী তৈরি করা।

ডেটা স্ট্রাকচারের গঠন

ইউনিয়ন-ফাইন্ড সাধারণত দুটি মূল উপাদানের সাহায্যে তৈরি হয়:

1. রুট পয়েন্ট: প্রতিটি উপাদানের একটি রুট পয়েন্ট থাকে যা তার গোষ্ঠীর প্রতিনিধিত্ব করে।
2. র‍্যাঙ্ক (Rank): প্রতিটি গোষ্ঠীর উচ্চতার ভিত্তিতে গঠন করে যাতে ইউনিয়ন অপারেশনগুলি কার্যকরী হয়।

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

প্রাথমিককরণ: প্রতিটি উপাদানকে একটি স্বতন্ত্র গোষ্ঠীতে রাখুন, অর্থাৎ, প্রতিটি উপাদানের রুট পয়েন্ট হল সে নিজেই।

ফাইন্ড অপারেশন: একটি উপাদানের রুট পয়েন্ট খুঁজতে হলে, প্রাথমিকভাবে নিজে থেকে শুরু করে তার রুট পর্যন্ত চলে যান। এই প্রক্রিয়াতে পাথ কম্প্রেশন (Path Compression) ব্যবহার করা যেতে পারে, যেখানে সমস্ত মধ্যবর্তী নোডের রুটকে সরাসরি রুট পয়েন্টের সাথে সংযুক্ত করা হয়।

ইউনিয়ন অপারেশন: দুইটি উপাদান একত্রিত করতে, তাদের রুট পয়েন্ট খুঁজে বের করুন এবং নিম্ন র্যাঙ্কের গোষ্ঠীকে উচ্চ র্যাঙ্কের গোষ্ঠীর অধীনে সংযুক্ত করুন। এতে গোষ্ঠীটি সঠিকভাবে গঠিত হয় এবং গঠনটি ভারসাম্য বজায় রাখে।

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

• ফাইন্ড অপারেশন: \( O(\alpha(n)) \)
• ইউনিয়ন অপারেশন: \( O(\alpha(n)) \)

এখানে \( \alpha(n) \) হল ইনভার্সিড অ্যাক্সিস ফাংশন, যা খুব দ্রুত বৃদ্ধি পায় এবং তাই প্রায় ধ্রুবক হিসাবে বিবেচিত হয়।

ব্যবহার

ইউনিয়ন-ফাইন্ড অ্যালগরিদমের বিভিন্ন ব্যবহার রয়েছে, যেমন:

1. গ্রাফের সংযোগ পরীক্ষা: গ্রাফে দুইটি নোড সংযুক্ত কিনা তা যাচাই করতে ব্যবহার করা হয়।
2. ক্লাস্টারিং: বিভিন্ন ডেটা পয়েন্টকে একটি একক গ্রুপ বা ক্লাস্টারে সংযুক্ত করতে।
3. মিনিমাম স্প্যানিং ট্রি: ক্রুস্কাল অ্যালগরিদমের মতো অ্যালগরিদমে, যেখানে একটি গ্রাফের মিনিমাম স্প্যানিং ট্রি তৈরি করতে হয়।
4. ইনভলভমেন্ট ডিটেকশন: সামাজিক নেটওয়ার্ক বা অন্যান্য সিস্টেমে ব্যক্তি বা উপাদানের সংযোগ নির্ণয়ে।

উদাহরণ

ধরা যাক, আমাদের একটি গ্রাফে 5টি নোড (0 থেকে 4) রয়েছে।

প্রাথমিককরণ: প্রতিটি নোড আলাদা গোষ্ঠীতে রয়েছে।

0  1  2  3  4

ইউনিয়ন অপারেশন: 0 এবং 1 যুক্ত করুন।

0-1 2  3  4

ফাইন্ড অপারেশন: 1 এর রুট খুঁজুন, যা 0 হবে।

আরেকটি ইউনিয়ন: 3 এবং 4 যুক্ত করুন।

0-1 2  3-4

অবশেষে, 1 এবং 4 এর মধ্যে সংযোগ: 1 এবং 4 এর জন্য ফাইন্ড চালান, তারা সংযুক্ত কিনা যাচাই করুন।

উপসংহার

ইউনিয়ন-ফাইন্ড অ্যালগরিদম একটি কার্যকর এবং গুরুত্বপূর্ণ ডেটা স্ট্রাকচার, যা গ্রাফ এবং নেটওয়ার্ক সমস্যায় অত্যন্ত উপকারী। এর সহজতম কার্যকারিতা এবং দ্রুত গতির জন্য, এটি বিভিন্ন কম্পিউটার বিজ্ঞান এবং বাস্তব জীবনের সমস্যা সমাধানে ব্যাপকভাবে ব্যবহৃত হয়।