গ্রাফ থিওরি এবং একটি রুপকথার গল্প
পোস্টের শুরু এক গল্প দিয়ে যেখানে এক রাজ্যে এক রাজার কোন সন্তান ছিল না । রাজার মনে খুব দুঃখ। রাজা আর রাণী সারাদিন মন খারাপ করে থাকে। এক দিন ভাগ্য দেবতা তাদের প্রতি প্রসন্ন হলেন। রাণীর গর্ভে সন্তান আসলো। কিন্তু গোল বাধলো ৯ মাস পর যখন সন্তান প্রসবের সময় আসলো রাণী এক মহা বিপদে পড়লেন রাজা সবাইকে বললেন যে যে কোন মুল্যে রাণীকে সুস্থ করে তুলতে হবে সবাই রাজার কথা মত রাণীর জন্য দাওয়াই খুজতে বের হল। সেখানে রাজার সেনাপতিরা এক অদ্ভুত সূর্যমুখী ফুলের সন্ধান পেলেন যেখানে ফুলটি দিনের রাতের বেলায়ও জ্বলজ্বল করে। সেনাপতি সেই ফুল রাণীর জন্য নিয়ে এলেন। এবং সেই ফুল ধোয়া পানি খেয়ে রাণী এক সুন্দর ফুটফুটে কন্যা সন্তান জন্ম দিলেন। যার চুল ছিল সোনালী আর সেই চুল ও কেউ গান গাইলে জ্বলজ্বল করতো।
এখানে সেই ফুল ছিল এক ডাইনি বুড়ির দখলে যে তার ফুল হারিয়ে পাগল হয়ে গিয়েছিল। কারণ সেই ফুলের ছিল এক আশ্চর্য গুন যেখানে সেই ফুল কোন অসুস্থ মানুষকে সুস্থ করতে পারতো আর সেই ফুলের গুণে সেই ডাইনি আর যৌবন ধরে রাখতে পেরেছিল। ডাইনির নজর ছিল সেই রাজকন্যার উপর আর তাই এক রাতে সে সেই রাজকন্যাকে চুরি করে এক উচু টাওয়ারের উপর লুকিয়ে রাখলো আর তাকে বলল যে বাইরের দুনিয়া খুব ভয়ংকর সেখানে মোটেও যাওয়া যাবের না। আর সে নিজে তার মা সেজে তারসব কাজ করে দিত।
ধীরে ধীরে সেই রাজকন্যা সেই ডাইনিকেই তার মা জেনে বড় হল আর জানল যে বাইরের দুনিয়া তার জন্য এক বিভিষীকাময় জায়গা।
আমাদের সবার অবস্থা সেই রাজকন্যার মত। আমাদের ভেতরে এক ডাইনি বুড়ি সব সময় যে গ্রাফ থিওরি হল এক বিভিষীকাময় জায়গা আর আমরা ভয়তে সেদিকে ফিরেও তাকাই না।
Back to the story: ধীরে ধীরে রাজকন্যার বয়স বাড়তে থাকলো আর সে বাইরের জগতের প্রতি আগ্রহী হয়ে উঠলো। এমন সময় তার ঘরে আসলো এক চোর যে কিনা তার মুকূট চূরি করে পালিয়েছে। রাজকন্যা বাইরের দুনিয়া দেখার কিঞ্চিত ভরসা পেল। আর নিজেকে বোঝাল যে বাইরের দুনিয়া যতই খারাপ সে একবার সেখানে যাবেই যাবে।
আর আমাদের জন্য সেই বার্তা বয়ে এনেছে আমাদের সবার প্রিয় সবচেয়ে সমৃদ্ধ বাংলা ব্লগ শাফায়েতের ব্লগ। বর্তমান সময়ের সব থেকে সমৃদ্ধ বাংলা টিউটোরিয়াল ব্লগ।
এতটুকু পড়ার পর তোমার মনে যদি একটু সাহস সঞ্চার হয়ে থাকে তাহলে গ্রাফ কি জেনে আসতে পারো এখান থেকে। তারপর গ্রাফ কিভাবে variable এ store করতে হয় তা জানতে পারো এখান থেকে আর এখান থেকে ।
back to story : রাজকন্যা চোরের সাথে বের হবার পর তার তো মাথা খারাপ অবস্থা সে বাইরের দুনিয়া দেখে পুরো পুরি বিস্মিত আর হতভম্ব সে নিজে বুঝতে পারলো যে তার তার মা তার সাথে যা বলেছে যা সে যা জেনেছে তা পুরোপুরি মিথ্যা।
তুমি যদি গ্রাফের আগের দুটো টিটোরিয়াল পড়ে থাকো তাহলে নিশ্চয় বুঝে গেছো যে তুমি যা জানতে তাও প্রায় পুরোপুরি মিথ্যা আর গ্রাফ খুব সহজ জিনিস। এখন তুমি যদি গ্রাফের দুনিয়া ঘুরে দেখতে চাও তাহলে তোমাকে গ্রাফ ট্রার্ভাস জানতে হবে আর তার জন্য আছে দুটো পদ্ধতি সে দুটো হল BFS আর DFS আর এদুটো আসলে কি তা জানতে তোমাকে BFS এর জন্য এখান থেকে আর DFS এর জন্য এখান তেকে ঘুরে আসতে হবে।আর যদি BFS কোড জানতে চাও তাহলে এখানে ছোট্ট একটা উকি দিয়ে আসো।
এখন তুমি গ্রাফের মোটামুটি expert বলা যায় এখন নিজের যোগ্যতা প্রমাণের জন্য হোক আর বন্ধুদের তাক লাগানোর জন্য হোক তুমি জলদি কয়েকটা problem solve করে ফেলতে পারো যদি জানতে চাও কোন গুলো তাহলে দেখ এই পোষ্টের শেষে অথবা uvatoolkit এ গিয়ে BFS লিখে একটা search মারো তুমি যত বেশি problem solve করবে তোমার লজিক তত develop করবে আর তুমি তত বড় মাপের problem solver হিসাবে আত্মপ্রকাশ করবে যদি ওয়া খাও তাহলে খুব খুশির কথা কারণ তুমি একটা নতুন জিনিস শেখার সুযোগ পেলে যা আগে জানতে না।
এখন যদি আবার গল্পের কথা মনে পড়ে তাহলে চল বাকিটুকু শুনে আসা যাক । রাজকন্যা পৃথিবী ঘোরা শুরু করার পর সে বুঝতে পারলো যে সে আসলে এত দিন মিথ্যার মধ্যে ছিল তারপর সে এক বিশাল adventure এর মধ্যে দিয়ে তার মা বাবাকে আবিষ্কার করে আর জানতে পারে তার আসল পরিচয় শেষ হয় এক শ্বাসরুদ্ধকর গল্পের। যারা আমার মত একটু হালকা পাতলা মুভি দেখ তারা নিশ্চয় বুঝে গেছ আমি কোন ছায়াছবির কথা বলতে চাইছি আমি আসলে Tangled এর গল্প বললাম যার মুল নাম রুপাঞ্জেল আর এটা একটা Spanish রুপকথা।
আমি যত সহজে গল্পটা শেষ করে দিলাম আমাদের আসল গ্রাফ থিওরি শেখা কিন্তু এতটা সহজে শেষ হবে না আমাদের আরো অনেক পথ যেতে হবে আর আমাদের adventure টাও রুপাঞ্জেলের থেকে কোন অংশে কম হবে না। এখনো তোমাকে গ্রাফ থিওরির অনেক অ্যালগো জানতে হবে।
MST গ্রাফের খুব গুরুত্বপূর্ণ একটা জিনিস তোমাকে MST কি জানতে উকি দিতে হবে এখানে আর কিভাবে MST বের করা যায় তা জানতে দেখতে হবে এখানে আর এখানে। MST এর বেলায়ও BFS এর মত একই কথা প্রযোজ্য uvatoolkit গিয়ে MST লিখে একটা search মারো যা আসবে solve করা শুরু করে দাও এখানে তোমাকে প্রত্যেক problem এর জন্য অ্যালগোটাকে অনেক ভাবে modify করা লাগবে যার মধ্যে দিয়ে তুমি গ্রাফ থিওরিতে হালকা পাতলা বস হতে শুরু করবে।
অরিজিনাল পোস্ট