গ্রাফ অ্যালগরিদম

ভূমিকা

গ্রাফ অ্যালগরিদমে আমার দুর্বলতা গোপন কিছু নয়। তাই লেখকের কাছ থেকে যখন তার বইয়ের মুখবন্ধ লেখার প্রস্তাব পেলাম তখন খুশি আর আমার ধরে না। কারণ এরকম প্রস্তাব এই প্রথম, বিনামূল্যে গ্রাফ অ্যালগরিদম শিখে ফেলা যাবে। সর্বোপরি এই বই দেখিয়ে নিজেকে গ্রাফ বিশেষজ্ঞ প্রমাণ করা যাবে। আরেকটি কারণ হলো আমি এবং শাফায়েত প্রোগ্রামিং কনটেস্টের দুই ঘরানার লোক (DU-BUET অথবা Codemarshal-Hackerrank যেভাবেই দেখি না কেন)। কিন্তু সবকিছুর আগে আমরা বাংলাদেশের ভালো চাই এবং আমাদের কাজে সেটাই ফুটে ওঠা উচিত। সেই ফুটিয়ে উঠানোর কাজটা সবচেয়ে ভালোভাবে করা সম্ভব এই বই এর মুখবন্ধ লেখার মাধ্যমে। পুরো বইটি পড়ার সময় হয়নি এখনো, কিন্তু যতদুর দেখেছি তাতেই মনে করি বইটি বোঝা বেশ সহজ, অযথা গাণিতিক প্রতীক / চিহ্ন ইত্যাদি ব্যবহার করে লেখক পান্ডিত্ব দেখানোর চেষ্টা করেননি এবং অনেক বেশি টপিক নিয়ে আলোচনারও চেষ্টা করেননি।
আমাদের দেশের ছেলে মেয়েদের ইংরেজিতে দুর্বলতা অনেক বেশি, কিন্তু এই দুর্বলতা ভালো প্রোগ্রামার হওয়ার পথে কোনো অন্তরায় হওয়া উচিত নয়। যদি তাই হতো তাহলে রাশিয়া, চীন থেকে বিশ্বের সব ভালো ভালো প্রোগ্রামাররা বের হয়ে আসত না আর আইসিপিসিতে ইংরেজিভাষী দেশগুলোকে মেডেলের জন্য হা-হুতাশ করতে হতো না। কাজেই কম্পিউটার বিজ্ঞানের বিভিন্ন বিষয়ের ওপর আরও বাংলা বই বের হওয়া উচিত এবং সেদিক দিয়ে এই বইটি একটি ভালো সংযোজন। এ ধরনের বই পড়ে আমাদের দেশের ছেলেমেয়েরা অনেক কম বয়সেই খুব ভালো প্রোগ্রামার হয়ে উঠতে পারবে।
বিশ্ব মানের প্রোগ্রামার তৈরির জন্য প্রোগ্রামিং প্রতিযোগিতা একমাত্র উপায় না হলেও খুবই গুরুত্বপূর্ণ একটি প্রক্রিয়া। তবে আমাদের দেশে ভালো প্রোগ্রামার তৈরিতে এর গুরুত্ব বিশ্বের উন্নত দেশের চেয়ে অনেক বেশি। কারণ, আমাদের দেশের প্রচলিত শিক্ষা ব্যবস্থা এখনো যুক্তিনির্ভর চিন্তা ভাবনার জন্য অনুকুল নয়। সেদিক থেকেও এই বইটি এর গুরুত্ব অপরিসীম। এই বই এ আলোচিত গ্রাফ অ্যালগরিদম গুলো ভালোভাবে বুঝলে প্রোগ্রামিং প্রতিযোগিতার অন্তত ৮০ ভাগ গ্রাফ সমস্যা সমাধান করা সম্ভব।
প্রোগ্রামিং শেখার জন্য বাংলায় বেশ কিছু বই রয়েছে। কিন্তু মূলত প্রোগ্রামিংয়ের একদম প্রারম্ভিক বিষয়গুলো নিয়ে সেখানে আলোচনা করা হয়েছে। অ্যালগরিদম শেখার জন্য ভালো বাংলা বই এখনো সেভাবে ছাপা হয়ে বের হয়নি। পিডিএফ হিসাবে হয়ত বেশ কিছু বই পাওয়া যাচ্ছে। সেদিক থেকেও এই বইটিকে একটি মাইলফলক হিসাবে দেখা যায়। সব মিলিয়ে আমি লেখককে ধন্যবাদ দিতে চাই এরকম একটি বই লেখার জন্য। আমি আশা করি সময়ের সঙ্গে সঙ্গে বইটি আরও উন্নত হবে এবং সঙ্গে সঙ্গে কম্পিউটার ইঞ্জিনিয়ারিংয়ে আরও অনেক ভালো ভালো বাংলা বই প্রকাশিত হবে। তখন আমরা জাপানিদের মতো বিশ্ববিদ্যালয় পর্যায়েও মাতৃভাষায় শিক্ষা দিতে পারব। ৫২ এর ভাষা আন্দোলন সেদিনই পরিপূর্ণভাবে সার্থক হবে।

শাহরিয়ার মঞ্জুর,
সভাপতি, বাংলাদেশ অ্যাসোসিয়েশন অব প্রবলেমসেটারস
জাজিং ডিরেক্টর, এসিএম আইসিপিসি ঢাকা রিজিয়নাল (২০০৪-২০১৫)
বিচারক, এসিএম আইসিপিসি ওয়ার্ল্ড ফাইনাল (২০০৩-২০১৬)
জাজিং ডিরেক্টর, এসিএম আইসিপিসি ঢাকা রিজিয়নাল (২০০৩-২০১৬)
এছাড়াও ২০০০ সাল থেকে ভ্যালাদলিদ অনলাইন জাজ (Valladolid Online Judge) এর সঙ্গে জড়িত

সূচীপত্র

অধ্যায় ১ – গ্রাফ থিওরিতে হাতেখড়ি

• ১.১ – কনিসবার্গের সেতু
• ১.২ – অয়লারের আক্রমণ
• ১.৩ – অসাধ্যতার প্রমান
• ১.৪ – গ্রাফ কী?
  • অ্যাডজেসেন্ট নোড (Adjacent node)
  • সাবগ্রাফ (Subgraph)
  • ডিরেক্টেড (Directed) গ্রাফ এবং আনডিরেক্টেড (Undirected) গ্রাফ
  • ওয়েটেড (Weighted) ও আনওয়েটেড (Unweighted) গ্রাফ
  • পাথ (Path)
  • ডিগ্রি (Degree)
  • ট্রি (Tree)
• ১.৫ – কিছু বিশেষ গ্রাফ
  • কমপ্লিট গ্রাফ (Complete Graph)
  • সাইকেল (Cycle)
  • হুইল গ্রাফ (Wheel Graph)
  • বাইপারটাইট গ্রাফ (Bipartite Graph)

অধ্যায় ২ – গ্রাফ উপস্থাপন

• ২.১ – অ্যাডজেসেন্সি ম্যাট্রিক্স (Adjacency Matrix)
  • অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করার সমস্যা
  • অ্যাডজেসেন্সি ম্যাট্রিক্স ব্যবহার করার সুবিধা
• ২.২ – অ্যাডজেসেন্সি লিস্ট (Adjacency List)
  • অ্যাডজেসেন্সি লিস্ট ব্যবহার করার সুবিধা
  • অ্যাডজেসেন্সি লিস্ট ব্যবহার করার অসুবিধা

অধ্যায় ৩ – ব্রেডথ ফার্স্ট সার্চ (Breadth First Search)

• ৩.১ – অ্যালগরিদমের বিবরণ
  • 2D গ্রিডে বিএফএস
• ৩.২ – বাইকালারিং (Bicoloring)

অধ্যায় ৪ – ডায়াক্সট্রা অ্যালগরিদম (Dijkstra Algorithm)

• ৪.১ – পাথ রিলাক্সেশন
• ৪.২ – অ্যালগরিদমের বিবরণ
  • নেগেটিভ সাইকেল?
  • ২য় সেরা সংক্ষিপ্ততম পথ

অধ্যায় ৫ – ফ্লয়েড ওয়ার্শল অ্যালগরিদম (Floyd Warshall Algorithm)

• ৫.১ – অ্যালগরিদমের বিবরণ
  • ট্রান্সিটিভ ক্লোজার (Transitive Closure)

অধ্যায় ৬ – ডিসজয়েন্ট সেট (Disjoint Set)

অধ্যায় ৭ – মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)

• ৭.১ – প্রিম অ্যামলগরিদম (Prim’s Algorithm)
• ৭.২ – ক্রুসকাল অ্যালগরিদম (Kruskal’s Algorithm)
  • ২য় সেরা মিনিমাম স্প্যানিং ট্রি

অধ্যায় ৮ – টপোলজিকাল সর্টিং (Topological Sorting)

অধ্যায় ৯ – বেলম্যান ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm)

অধ্যায় ১০ – স্টেবল ম্যারেজ (Stable Marriage)

অধ্যায় ১১ – ডেপথ ফার্স্ট সার্চ (Depth First Search)

অধ্যায় ১২ – আর্টিকুলেশন পয়েন্ট (Articulation Point) এবং ব্রিজ (Bridge)

• ১২. ১ – আর্টিকুলেশন পয়েন্ট (Articulation Point)
• ১২.২ – ব্রিজ (Bridge)
  • ইউনিক পাথ প্রবলেম

অধ্যায় ১৩ – স্ট্রংলি কানেক্টেড কম্পোনেন্ট (Strongly Connected Component)

অধ্যায় ১৪ – ম্যাক্সিমাম ফ্লো (Maximum Flow)

• ১৪.১ – কয়েকটি ভ্যারিয়েশন
  • #১ একাধিক সোর্স/সিংক থাকলে কী করবে?
  • #২ প্রতিটি নোডের নির্দিষ্ট ক্যাপাসিটি থাকলে কী করবে?
  • #৩ এজ ডিসজয়েন্ট পাথ কীভাবে বের করবে?
• ১৪.২ – বাইপারটাইট ম্যাচিং
• ১৪.৩ – মিন-কাট প্রবলেম