গ্রাফপড়তে ৬ মিনিট লাগবে

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

সবচেয়ে কম খরচে রাস্তা বানিয়ে সবগুলো শহরকে এক সুতোয় গাঁথা
Kruskal's: O(E log E)Prim's: O(E log V)space: O(V)

ধরুন আপনি একটা দেশের প্রধান ইঞ্জিনিয়ার। আপনার হাতে V-সংখ্যক শহর আছে এবং এই শহরগুলোর মধ্যে রাস্তা বানানোর জন্য E-সংখ্যক সম্ভাব্য প্ল্যান আছে। প্রতিটা রাস্তা বানানোর আলাদা আলাদা খরচ আছে। আপনার লক্ষ্য হলো: সবগুলো শহরকে একে অপরের সাথে এমনভাবে যুক্ত করা যেন রাস্তা বানানোর মোট খরচ সবচেয়ে কম হয়। আর হ্যাঁ, কোনো অযথা রাস্তা বানানো যাবে না — অর্থাৎ এমনভাবে রাস্তা বানাতে হবে যেন কোনো সাইকেল বা বৃত্ত তৈরি না হয় (কারণ এক শহরে যানয়ার জন্য একটাই রাস্তা যথেষ্ট, দুই দিক দিয়ে যানয়ার দরকার নেই)।

এই প্ল্যানের ফাইনাল রেজাল্টটাই হলো একটা মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree বা MST): এটা এমন একটা ম্যাপ যেখানে ঠিক V-1 টা রাস্তা থাকে, যা সব শহরকে একসাথে জুড়ে দেয় এবং যার মোট খরচ হয় দুনিয়ার যেকোনো প্ল্যানের চেয়ে সবচেয়ে কম।

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

ক্রুসকালস অ্যালগরিদমের বুদ্ধিটা একদম সোজা বা গ্রিডি (greedy): সবচেয়ে কম খরচের রাস্তাটা আগে বানিন, তবে খেয়াল রেখো যেন কোনো সাইকেল বা লুপ তৈরি না হয়। প্রথমে সব রাস্তাগুলোকে তাদের খরচের ছোট থেকে বড় হিসেবে সাজানেন (sort) হয়। এরপর একটা একটা করে রাস্তা নেওয়া হয়; যদি রাস্তাটা বানালে লুপ তৈরি না হয়, তবে সেটাকে ম্যাপে ঢোকানো হয়, নাহলে বাদ দিয়ে পরের রাস্তায় যানয়া হয়।

কোনো লুপ তৈরি হচ্ছে কি না, সেটা চোখের পলকে (O(α(n)) স্পিডে) চেক করার দায়িত্ব নেয় ইউনিয়ন-ফাইন্ড (Union-Find) — যার ফলে ক্রুসকালস অ্যালগরিদম হয়ে ওঠে মারাত্মক এফিশিয়েন্ট বা দ্রুত।

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
function kruskal(cities, roads):
  সব রাস্তাকে তাদের খরচের ছোট থেকে বড় হিসেবে সাজান
  uf = UnionFind(cities)  // লুপ চেক করার জাদুকরী টুল
  mst = []


  for (cityA, cityB, cost) of roads:
    if find(cityA) !== find(cityB):  // লুপ বা সাইকেল নেই!
      union(cityA, cityB)
      mst.push((cityA, cityB, cost))
    if mst.length === cities.length - 1: break  // সব শহর জোড়া লেগে গেছে


  return mst

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

প্রিমস অ্যালগরিদম অন্য একটা বুদ্ধি কাটায়: সে একটা শহর থেকে শুরু করে তার চারপাশে একটু একটু করে জাল বা নেটওয়ার্ক বাড়াতে থাকে। যেকোনো একটা শহর দিয়ে কাজ শুরু হয়। এরপর ওই শহরের সাথে যুক্ত সবচেয়ে সস্তা রাস্তাটা খুঁজে বের করে নতুন একটা শহরকে জালে ঢোকানো হয়। এই 'সবচেয়ে সস্তা রাস্তা' খুব সহজে খুঁজে পাওয়ার জন্য একটা মিন-হিপ (min-heap) ব্যবহার করা হয়।

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function prim(graph, start):
  inMST = {start}  // কোন কোন শহর জালে ঢুকেছে তার হিসাব
  heap = start থেকে বের হওয়া রাস্তাগুলোর মিন-হিপ (cost, neighbor)
  mst = []


  while heap ফাঁকা নয় এবং inMST.size < V:
    (cost, city) = heap.pop()  // সবচেয়ে সস্তা রাস্তাটা নিন
    if city in inMST: continue // শহরটা আগে থেকেই জালে থাকলে কিছু কোরো না
    inMST.add(city)            // জালে ঢোকান
    mst.push(city)
    for (neighbor, weight) of graph[city]:
      if neighbor not in inMST:
        heap.push((weight, neighbor))  // নতুন রাস্তার অপশনগুলো হিপে ঢোকান


  return mst

কখন ক্রুসকালস আর কখন প্রিমস?

দুটো অ্যালগরিদমই সবসময় জেনুইন একটা MST বানাতে পারে। ক্রুসকালস (Kruskal's) বেশি ভালো কাজ করে ফাঁকা বা স্পার্স গ্রাফে (sparse graph, যেখানে রাস্তা কম থাকে) — কারণ রাস্তা কম থাকলে রাস্তার লিস্টকে সর্ট (sort) করতে সময় কম লাগে। অন্যদিকে প্রিমস (Prim's) বেশি ভালো কাজ করে ঘিঞ্জি বা অনেক রাস্তাওয়ালা ঘন গ্রাফে (dense graph) — কারণ হিপের ভেতরে শুধু জালের বর্ডারের বা সামনের দিকের রাস্তাগুলোই থাকে, সব রাস্তা একসাথে রাখতে হয় না।

◈ Watch MST grow

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

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

Complexity

ক্রুসকালস (Kruskal's)
রাস্তাগুলোকে ছোট থেকে বড় সর্ট করতেই বেশি সময় যায়
সর্টিং নির্ভর O(E log E)
প্রিমস (Prim's) হিপ দিয়ে
বর্ডারের রাস্তার জন্য হিপ বা কিউ মেইনটেইন করে
খুব ফাস্ট O(E log V)
জায়গা (Space)
ইউনিয়ন-ফাইন্ড বা ভিজিটেড সেটের (visited set) জন্য মেমোরি লাগে
লিনিয়ার O(V)
Challenge

ছোট কুইজ

ক্রুসকালস অ্যালগরিদম একটা নতুন রাস্তা ম্যাপে ঢোকাতে যাচ্ছে। সে ইউনিয়ন-ফাইন্ডকে জিজ্ঞেস করে জানতে পারল যে রাস্তার দুই প্রান্তের শহর দুটোরই লিডার বা রুট (root) একই। তখন সে কী করবে?

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

ইউনিয়ন-ফাইন্ড (Union-Find বা DSU)
কে কার বন্ধু সেটুকুই শুধু মনে রাখা — আর চোখের পলকে তাদের এক গ্রুপে মিলিয়ে দেওয়া
→
ডাইকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm)
গ্রাফের জিপিএস (GPS) — এক জায়গা থেকে বাকি সব জায়গায় যানয়ার সবচেয়ে সস্তা বা ছোট রাস্তা বের করা
→
গ্রাফ কীভাবে মেমোরিতে থাকে (Graph Representation)
শহর আর রাস্তার ম্যাপ কীভাবে কম্পিউটারের মাথায় ঢোকানো যায়
→