গ্রাফ থিওরি (পর্ব ৫)
প্রোগ্রামিং — ১
গ্রাফের মধ্যে ঘুরাঘুরি
আসো, কনরাড জিউস (Konrad Zuse) এর সাথে পরিচয় করিয়ে দিই তোমাদের। আধুনিক কম্পিউটার (prorgrammable computer) ও প্রথম হাই লেভেল প্রোগ্রামিং ভাষার (Plankalkul) “আব্বা” হচ্ছেন এই ভদ্রলোক। পেশায় একজন সিভিল ইঞ্জিনিয়ার জার্মানির এই ভদ্রলোক বিশ্বের প্রথম কম্পিউটার ব্যবসায়ীও ছিলেন। দেখা যাচ্ছে যে, অনেককিছুর প্রথম তিনি।
জিউস সাহেব উনার পিএইচডি পেপারে ‘গ্রাফে ঘুরে বেড়ানোর’ একটি পদ্ধতি নিয়ে আলোচনা করেন। কিন্তু উনার পেপার বাতিল করা হয়। পরবর্তীতে প্রায় ১৪ বছর পর একইসাথে এমআইটি এবং হার্ভাডে শিক্ষকতা করা এডওয়ার্ড মুর (Edward F. Moore), জিউসের ওই পদ্ধতিটি সফলভাবে কাজে লাগান। পদ্ধতিটির নাম হচ্ছে Breadth First Search (সংক্ষেপে BFS)।
মুর সাহেব গোলকধাঁধার (Maze) মধ্য দিয়ে সবচেয়ে ছোট রাস্তায় কিভাবে বের হয়ে আসা যায় সেটা বের করার জন্য BFS কে কাজে লাগান। গোলকধাঁধা সম্পর্কে একটা ধারণা নেয়ার জন্য নিচের ছবিটি খেয়াল করা যেতে পারে।
মুর বা জিউসের অনেক অনেক আগে চার্লস পিয়েরে ট্রিমক্স (Charles Pierre Tremaux) নামক একজন ফ্রেঞ্চ গণিতবিদ এই গোলকধাঁধা সমাধান করতে গিয়ে বা গোলকধাঁধার মধ্যে কিভাবে সবচেয়ে কম রাস্তায় ঘুরে বেড়ানো যায়, সেটার জন্য একটি পদ্ধতি আবিষ্কার করেন। এই পদ্ধতির নাম হচ্ছে Depth First Search (সংক্ষেপে DFS)।
বর্তমান সময়ে বুদ্ধি খাটিয়ে গ্রাফে ঘুরে বেড়ানোর জন্য এই দুটি (BFS ও DFS) পদ্ধতি ব্যাপকভাবে ব্যবহার করা হয়। আমরা এই পর্বে পদ্ধতি দুটো নিয়ে বিশদভাবে আলোচনা করবো। আলোচনার জন্য একটি গ্রাফ (L) উদাহরণ হিসেবে নিলাম,
প্রথমে BFS নিয়ে কথা বলবো।
প্রথম কথা হচ্ছে যে, আমরা গ্রাফের যেকোন নোড থেকে আমাদের যাত্রা শুরু করতে পারি। একদম ইচ্ছামত আরকি! আমরা সবগুলো উদাহরণে ১ নং নোড থেকে যাত্রা আরম্ভ করবো, তুমি ইচ্ছা করলে অন্য কোথাও থেকে শুরু করতে পারো।
দ্বিতীয় কথা হচ্ছে যে, যেখান থেকে যাত্রা শুরু করলাম তার সাথে কার কার এজ বা সম্পর্ক আছে তা খুঁজে বের করে সেখানে সেখানে ঘুরে আসতে হবে। উদাহরণ হিসেবে বলা যায়, ‘১’ থেকে যাত্রা শুরু করলাম। এরপর ১ নং নোডের সাথে ৩, ৪, ৫ নং নোডের এজ আছে, সেগুলো ঘুরে শেষ করলাম। তাহলে বলা যায়, ১ নং এর কাজ শেষ। নিচের ছবিটি খেয়াল করো,
এখানে কি কি করা হয়েছে সেটা বলা যাক।
যেহেতু ১ নং নোড থেকে যাত্রা শুরু করেছি তাই সেটা লিখে রাখলাম। তারপর ১ থেকে ৩, ৪, ৫ এ গেলাম তাই এদেরকেও লিখে রাখলাম। তুমি যদি প্রশ্ন করো যে, ‘১’ থেকে ‘৩’ এ প্রথমে না গিয়ে ‘৪’ এ বা ‘৫’ এ যাওয়া যাবে? অবশ্যই। তোমার ইচ্ছা। কারণ তুমি অন্যপথে গিয়ে দেখতে পারো, শেষে গিয়ে ফলাফল একই পাবা।
তারপর আমরা দেখতে পাচ্ছি যে, ‘১’ থেকে আর কোথাও যাওয়া যাবেনা মানে ১ নং ভালোমতো ঘুরাঘুরি করা হয়ে গেছে তাই এটাকে কালো করে দিয়েছি।
এবার তাহলে আমরা ৩ নং নোড থেকে যাত্রা শুরু করবো। কারণ ‘১’ এর পরে ‘৩’ আছে।
এখানে যা করা হয়েছে তা হল, ৩ নং থেকে যাত্রা শুরু করে ১ ও ২ নং নোডে যেতে পারি কিন্তু ১ নং নোড ইতিমধ্যেই ঘুরাঘুরি করা শেষ। তাই শুধু ২ নং নোড আমরা ঘুরে নিলাম এবং সেটাকে এখানে লিখে দিলাম। যেহেতু ৩ নং নোডের কাজ শেষ তাই এটাও কালো হয়ে গেলো।
অনুরূপভাবে ৪ নং থেকে ১, ২, ৫ এ যাওয়া গেলেও আমরা ওসব জায়গা ঘুরে ফেলেছি তাই ৪ নংও কালো হয়ে যাবে। একইভাবে ৫ ও ২ নং কালো হয়ে যাবে। অর্থাৎ গ্রাফে ঘুরাঘুরি শেষ। এটাই হচ্ছে BFS এর মোদ্দা কথা।
এবার আমরা L গ্রাফে DFS এর নিয়ম মেনে ঘুরাঘুরি করবো। তাহলে শুরু করা যাক।
প্রথম কথা হচ্ছে যে, এটার ক্ষেত্রেও আমরা যেকোন নোড থেকে শুরু করতে পারি।
দ্বিতীয় কথা হচ্ছে যে, ‘১’ থেকে যতগুলো নোডে যাওয়া যায় সবগুলোতে যাবোনা। উদাহরণস্বরূপ বলা যায়, ১ নং নোড থেকে যাত্রা শুরু করে হয়তো প্রথমে ‘৩’ এ আসলাম। এবার করবো কি, ৩ নং থেকে আবার কোথায় যাওয়া যায় সেটা দেখবো অর্থাৎ ভেতরে ঢুকতে থাকবো। আমরা BFS এর ক্ষেত্রে ১ নং থেকে তার আশেপাশে মানে প্রস্থ (breadth) বরাবর যতগুলো নোডে যাওয়া যায় সেভাবে ঘুরাঘুরি শেষ করেছিলাম কিন্তু DFS এর ক্ষেত্রে আমরা ‘১’ থেকে ‘৩’ এ, ‘৩’ থেকে ‘২’ এ, আবার ‘২’ থেকে ‘৪’ এ; এভাবে ভেতরে (deep এ) ঢুকতে থাকবো। আশা করছি নামকরণের সার্থকতা বোঝা গেছে।
এখানে কি করেছি? ১ নং নোড থেকে যাত্রা আরম্ভ করে ৩ নং এ এসেছি। কিন্তু ১ নং কে কালো করিনি কারণ ‘১’ এর কাজ এখনও শেষ হয়নি।
এখানে ৩ নং থেকে যাত্রা আরম্ভ করে ‘২’ এ এসেছি। আবারও ‘৩’ এর কাজ শেষ না হওয়ায় একে কালো করা হয়নি।
এখানে ২ নং থেকে যাত্রা আরম্ভ করে ‘৪’ এ এসেছি। ‘৪’ এর কাজ শেষ হয়নি।
অবশেষে আমরা ৪ নং নোডে পৌঁছে গেলাম। এখানে থেকে ‘১’ ও ‘৫’ এ যাওয়ার রাস্তা আছে। কিন্তু ১ নং নোড না গিয়ে ‘৫’ এ যাওয়া ভালো কারণ ১ নং নোড থেকে যাত্রা আরম্ভ করে এসেছি মানে সেটা খানিকটা ঘুরা হয়েছে কিন্তু ‘৫’ এ কখনো যাইনি। তাই আমরা ‘৪’ থেকে ‘৫’ এ গিয়ে দেখি আর কোথাও যাওয়া যাচ্ছেনা। তাই ৫ নং কে কালো করে দিয়ে আমরা পেছনে আসা (backtracking, এটা নিয়ে পরে কথা হবে) শুরু করলাম। ৪ নং এ এসে দেখা যাচ্ছে নতুন কোন জায়গা নেই যাওয়ার তাহলে ৪ নংও কালো হয়ে যাবে।
অনুরূপভাবে ৪ নং থেকে পেছনে এসে পৌঁছলাম ২ নং নোডে। এখান থেকেও নতুন কোন জায়গা নেই যাওয়ার, তাই এটাও কালো হয়ে যাবে। একইভাবে ৩ ও ১ নং নোড কালো হয়ে গিয়ে গ্রাফে ঘুরাঘুরি শেষ। এটাই হচ্ছে DFS এর মোদ্দা কথা।
এবার আমরা ৪০ ও ৪৬ নং ছবি তুলনা করলে দেখবো, দুই পদ্ধতিতে দুইটি আলাদা রাস্তা ব্যবহৃত হয়েছে।
BFS এর ক্ষেত্রে ১ — ৩ — ৪ — ৫ — ২
DFS এর ক্ষেত্রে ১ — ৩ — ২ — ৪ — ৫
আশা করি সবাই বুঝেছো। যদি কারও এখনও অস্পষ্টতা থাকে সেজন্য আমি আরেকটা উদাহরণ দেখাচ্ছি, তবে এবার একটু কম কথা খরচ করে দ্রুত ব্যাখ্যা করে ফেলবো।
প্রথমে BFS অনুসারে, ১ নং থেকে শুরু করে ২, ৪, ৫ এ যাওয়া যায়। সিকোয়েন্স দাঁড়ালো, ১ — ২ — ৪ — ৫
এবার তাহলে ২ নং থেকে শুরু করে যাওয়া যায় ৭, ৬, ৩ এ। চূড়ান্ত সিকোয়েন্স,
১ — ২ — ৪ — ৫ — ৭ — ৬ — ৩
এবার DFS অনুসারে করে, ১ নং থেকে শুরু করে গেলাম ‘২’ এ। এবার ‘২’ থেকে ‘৩’ এ গেলাম। আমি আগেও বলেছি এবং এখনও বলছি যে, তুমি অন্য যেকোন রাস্তা পছন্দ করতে পারো। তো যা বলছিলাম, ‘৩’ এ গিয়ে দেখলাম যাওয়ার আর জায়গা নাই। তখন পেছনে আসা শুরু করলাম।
এখন পর্যন্ত সিকোয়েন্স দাঁড়ালো, ১ — ২ — ৩
পিছনে এসে পৌঁছলাম ২ নং এ। এখান থেকে গেলাম ‘৬’ এ। ৬ নং থেকে আর কোথাও যাওয়ার উপায় নাই, তাই আবার backtracking। আসলাম আবার ‘২’ এ। এবার ‘২’ থেকে ‘৭’ গিয়ে আবারও একই কাহিনী। ফেরত আসলাম ‘২’ এ। এখন পর্যন্ত সিকোয়েন্স, ১ — ২ — ৩ — ৬ — ৭
এখন দেখা যাচ্ছে যে, ‘২’ থেকে আর কোথাও যাওয়া যাচ্ছেনা। তাই আমরা ‘২’ থেকে পেছনে আসবো অর্থাৎ ‘১’ এ। এবার ‘১’ থেকে ৪ নং এ গিয়ে দেখছি ওখান কোথাও যাওয়া যাচ্ছেনা তাই পেছনে ফিরে ‘১’ এ আসলাম। এবার ‘১’ থেকে ‘৫’ এ গিয়ে একই অবস্থা। আবার আসলাম ‘১’ এ। এবার ‘১’ থেকেও কোথাও যাওয়া যাচ্ছেনা, সব জায়গা ঘুরাঘুরি করা শেষ। সিকোয়েন্স দাঁড়ালো শেষে, ১ — ২ — ৩ — ৬ — ৭ — ৪ — ৫
অনেক হলো ঘুরাঘুরি। এবার আমরা চেষ্টা করবো এই BFS ও DFS কিভাবে কম্পিউটার বাবাজিকে বুঝানো যায়, ওই কোড ফোড আরকি। তো হয়ে যাক প্রোগ্রামিং।
প্রথমে DFS এর কোড দেখবো,
উপরের কোডে adjacency matrices এর মাধ্যমে একটি গ্রাফ নেয়া হয়েছে। ৪১ নং লাইনে dfs() নামের একটি ফাংশন ডিক্লেয়ার করা হয়েছে। এর ব্যাখ্যা নিচে দেয়া হল,
২১ নং লাইন — এখানে dfs() ফাংশন শুরু হচ্ছে। আমাদের গ্রাফ নেয়া হয়ে গেছে (৩৩-৪০ নং লাইন), এখন আমাদের কি করা উচিৎ? আমরা একটা কৌশল অবলম্বন করবো। সেটা হচ্ছে, যে নোড আমরা এখনও ঘুরিনি সেটাকে সাদা রঙ এ, যে নোডের কাজ চলছে অর্থাৎ ঘুরাঘুরি চলছে তাকে ছাই (gray) রঙ এ এবং যে নোডের কাজ শেষ তাকে কালো রঙ এ রাঙিয়ে দিবো। তাহলে হিসাব রাখতে সুবিধা হবে যে কোন্ কোন্ নোড ঘোরা হয়েছে আর কোনটা হয়নি।
২, ৩, ৪ নং লাইন — এই তিন লাইনে আমরা বলে দিয়েছি যে ‘১’ সংখ্যাটি দিয়ে সাদা বুঝানো হবে এবং ‘২’ ও ‘৩’ দিয়ে যথাক্রমে ছাই ও কালো বুঝানো হবে।
৫ নং লাইন — কিছু ডিক্লেয়ারেশন করা হয়েছে, এগুলোর কাজ পরে বুঝা যাবে।
২৩, ২৪ নং লাইন — যতগুলো নোড আছে সবগুলোকে সাদা রঙে রাঙানো হল, কেননা যাত্রা শুরু করার আগে তো আমরা কাউকেই ঘুরে দেখিনি।
২৫-২৭ নং লাইন — এবার আমরা খুঁজে বের করবো কোন্ নোডটি সাদা, দিয়ে সেখান থেকে যাত্রা আরম্ভ করবো। তোমাদের মনে হতে পারে এখনি সবগুলোকে সাদা করলাম, তাহলে খোঁজার কি আছে? এরপর আমরা আরও কিছু কাজ করবো যাতে করে কিছু নোড ধীরে ধীরে অন্য রঙের হবে এবং সাদা নোডের সংখ্যা কমতে থাকবে।
২৮ নং লাইন — এখানে একটি নতুন ফাংশন ডিক্লেয়ার করা হয়েছে। এই ফাংশন দিয়ে আমরা একটি নির্দিষ্ট নোডকে ঘুরে দেখবো।
৮ নং লাইন — এখানে নতুন ফাংশনটির (dfsVisit()) কাজ দেখানো আছে।
১০ নং লাইন — খেয়াল করে দেখো এই ফাংশনটি প্যারামিটার হিসেবে একটি সংখ্যা নিচ্ছে। এই সংখ্যাটি আসছে ২৮ নং লাইন থেকে। সংখ্যাটি কি সেটা ২৭ নং লাইনের দিকে তাকালে বোঝা যাবে। যে নোডের রঙ সাদা সেই সংখ্যাটি ২৮ নং লাইনে যাচ্ছে এবং সেখান থেকে ৮ নং লাইনে প্যারামিটার হিসেবে আসছে। সেই সংখ্যাটিই আবার ১০ নং লাইনে ছাই রঙের হচ্ছে। তারমানে ওই নোডের কাজ শুরু হলো।
১৩ নং লাইন — আমরা এখন গ্রাফের মধ্যে খুঁজবো ১০ নং লাইনের নোডের সাথে কার কার এজ আছে।
১৪-১৫ নং লাইন — যাদের সম্পর্ক আছে তাদের রঙ কি সাদা? যদি হয় তাহলে তাদের মধ্যে ঘুরবো।
১৮ নং লাইন — ঘোরাঘুরি শেষ।
১৯ নং লাইন — তাহলে তাকে কালো করে দাও।
BFS এর কোড নিয়ে সামনের পর্বে আলোচনা করবো, নাহলে এই পর্ব অনেক লম্বা হয়ে যাবে।
অয়লার ভাইয়াকে নিয়ে আজকে যে তথ্যটি দিবো সেটার সাথে বার্নুলি পরিবারের সম্পর্ক আছে। তাই বার্নুলি পরিবার নিয়ে দুটো কথা না বললেই নয়। বার্নুলি পরিবারের বসবাস সুইজারল্যান্ডের বাসেল শহরে। রজার ফেদেরার ভাইয়াও কিন্তু এই শহরের মানুষ। বার্নুলি পরিবার অবশ্য অনেক পুরনো। আমি মোটামুটি ৪০০ বছর আগের কথা বলছি। এই পরিবারে কমপক্ষে ৮ জন বিখ্যাত গণিতবিদ জন্মগ্রহণ করেছেন। উমুক বার্নুলি, তমুক বার্নুলি ইত্যাদি। মাথা খারাপ হয়ে যাবে ইনাদের নাম মনে রাখতে গিয়ে।
এই পরিবারের একজন বিখ্যাত সন্তান ছিলেন জোহান বার্নুলি (Johann Bernoulli), ইনি আবার কুরি পরিবারের জামাই ছিলেন। জ্বী ভাই, সেই বিখ্যাত কুরি পরিবার। এই ভদ্রলোক আবার অয়লারের বাবার বন্ধুও ছিলেন। প্রতি শনিবার তিনি অয়লারকে প্রাইভেট পড়াতেন। অয়লারের বাপ চেয়েছিল ছেলে তার ধর্মযাজক (খ্রিস্টান ধর্মের ইমাম আরকি!) হোক। কিন্তু বার্নুলি সাহেব উনাকে অনেক বুঝান যে, ছেলে আপনার মস্ত বড় গণিতবিদ হবে। তাই আমরা অয়লার সাহেবকে পেয়েছি। নইলে কি যে হতো! শেষ করতে করতে আরেকটা কথা, অয়লার মাত্র ১৭ বছর বয়সে মাস্টার্স পাশ করেছিলেন।
