গ্রিডি অ্যালগরিদম৮ মিনিট পড়া

এমএসটি (MST) — গ্রিডি দৃষ্টিভঙ্গি (Greedy Lens)

সবচেয়ে কম রাস্তা ব্যবহার করে সব শহর সংযুক্ত করুন — সবসময় সবচেয়ে সস্তা রাস্তাটি নিন যা কোনো লুপ তৈরি করে না
Kruskal:\(O(E \log E)\)Prim (binary heap):\(O(E \log V)\)Prim (Fibonacci heap):\(O(E + V \log V)\)

কল্পনা করুন আপনি একজন সিটি প্ল্যানার বা নগর পরিকল্পনাকারী এবং আপনাকে ১০টি দূরবর্তী শহরকে রাস্তা দিয়ে যুক্ত করতে হবে। প্রতিটি সম্ভাব্য রাস্তা তৈরির একটি নির্দিষ্ট খরচ আছে। আপনি চান প্রতিটি শহর অন্য প্রতিটি শহরের সাথে যুক্ত থাকুক (সরাসরি বা অন্য শহরের মাধ্যমে), এবং আপনি চান সব মিলিয়ে আপনার মোট খরচ যেন সর্বনিম্ন হয়। আপনি কী করবেন?

খুব সহজ নিয়ম: সবসময় সেই রাস্তাটিই আগে তৈরি করুন যা সবচেয়ে সস্তা এবং যা কোনো ক্লোজড লুপ বা চক্র তৈরি করে না। লুপ থাকার মানে হলো আপনি একই সংযোগের জন্য বাড়তি টাকা খরচ করছেন। সবগুলো শহর একে অপরের সাথে যুক্ত না হওয়া পর্যন্ত এভাবে রাস্তা যোগ করতে থাকুন। এটিই আপনাকে দেবে আপনার কাঙ্ক্ষিত মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree) — যা হলো শহরের সর্বনিম্ন ব্যয়ের নেটওয়ার্ক।

স্প্যানিং ট্রি কী?

V সংখ্যক ভার্টেক্স বা শহর বিশিষ্ট কোনো একটি সংযুক্ত গ্রাফের স্প্যানিং ট্রি-তে ঠিক V − ১ টি এজ বা রাস্তা থাকে এবং এটি কোনো চক্র ছাড়াই সবগুলো ভার্টেক্সকে যুক্ত করে। আর মিনিমাম স্প্যানিং ট্রি (MST) হলো সেই স্প্যানিং ট্রি যার সবগুলো এজের মোট ওজন বা খরচ সর্বনিম্ন। যখন সবগুলো এজের ওজন ভিন্ন ভিন্ন হয়, তখন পুরো গ্রাফের জন্য একটি মাত্র অনন্য এমএসটি থাকে।

কাট প্রোপার্টি (Cut Property) — গ্রিডি কেন সঠিক

এমএসটি তৈরির সব অ্যালগরিদম আসলে একটি থিওরেমের ওপর ভিত্তি করে কাজ করে: কাট প্রোপার্টি।

একটি কাট (cut) হলো ভার্টেক্সগুলোকে দুটি অস্বচ্ছ বা নন-এম্পটি গ্রুপ S এবং V\S এ বিভাজন করা। কাট প্রোপার্টি বলে: যেকোনো কাটের বিপরীত পাশে থাকা এজগুলোর মধ্যে যেটির ওজন সবচেয়ে কম, সেটি অবশ্যই কোনো না কোনো এমএসটি-র অংশ হবে।

কেন? ধরুন সবচেয়ে হালকা এজ e এমএসটি-তে নেই। কিন্তু এমএসটি যেহেতু S এবং V\S কে যুক্ত করে রাখতে হবে, তাই অন্য কোনো একটি এজ e' অবশ্যই কাটটি অতিক্রম করেছে। কিন্তু e' এর ওজন e এর থেকে বেশি। এখন যদি আপনি e' কে e দিয়ে বদলে দেন — তবে আপনি আগের চেয়েও হালকা একটি স্প্যানিং ট্রি পাবেন, যা এমএসটি-র সংজ্ঞার (সর্বনিম্ন ওজন) পরিপন্থী। তার মানে আমাদের অনুমান ভুল ছিল।

ক্রুশকাল (Kruskal) এবং প্রিম (Prim) — উভয় অ্যালগরিদমই আসলে বিভিন্নভাবে এই কাট প্রোপার্টিকে বারবার প্রয়োগ করার একেকটি মাধ্যম মাত্র।

ক্রুশকাল অ্যালগরিদম (Kruskal's Algorithm)

১. সব এজকে তাদের ওজন অনুযায়ী ছোট থেকে বড় ক্রমে সাজান।
২. ক্রম অনুযায়ী এজগুলোর মধ্য দিয়ে যান। প্রতিটি এজ (u, v) এর জন্য:
• যদি u এবং v ভিন্ন দুটি কম্পোনেন্ট বা অংশে থাকে → তবে এই এজটি যুক্ত করুন (এটিই হলো সেই হালকা এজ যা তাদের কম্পোনেন্টের মধ্যবর্তী কাট পার করে দিচ্ছে)।
• যদি u এবং v আগে থেকেই যুক্ত থাকে → তবে এটি এড়িয়ে যান (এটি যুক্ত করলে চক্র তৈরি হবে)।
৩. ভি − ১ টি এজ যুক্ত হয়ে গেলে থেমে যান।

চক্র শনাক্ত করাই হলো এখানকার মূল চ্যালেঞ্জ। ইউনিয়ন-ফাইন্ড (Union-Find) এই কাজটি প্রতি এজের জন্য প্রায় \(O(1)\) সময়ে করে দেয়: শুধু পরীক্ষা করুন find(u) == find(v) কিনা। সমান হলে বাদ দিন, আর সমান না হলে এজটি যুক্ত করে union(u, v) করুন।

মোট খরচ: \(O(E \log E)\) শুধুমাত্র সর্টিংয়ের জন্য — ইউনিয়ন-ফাইন্ড অপারেশনগুলোতে সময় প্রায় লাগে না বললেই চলে।

প্রিম অ্যালগরিদম (Prim's Algorithm)

১. যেকোনো একটি ভার্টেক্স থেকে শুরু করুন। এটিকে ক্রমবর্ধমান টি (T) বা গাছের মধ্যে রাখুন।
২. T থেকে বের হচ্ছে এমন সব এজের (একটি প্রান্ত T-তে এবং অন্যটি বাইরে) একটি মিন-হিপ (min-heap) বা তালিকা রাখুন।
৩. বারবার সেই তালিকা থেকে সবচেয়ে হালকা এজ (u, v) বের করুন যেখানে v এখনো T-তে নেই। v-কে এবং এজটিকে T-তে যুক্ত করুন। v থেকে নতুন বের হওয়া সব এজ হিপে পুশ করুন।
৪. সব ভার্টেক্স T-তে আসা পর্যন্ত এটি চালিয়ে যান।

এটি প্রতি ধাপে S = বর্তমান গাছ T ধরে কাট প্রোপার্টির প্রয়োগ করে। T থেকে বাইরে যাওয়ার জন্য সবচেয়ে হালকা এজটি সব সময়ই নিরাপদ।

বাইনারি হিপের সাথে খরচ: \(O(E \log V)\)। ফিবোনাচি হিপের সাথে: \(O(E + V \log V)\) — তবে ফিবোনাচি হিপ ইমপ্লিমেন্ট করা বেশ জটিল।

কখন কোনটি ব্যবহার করবেন

ক্রুশকাল কোড করা বেশ সহজ এবং এটি স্পার্স বা হালকা গ্রাফে (যেখানে E এবং V কাছাকাছি) খুব ভালো কাজ করে। অন্যদিকে, ডেন্স বা ঘন গ্রাফের জন্য (যেখানে E এবং V^2 কাছাকাছি) এডজাসেন্সি ম্যাট্রিক্স ব্যবহার করে প্রিম চালানো ভালো কারণ এতে সব এজ সর্ট করার ঝামেলা থাকে না। কম্পিটিটিভ প্রোগ্রামিংয়ে অধিকাংশ এমএসটি সমস্যার জন্য ক্রুশকাল + ইউনিয়ন-ফাইন্ডই মূলত প্রথম পছন্দ।

দ্রষ্টব্য: উভয় অ্যালগরিদমই আসলে একই গ্রিডি আইডিয়া ভিন্নভাবে উপস্থাপন করে: ক্রুশকাল পুরো গ্রাফের যেকোনো স্থানে যেটির সস্তা এবং নিরাপদ সেটি নিয়ে কাজ করে; আর প্রিম একটি নির্দিষ্ট গাছ থেকে শুরু করে এক এক করে ভার্টেক্স বাড়িয়ে সামনে এগোয়। উভয়ই কাট প্রোপার্টি দ্বারা প্রমাণিত।

ক্রুশকালের এমএসটি — সর্টিং + ইউনিয়ন-ফাইন্ড

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()
    parent = list(range(n))
    rank = [0] * n


    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x


    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        if rank[ra] < rank[rb]: ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1
        return True


    mst_weight = 0
    mst_edges = []
    for w, u, v in edges:
        if union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
    return mst_weight, mst_edges


# Graph: 4 vertices (0-3), edges as (weight, u, v)
edges = [(1,0,1),(2,0,2),(3,1,2),(4,1,3),(5,2,3)]
weight, mst = kruskal(4, edges)
print(f"MST weight: {weight}")
for u, v, w in mst:
    print(f"  {u} -- {v}  (weight {w})")
Output
MST weight: 7
  0 -- 1  (weight 1)
  0 -- 2  (weight 2)
  1 -- 3  (weight 4)

Complexity

🗂️ ক্রুশকাল — এজ সর্টিং
মূল খরচ। উল্লেখ্য যে: \(O(E \log E)\) = \(O(E \log V)\) যেহেতু E ≤ \(V^2\)
E সংখ্যক এজ সর্ট করা \(O(E \log E)\)
⚡ ক্রুশকাল — ইউনিয়ন-ফাইন্ড অপারেশন
α হলো ইনভার্স আকেরম্যান ফাংশন (inverse Ackermann function) — কার্যকরভাবে প্রতিটি অপারেশনের জন্য \(O(1)\)
প্রতিটিতে প্রায় ধ্রুবক বা কন্সট্যান্ট \(O(E · α(V)\))
🌲 প্রিম — বাইনারি হিপ
প্রতিটি এজ হিপে সর্বোচ্চ একবার ডিক্রিজ-কী (decrease-key) ট্রিগার করে
হালকা বা মাঝারি গ্রাফের জন্য \(O(E \log V)\)
🚀 প্রিম — ফিবোনাচি হিপ
ডিক্রিজ-কী এখানে অ্যামর্টাইজড \(O(1)\) সময়ে হয়; জটিলতার কারণে বাস্তবে খুব কমই ব্যবহৃত হয়
তাত্ত্বিকভাবে সর্বোচ্চ গতি \(O(E + V \log V)\)
📐 এমএসটি আউটপুট সাইজ
V সংখ্যক ভার্টেক্স বিশিষ্ট যেকোনো স্প্যানিং ট্রিতে ঠিক V − ১ টি এজ থাকে
সর্বদা V − ১ টি এজ \(O(V)\)

ছোট কুইজ

কাট প্রোপার্টি (Cut property) কী এবং কেন এটি এমএসটি অ্যালগরিদমগুলো সঠিক হওয়ার নিশ্চয়তা দেয়?

পড়া চালিয়ে যান