কোসারাজু অ্যালগরিদম (Kosaraju's Algorithm)

একটি সোশ্যাল নেটওয়ার্কের কথা কল্পনা করুন। ব্যক্তি A হয়তো ব্যক্তি B-কে ফলো করে, কিন্তু B কি পাল্টা A-কে ফলো করে? গ্রাফ থিওরির ভাষায় স্ট্রংলি কানেক্টেড কম্পোনেন্ট (SCC) হলো এমন একটি গ্রুপ যেখানে প্রত্যেকে প্রত্যেকের কাছে পৌঁছাতে পারে — যা অনেকটা একটি নিখুঁত 'মিউচুয়াল-ফলো' গ্রুপের মতো।

কোসারাজুর অ্যালগরিদম ঠিক দুটি DFS (Depth-First Search) ব্যবহার করে এই ধরণের সবগুলো গ্রুপ খুঁজে বের করে। এটি দেখতে যেমন মার্জিত, কোড করাও তেমনি সহজ এবং এটি লিনিয়ার সময়ে কাজ সম্পন্ন করে।

মূল ধারণা: গ্রাফটি উল্টে দেওয়া

এই অ্যালগরিদমের সবচেয়ে বড় কৌশল হলো ট্রান্সপোজ গ্রাফ (Transposed Graph) বা \(G^T\) তৈরি করা। অর্থাৎ গ্রাফের প্রতিটি ডিরেক্টেড এজ বা তীরকে উল্টে দেওয়া। A→B হয়ে যাবে B→A।

মজার ব্যাপার হলো: মূল গ্রাফ এবং উল্টানো গ্রাফের SCC-গুলো একই থাকে। যদি কোনো গ্রুপের সবাই আগে একে অপরের কাছে পৌঁছাতে পারতো, তবে রাস্তা উল্টে দিলেও তারা একে অপরের কাছে পৌঁছাতে পারবে (হয়তো ভিন্ন পথে)। রাস্তা উল্টে দেওয়ার ফলে গ্রুপের ভেতরের পারস্পরিক সম্পর্ক নষ্ট হয় না, শুধু একটি গ্রুপের সাথে অন্য গ্রুপের সম্পর্কের দিক বদলে যায়।

প্রথম ধাপ: মূল গ্রাফে DFS চালানো

প্রথমে মূল গ্রাফের ওপর একটি পূর্ণ DFS চালান। যখনই কোনো ভার্টেক্সের কাজ শেষ হবে (অর্থাৎ তার সব প্রতিবেশীকে দেখা হয়ে যাবে), তখন সেটিকে একটি স্ট্যাক-এ (Stack) পুশ করুন। যে ভার্টেক্সটি সবার শেষে শেষ হবে, সেটি স্ট্যাকের একদম উপরে থাকবে।

এটি অনেকটা একটি ভবন থেকে বের হওয়ার মতো — যে সবার শেষে ঢুকেছে এবং সবচেয়ে গভীরে গেছে, সে-ই সবার আগে আসবে না; বরং যে সবার শেষে কাজ শেষ করেছে সে উপরে থাকবে। এই স্ট্যাকটি আমাদের নিশ্চিত করে যে কোন SCC-টি গ্রাফের 'উৎস' হিসেবে কাজ করছে।

দ্বিতীয় ধাপ: উল্টানো গ্রাফে DFS চালানো

এখন উল্টানো গ্রাফটি (\(G^T\)) নিন এবং স্ট্যাক থেকে একটি একটি করে ভার্টেক্স বের করে (Pop) DFS চালান। প্রতিটি DFS কলে আপনি যে ভার্টেক্সগুলো পাবেন, তারা সবাই মিলে একটি নির্দিষ্ট SCC তৈরি করবে।

কেন এটি কাজ করে? কারণ স্ট্যাকের অর্ডার আমাদের গ্যারান্টি দেয় যে আমরা প্রতিটি নতুন গ্রুপের কাজ শুরু করছি সঠিক জায়গা থেকে। যেহেতু আমরা উল্টানো গ্রাফে কাজ করছি, আমরা ভুল করে অন্য কোনো SCC-তে ঢুকে যেতে পারবো না — আমরা একটি গ্রুপের মধ্যেই সীমাবদ্ধ থাকবো।

কনডেনসেশন ডিএজি (Condensation DAG)

সবগুলো SCC খুঁজে পাওয়ার পর, আপনি প্রতিটি গ্রুপকে একটি মাত্র নোড বা বিন্দু হিসেবে কল্পনা করতে পারেন। এই নতুন নোডগুলোর মধ্যে সংযোগ দিলে যে গ্রাফটি পাওয়া যায় তা সবসময় একটি DAG (Directed Acyclic Graph) হবে। অর্থাৎ এই নতুন নোডগুলোর মধ্যে কোনো লুপ বা সাইকেল থাকবে না। যদি থাকত, তবে ওই গ্রুপগুলো মিলেই একটি বড় SCC হয়ে যেত!