গ্রাফ কীভাবে মেমোরিতে থাকে (Graph Representation)

একটা গ্রাফ (Graph) হলো মূলত একটা ম্যাপ বা মানচিত্র। ধরুন একটা দেশে অনেকগুলো শহর (যাদের আমরা বলি ভার্টেক্স বা V) আছে, আর সেই শহরগুলো একে অপরের সাথে রাস্তা (যাদের আমরা বলি এজ বা E) দিয়ে যুক্ত। একটা গ্রাফ দিয়ে আপনি পৃথিবীর যেকোনো নেটওয়ার্ক বোঝাতে পারেন — সেটা হতে পারে বিমানের রুট, সোশ্যাল মিডিয়ার বন্ধুত্বের নেটওয়ার্ক, অথবা ওয়েবসাইটের লিংক।

ম্যাপ মনে রাখার দুটো উপায়

ধরুন আপনি ৫টা শহরের একটা ম্যাপ বানিয়েছেন। এখন কোন শহরের সাথে কোন শহরের রাস্তা আছে, সেটা খাতায় বা কম্পিউটারে লিখে রাখবেন কীভাবে? এর জন্য মূলত দুটো ক্লাসিক উপায় আছে:

অ্যাডজাসেন্সি লিস্ট (Adjacency List)

প্রতিটা শহরের জন্য একটা আলাদা কন্টাক্ট লিস্ট বা ফোনবুক রাখা। যেমন, শহর A-এর লিস্টে লেখা থাকবে: "আমার সাথে B এবং C-এর রাস্তা আছে।" আবার শহর B-এর লিস্টে লেখা থাকবে: "আমার সাথে A এবং D-এর লাইন আছে।" এই পদ্ধতিটাতে মেমোরি অনেক বাঁচে — কারণ এখানে আপনি শুধু সেই রাস্তাগুলোর হিসাবই রাখছেন, যেগুলো বাস্তবে আছে। যদি বেশিরভাগ শহরের মধ্যে সরাসরি রাস্তা না থাকে, তবে এই উপায়ে আপনার প্রচুর জায়গা বা মেমোরি বেঁচে যাবে।

অ্যাডজাসেন্সি ম্যাট্রিক্স (Adjacency Matrix)

একটা ছক বা গ্রিড আঁকুন, যার ডানে এবং নিচে সব শহরের নাম লেখা থাকবে। এবার ছকের যে ঘরে শহর X এবং শহর Y-এর সংযোগ বা রাস্তা মিলবে, সেখানে একটা 1 বসিয়ে দিন, আর রাস্তা না থাকলে 0। এই নিয়মে প্রতি জোড়া শহরের জন্যই একটা করে ঘর বরাদ্দ থাকে — এমনকী যাদের মধ্যে কোনো রাস্তাই নেই, তাদের জন্যও একটা করে (0-ওয়ালা) ঘর নষ্ট হয়! তবে এর একটা বড় সুবিধা হলো: "X থেকে Y-তে যানয়ার রাস্তা আছে কি না?"—এটা চেক করতে চোখের পলক বা O(1) সময় লাগে। কিন্তু ম্যাপ প্রায় ফাঁকা থাকলেও এটা মেমোরিতে বিশাল O(V²) জায়গা দখল করে নেয়।

ডিরেক্টেড (Directed) বনাম আনডিরেক্টেড (Undirected)

একটা আনডিরেক্টেড (Undirected) গ্রাফ হলো টু-ওয়ে বা দ্বিমুখী রাস্তার মতো — আপনি যদি A থেকে B-তে যেতে পারেন, তবে B থেকেও A-তে ফিরে আসতে পারবেন (ফেসবুকের ফ্রেন্ড রিকোয়েস্টের মতো)। অন্যদিকে একটা ডিরেক্টেড (Directed) গ্রাফ হলো ওয়ান-ওয়ে রাস্তার মতো — A থেকে B-তে রাস্তা আছে মানেই যে B থেকে A-তে রাস্তা থাকবে, তার কোনো গ্যারান্টি নেই (টুইটারে ফলো করার মতো, আপনি কাউকে ফলো করলেই যে সে আপনাকে ফলো ব্যাক করবে তার কোনো নিশ্চয়তা নেই!)।

ওয়েটেড গ্রাফ (Weighted Graphs)

বাস্তবে সব রাস্তার দৈর্ঘ্য বা দূরত্ব সমান হয় না। একটা ওয়েটেড গ্রাফে (Weighted Graph) প্রতিটা রাস্তার গায়ে একটা মান বা ওজন (Weight) লেখা থাকে — সেটা হতে পারে দূরত্ব, খরচ, বা যাতায়াতের সময়। লিস্টের ক্ষেত্রে এটা রাখা হয় জোড়া বানিয়ে: (পরের শহর, ওজন)। আর ম্যাট্রিক্সের ক্ষেত্রে 1-এর বদলে সরাসরি ওই ওজনের মানটাই (যেমন 5 বা 10) বসিয়ে দেওয়া হয়। ওয়েটেড গ্রাফ সবচেয়ে কম খরচের পথ বের করার অ্যালগরিদম যেমন ডাইকস্ট্রা (Dijkstra) ও বেলম্যান-ফোর্ড (Bellman-Ford)-এর ভিত্তি।