মিনিমাম স্প্যানিং ট্রি(prim’s mst)
গ্রাফ থিওরি অ্যালগোরিদমের একটি খুবই গুরুত্বপূর্ণ অংশ। গ্রাফের সাহায্যে আমরা বাস্তব জীবনের অনেক সমস্যাকে মডেলিং করতে পারি তাই প্রবলেম সলভারদের জন্য গ্রাফ থিওরি জানা অপরিহার্য।
আমরা আজকে দেখবো কিভাবে একটি গ্রাফের মিনিমাম স্প্যানিং ট্রি নির্ণয় করা যায়। লেখাটি পড়ার জন্য পাঠকদের গ্রাফ থিওরি নিয়ে বেসিক কিছু জ্ঞান থাকলে ভালো হয়। প্রোগ্রামিং কনটেস্টেন্ট এবং কম্পিউটার বিজ্ঞানের শিক্ষার্থীদের জন্য এ লেখাটি বেশি কাজে লাগলেও বাকিদেরও অনুরোধ করবো কষ্ট করে একবার পড়ে ফেলতে,তাহলে কম্পিউটার বিজ্ঞানে আসলে কি ধরণের জিনিস পড়ানো হয় সেটা জানতে পারবেন। গ্রাফ থিওরির একদম গোড়া থেকে শুরু করতে চাইলে এখানে ক্লিক করুন।
একটি গ্রাফ থেকে কয়েকটি নোড আর এজ নিয়ে নতুন একটি গ্রাফ তৈরি করা হলে সেটাকে বলা হয় সাবগ্রাফ। স্প্যানিং ট্রি হলো এমন একটি সাবগ্রাফ যেটায়:
* মূল গ্রাফের সবগুলো নোড আছে।
* সাবগ্রাফটি একটি ট্রি। আমরা ট্রিতে কখনো সাইকেল থাকেনা,edge থাকে n-1 টি যেখানে n হলো নোড সংখ্যা।
একটি গ্রাফের অনেকগুলো স্প্যানিং ট্রি থাকতে পারে,যে ট্রি এর edge গুলোর weight যোগফল সব থেকে কম সেটাই মিনিমাম স্প্যানিং ট্রি।
(n টি নোডকে সর্বনিম্ন n-1 টি edge দিয়ে একসাথে যুক্ত করা সম্ভব,তাই n-1 টির বেশি এজ আমরা নিবোনা)
মনে করি নিচের গ্রাফের প্রতিটি নোড হলো একটি করে বাড়ি। আমাদের বাড়িগুলোর মধ্যে টেলিফোন লাইন বসাতে হবে। আমরা চাই সবথেকে কম খরচে লাইন বসাতে। edge গুলোর weight লাইন বসানোর খরচ নির্দেশ করে:
আমরা অনেক ভাবে লাইন বসাতে পারতাম। ছবিতে লাল এজ দিয়ে টেলিফোন লাইন বসানোর একটি উপায় দেখানো হয়েছে। টেলিফোন লাইনগুলো একটি সাবগ্রাফ তৈরি করেছে যেটায় অবশ্যই n-1 টি এজ আছে,কোনো সাইকেল নেই কারণ অতিরিক্ত edge বসালে আমাদের খরচ বাড়বে,কোনো লাভ হবেনা। মিনিমাম স্প্যানিং ট্রি বের করার সময় আমরা এমন ভাবে এজগুলো নিবো যেন তাদের weight এর যোগফল মিনিমাইজ হয়।
এখন নিচের গ্রাফ থেকে কিভাবে আমরা mst বের করব?
আমরা prim's অ্যালগোরিদম ব্যবহার করে mst নির্ণয় করবো।
আমরা প্রথমে যেকোনো একটি সোর্স নোড নিব। ধরি সোর্স হলো ১। ১ থেকে যতগুলো এজ আছে সেগুলোর মিনিমাম টিকে আমরা সাবগ্রাফে যোগ করব। নিচের ছবিতে নীল এজ দিয়ে বুঝানো হচ্ছে এজটি সাবগ্রাফে যুক্ত করা হয়েছে:
এবার সোর্স ১ এবং ৫ নম্বর নোড থেকে মোট যত এজ আছে(আগের এজগুলো সহ) তাদের মধ্যে মিনিমাম টি নিব:
এবার নিব ১,২ এবং ৫ নম্বর নোড থেকে মোট যত এজ আছে(আগের এজগুলো সহ) তাদের মধ্যে মিনিমাম:
পরের ধাপটি গুরুত্বপূর্ণ। ১,২,৫,৪ থেকে যত এজ আছে তাদের মধ্য মিনিমাম হলো ২-৪, কিন্তু ২ নম্বর নোড এবং ৪ নম্বর নোড দুইটাই অলরেডি সাবগ্রাফের অংশ,তারা আগে থেকেই কানেক্টেড,এদের যোগ করলে সাবগ্রাফে সাইকেল তৈরি হবে,তাই ২-৪ এজটি নিয়ে আমাদের কোনো লাভ হবেনা। আমরা এমন প্রতিবার এজ নিব যেন নতুন আরেকটি নোড সাবগ্রাফে যুক্ত হয়। তাহলে ৪-৮ হবে আমাদের পরের চয়েস।
এভাবে শেষ পর্যন্ত আমরা পাবো:
নীলরং এর এই সাবগ্রাফটাই আমাদের মিনিমাম স্প্যানিং ট্রি। বাকি এজগুলো মুছে দিলে থাকে:
তাহলে টেলিফোন লাইন বসাতো মোট খরচ: ৪+২+৫+১১+৯+২+১=৩৪। একটি গ্রাফে অনেকগুলো মিনিমাম স্প্যানিং ট্রি থাকতে পারে,তাই অনলাইন জাজে mst সংক্রান্ত প্রবলেম অনেক ক্ষেত্রেই special judge দিয়ে কাজ করে,অর্থাত সঠিক আউটপুটগুলোর যেকোনো একটা প্রিন্ট করলেই চলে।
আমাদের সুডোকোড হবে এরকম:
* Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
* Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
* Repeat until Vnew = V:
o Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not
(if there are multiple edges with the same weight, any of them may be picked)
o Add v to Vnew, and (u, v) to Enew
* Output: Vnew and Enew describe a minimal spanning tree
(Wiki)এখন মাথায় প্রশ্ন আসতে পারে কি ভাবে prim's mst ইম্প্লিমেন্ট করব? বারবার লুপ চালিয়ে naive অ্যাপ্রোচে কোড লিখলে তোমার কোড টাইম লিমিটের মধ্যে রান না করার সম্ভাবনাই বেশি।
আমাদের সমস্যার সমাধান হলো "priority queue"। আশা করি এই ডাটা স্ট্রাকচারটি সম্পর্কে সবাই জানেন। প্রতিটি নোড ভিজিট করার সাথে সাথে নতুন এজগুলোকে priority queue তে ঢুকিয়ে রাখবেন। priority queue তে এজগুলোকে weight অনুযায়ী সর্টেড রাখবে। তাহলে প্রতিবার queue এর top এ পাবে এখন পর্যন্ত নেয়া নোডগুলো থেকে বের হওয়া সবথেকে কম weight এর এজ,সেটাকে সাবগ্রাফে যোগ করবেন।
mst নির্ণয়ের জন্য আরেকটি অ্যালগোরিদম আছে যা kruskal's mst নামে পরিচিত যা কন্টেস্টেন্টদের মধ্যে বেশি জনপ্রিয়। kruskal শিখতে হলে আপনাকে disjoint set(union find) নামের একটি চমৎকার data structure এর সাথে অবশ্যই পরিচিত হতে হবে। তারপর kruskal's mst শেখা খুব সহজ হবে, prim's শিখলেও kruskal অবশ্যই শিখতে হবে। disjoint set শেখার জন্য নিচের টিউটোরিয়ালগুলো দেখতে পারেন:
আমার লেখা টিউটোরিয়াল
topcoder tutorial
Wikipedia
Coreman's introduction to algorithm
mst নিয়ে uva অনলাইন জাজে অনেক প্রবলেম আছে। অ্যালগোরিদমটা implement করার পর অবশ্যই নিচের সমস্যা গুলো সমাধানের চেষ্টা করবেন, আবারো বলবো প্রবলেম সল্ভ না করলে অ্যালগোরিদম শেখা অর্থহীন কারণ মাথা খাটিয়ে প্রবলেম সলভিং হলো স্কিল ডেভেলপ করার সব থেকে ভালো উপায়।
http://uva.onlinejudge.org/external/5/544.html(Straight forward)
http://uva.onlinejudge.org/external/9/908.html
http://uva.onlinejudge.org/external/100/10034.html(Straight forward)
http://uva.onlinejudge.org/external/104/10462.html(2nd best mst)
শাফায়েত
সিএসই,ঢাকা বিশ্ববিদ্যালয়।
