টপোলজিকাল সর্ট কি?

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0″. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0″. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no in-coming edges).

Source- wikipedia

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

১. সকালের নাস্তা —> অফিস (ক—>খ এর মানে হলো ‘খ’ কাজটি করার আগে ‘ক’ কাজটি করতে হবে)
২. সুট-টাই পড়া —-> অফিস
৩. অফিস —-> ইমেইল
৪. অফিস —-> ডিনার
৫. অফিস —-> খেলা
৬. ইমেইল —> ডিনার
৭. ইমেইল —> খেলা
৮. ডিনার —> খেলা

আপনি এখন কোন কাজ কখন করবেন? উল্টাপাল্টা অর্ডারে করলে আপনার কাজ ভন্ডুল হয়ে যাবে,ইমেইল না করে খেলা দেখতে বসলে আপনি ক্লায়েন্ট হারাবেন,তাই অর্ডারিং খুব জরুরি।

এটা একটি “টাস্ক শিডিউলিং” প্রবলেম। কোন কাজের পর কোন কাজ করতে হবে সেটা আমাদের বের করতে হবে। অর্থাৎ এটা এক ধরণের সর্টিং। এই সর্টিংকে টপোলোজিকাল সর্টিং বলে।

অনেকেই এই সর্টিংকে টপ সর্ট বলেও অভিহিত করে থাকেন।

টপ সর্ট হল একটা  অ্যালগোরিদম। সহজ ভাষায়-  আমি কিভাবে আমার জিনিসগুলো সাজাব তা আমি টপ সর্ট করে বের করে ফেলতে পারব।