একটি গ্রাফ থেকে কয়েকটি নোড আর এজ নিয়ে নতুন একটি গ্রাফ তৈরি করা হলে সেটাকে বলা হয় সাবগ্রাফ। স্প্যানিং ট্রি হলো এমন একটি সাবগ্রাফ যেটায়:
* মূল গ্রাফের সবগুলো নোড আছে।
* সাবগ্রাফটি একটি ট্রি। ট্রিতে কখনো সাইকেল থাকেনা,এজ থাকে $n-1$ টি যেখানে $n$ হলো নোড সংখ্যা।
একটি গ্রাফের অনেকগুলো স্প্যানিং ট্রি থাকতে পারে,যে ট্রি এর এজ গুলোর কস্ট/ওয়েট এর যোগফল সব থেকে কম সেটাই মিনিমাম স্প্যানিং ট্রি। আমরা এই লেখায় প্রিম অ্যালগোরিদমের সাহায্যে মিনিমাম স্প্যানিং ট্রি বের করা শিখবো।
মনে করি নিচের গ্রাফের প্রতিটি নোড হলো একটি করে বাড়ি। আমাদের বাড়িগুলোর মধ্যে টেলিফোন লাইন বসাতে হবে। আমরা চাই সবথেকে কম খরচে লাইন বসাতে। এজ গুলোর ওয়েট লাইন বসানোর খরচ নির্দেশ করে:
আমরা অনেক ভাবে লাইন বসাতে পারতাম। ছবিতে লাল এজ দিয়ে টেলিফোন লাইন বসানোর একটি উপায় দেখানো হয়েছে। টেলিফোন লাইনগুলো একটি সাবগ্রাফ তৈরি করেছে যেটায় অবশ্যই $n-1$ টি এজ আছে,কোনো সাইকেল নেই কারণ অতিরিক্ত এজ বসালে আমাদের খরচ বাড়বে,কোনো লাভ হবেনা। মিনিমাম স্প্যানিং ট্রি বের করার সময় আমরা এমন ভাবে এজগুলো নিবো যেন তাদের এজ এর যোগফল মিনিমাইজ হয়।
এখন নিচের গ্রাফ থেকে কিভাবে আমরা মিনিমাম স্প্যানিং ট্রি বের করব?
গ্রিডি(greedy) অ্যাপ্রোচে খুব সহজে মিনিমাম স্প্যানিং ট্রি বের করা যায়। আমরা এখন প্রিমস অ্যালগোরিদম কিভাবে কাজ করে দেখব। তুমি যদি আগে ক্রুসকাল শিখতে চাও তাহলেও সমস্যা নেই, সরাসরি পরের পর্বে চলে যেতে পারো।
আমরা প্রথমে যেকোনো একটি সোর্স নোড নিব। ধরি সোর্স হলো ১। ১ থেকে যতগুলো এজ আছে সেগুলোর মিনিমাম টিকে আমরা সাবগ্রাফে যোগ করব। নিচের ছবিতে নীল এজ দিয়ে বুঝানো হচ্ছে এজটি সাবগ্রাফে যুক্ত করা হয়েছে:
এবার সোর্স ১ এবং ৫ নম্বর নোড থেকে মোট যত এজ আছে(আগের এজগুলো সহ) তাদের মধ্যে মিনিমাম টি নিব:
এবার নিব ১,২ এবং ৫ নম্বর নোড থেকে মোট যত এজ আছে(আগের এজগুলো সহ) তাদের মধ্যে মিনিমাম:
পরের ধাপটি গুরুত্বপূর্ণ। ১,২,৫,৪ থেকে যত এজ আছে তাদের মধ্য মিনিমাম হলো ২-৪, কিন্তু ২ নম্বর নোড এবং ৪ নম্বর নোড দুইটাই অলরেডি সাবগ্রাফের অংশ,তারা আগে থেকেই কানেক্টেড,এদের যোগ করলে সাবগ্রাফে সাইকেল তৈরি হবে,তাই ২-৪ এজটি নিয়ে আমাদের কোনো লাভ হবেনা। আমরা এমন প্রতিবার এজ নিব যেন নতুন আরেকটি নোড সাবগ্রাফে যুক্ত হয়। তাহলে ৪-৮ হবে আমাদের পরের চয়েস।
এরপর ৮-৬ যোগ করবো:
সবশেষে ৪-৩ যোগ করবো:
নীলরং এর এই সাবগ্রাফটাই আমাদের মিনিমাম স্প্যানিং ট্রি। বাকি এজগুলো মুছে দিলে থাকে:
তাহলে টেলিফোন লাইন বসাতো মোট খরচ: ৪ + ২ + ৫ + ১১ + ৯ + ২ + ১ = ৩৪। একটি গ্রাফে এক বা একাধিক মিনিমাম স্প্যানিং ট্রি থাকতে পারে।
আমাদের সুডোকোড হবে এরকম:
|
1 2 3 4 5 6 7 |
* 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 |
এখন মাথায় প্রশ্ন আসতে পারে কি ভাবে প্রিমস অ্যালগোরিদম ইম্প্লিমেন্ট করব? বারবার লুপ চালিয়ে নেইভ অ্যাপ্রোচে কোড লিখলে তোমার কোড টাইম লিমিটের মধ্যে রান না করার সম্ভাবনাই বেশি।
রানটাইম কমাতে প্রায়োরিটি কিউ ব্যবহার করতে পারো। যখন নতুন একটা নোড Vnew তে যোগ করছো তখন সেই নোডের অ্যাডজেসেন্ট সবগুলো এজ প্রায়োরিটি কিউতে ঢুকিয়ে রাখতে হবে। এখন প্রায়োরিটি কিউ থেকে সবথেকে মিনিমাম ওয়েটের এজটা লগারিদম কমপ্লেক্সিটিতে খুজতে পারবে। মোট কমপ্লেক্সিটি হবে $O(ElogE)$। তবে এজের বদলে কিউতে নোড পুশ করে $O(ElogV)$ তে কমপ্লেক্সিটি নামিয়ে আনা যায়, সেটা কিভাবে করা যায় চিন্তা করে বের করো।
অ্যালগোরিদমটা ইমপ্লিমেন্ট করার পর অবশ্যই নিচের সমস্যা গুলো সমাধানের চেষ্টা করবে।
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/112/11228.html
http://uva.onlinejudge.org/external/104/10462.html(2nd best mst)
spoj:
http://www.spoj.pl/problems/MST/(Straight forward)
মিনিমাম স্প্যানিং ট্রি বের করার জন্য আরেকটি অ্যালগোরিদম আছে যা ক্রুসকাল অ্যালগোরিদম নামে পরিচিত। পরের পর্বে আমরা সেটা শিখবো।
ফেসবুকে মন্তব্য
Powered by Facebook Comments
“priority queue ডিক্লেয়ার করে সেটায় ‘data’ টাইপের ভ্যারিয়েবল পুশ করলে Q তে অটোমেটিক সর্ট হয়ে যাবে।” …ভাইয়া এখানে একটু সমস্যা হচ্ছে ,একটু যদি ডিটেইলস লিখতেন যে কিভাবে data টাইপের stucture দিয়ে minimum priority queue তৈরি করতে হয়,খুব উপকার হত।আর আপনার পুরো কোড টা একটু দেখতে চাই…প্লিজ।
আপনাকে অভিবাদন এত সুন্দর একটা টিউটরিয়াল লেখার জন্য।
কোডে সামান্য ভুল আছে,return cost < p.cost; এর জায়গায় return cost > p.cost; হবে।
আমরা ইন্টিজার,ডাবলে সহজেই +,< ইত্যাদি অপারেটর ব্যবহার করতে পারি। কিন্তু স্ট্রাকচারগুলো কাস্টম ডাটাটাইপ,এগুলোর জন্য অপারেটর নিজে ডিফাইন করে দিতে হয়। struct data { int u,v,cost;}; ডাটা টাইপের দুটি ভ্যারিয়েবল তুমি তুলনা করবে কিভাবে? u,v বা cost এর ভিত্তিতে বা এ সবগুলোর ভিত্তিতে ছোট-বড় তুলনা করা যেতে পারে তবে তোমাকে সেটা ডিফাইন করে দিতে হবে। উপরের কোডে ঠিক এভাবেই ডিফাইন করা হয়েছে ওভারলোডিং এর মাধ্যমে,এ ক্ষেত্রে cost অনুযায়ী তুলনা করা হয়েছে। প্রায়োরিটি কিউ যখন তোমার ডাটা গুলোকে সর্ট করবে তখন সে "<" ব্যবহার করে তুলনা করবে,তাই আমরা "<" এর আচরণ ডিফাইন করে দিয়েছি। অনেক প্রোগ্রামার ওভারলোডিং এর বিরুদ্ধে কারণ কোড readability হারায়,এ কারণে জাভাসহ অনেক হাইলেভেল ল্যাংগুয়েজ এটি সাপোর্ট করেনা। উইকিতে একটা ছোট আর্টিকেল আছে,পুরোটা পড়ে ফেলো: http://en.wikipedia.org/wiki/Operator_overloading
ধন্যবাদ উত্তর দেয়ার জন্য । আরেকটা সমস্যায় পরেছি তা হচ্ছে…
“পরের ধাপটি গুরুত্বপূর্ণ। ১,২,৫,৪ থেকে যত এজ আছে তাদের মধ্য মিনিমাম হলো ২-৪, কিন্তু ২ নম্বর নোড এবং ৪ নম্বর নোড দুইটাই অলরেডি সাবগ্রাফের অংশ,তারা আগে থেকেই কানেক্টেড,এদের যোগ করলে সাবগ্রাফে সাইকেল তৈরি হবে,তাই ২-৪ এজটি নিয়ে আমাদের কোনো লাভ হবেনা। আমরা এমন প্রতিবার এজ নিব যেন নতুন আরেকটি নোড সাবগ্রাফে যুক্ত হয়।”
আমি যে কোড টা করেছি তাতে সাইকেল তৈরী হয়ে যাচ্ছে 🙁 কোন উপায় খুজে পাচ্ছিনা… একটু হেল্প চাই…প্লিজ। আর আপনার প্রিম’স অ্যালগরিদম এর কোড টা একটু দেখতে চাই,আমাকে মেইল করে দিলে খুব ভাল হয়।
অসংখ্য ধন্যবাদ সময় দেয়ার জন্য।
আমি প্রিম মাত্র একবার ইম্প্লিমেন্ট করেছি,এই টিউটোরিয়ালটা লেখার সময়,কোডটা এখন নেই। তুমি যখনই কোনো এজ নিচ্ছো তখন দুপাশের নোডদুটিকে ভিজিটেড করে দাও,যখন নতুন এজ কিউ থেকে নিবে তখন আগে চেক করবে যে এজের দুপাশের দুটি নোডই ভিজিটেড নাকি,যদি দুটিই ভিজিটেড হয় তাহলে সেই এজ নেবার কোনো দরকার নেই। না পারলে তোমার কোডটি পোস্ট করতে পারো,দেখার চেষ্টা করবো।
bool operator p.cost;
ভাইয়া, এই লাইন ২ টার কাজ বুজতে পারতেছি না। প্লিজ একটু ব্যাখ্যা করে দেন।
এটাকে অপারেটর ওভারলোডিং বলে, উপরের একটা কমেন্টে ব্যাখ্যা করেছি দেখো।
bool operator p.cost;এই ২ টা লাইনে
আগের কমেন্টটা ডিলিট করে দিবেন প্লিজ।
ভাইয়া priority queue নিয়েই যত্তো সমস্যা।
নরমাল সর্ট করার সময় যেভাবে compare ফাংশান দিয়ে কাজ করি সেটা কীভাবে করবো? ওভারলোডিং করতে আমার সমস্যা হয় কীনা!
আর ভেরিয়্যাবল ডিক্লেয়ার করবো কীভাবে?
compare function এর কী ব্যাবস্থা করবো?
আর পুশ কি এইভাবে করতে হবে ভেক্টরের নিয়মে?
তুমি এই লিংকটা দেখো, আমার মনে হয় এটা দেখার পরে তোমার সমস্যা মিটে যাবে, এরপরেও সমস্যা থাকলে জানাও।
ধন্যবাদ ভাইয়া।
“যেহেতু এটা অ্যালগোরিদমের টিউটোরিয়াল,সি++ এর না,তাই এসব নিয়ে আর বেশি লিখবোনা,কোথায় সমস্যা হলে মন্তব্য অংশে বা আমার সাথে যোগাযোগ করে জানাতে পারো, আর তার আগে এই লিংকটা একবার দেখো।”
ভাইয়া, এই লিংকটা কাজ করছে না।
লিংকটা সরিয়ে ফেলা হয়েছে। অন্য একটা লিংক বসিয়ে দিলাম।
ভাইয়া, আমি ইউভিএ এর ৫৪৪ নাম্বার প্রব্লেম টা implement করেছি কিন্তু verdict- TLE . নিচে আমার কোড, দয়া করে সাহায্য করলে উপক্রিত হতাম ঃ
http://ideone.com/JRDg5A
ভাইয়া এইটা দেখেন। উপরের কমেন্টটা মুছে ফেইলেন, প্লিজ। 🙂
ঠিকই আছে, বেশি জটিল হয়নি :)। [আমি অবশ্য কোডটা এক্সিকিউট করে দেখিনি, লজিক ঠিকই আছে মনে হচ্ছে]