একটি ডাইরেক্টেড গ্রাফের একটি টপোলজিক্যাল সর্ট বা টপোলজিক্যাল অর্ডারিং হলো এর ভারটেক্সগুলোর একটি লিনিয়ার অর্ডারিং যাতে প্রতিটি ডাইরেক্টেড এজ UV (ভারটেক্স u থেকে ভারটেক্স v-এ) এর জন্য, u অর্ডারিং-এ v-এর আগে আসে। এটি শুধু ডাইরেক্টেড গ্রাফে মানে রাখে।
অনেক জায়গায় টপোলজিক্যাল সর্ট অনেক মানে রাখে। উদাহরণস্বরূপ, ধরুন আপনি একটি রেসিপি ফলো করছেন, এখানে কিছু স্টেপ আছে যা পরবর্তী স্টেপে যেতে আবশ্যক। কিন্তু কিছু স্টেপ প্যারালেলভাবে করা যায়। একই রকম, কলেজে কোর্স সিলেক্ট করার সময়, আরও এডভান্সড কোর্সের জন্য কিছু প্রেরিকোয়েজিট থাকে যেগুলো আবার আরও কোর্সের প্রেরিকোয়েজিট হতে পারে। উদাহরণস্বরূপ:
উদাহরণ
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
উপরের গ্রাফে, বিবেচনা করুন আপনি এক লেভেলের কোর্স করতে চান, তবে আপনাকে প্রথমে সেটির সাথে উপরের লেভেল থেকে কানেক্টেড সব কোর্স করতে হবে। উপরের গ্রাফের কিছু সম্ভাব্য টপোলজিক্যাল সর্ট নিচে দেওয়া হলো:
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
আসুন এটি জাভাস্ক্রিপ্টে বাস্তবায়ন করি। আমরা ২টি ফাংশন লিখব: topologicalSort, এবং topologicalSortHelper রিকারসিভলি মার্ক এবং এক্সপ্লোর করতে গ্রাফকে।
উদাহরণ
topologicalSortHelper(node, explored, s) {
explored.add(node);
// এই নোডকে ভিজিটেড মার্ক করে এবং সেই নোডগুলোর ওপর যেতে থাকে
// যা এই নোডের ওপর ডিপেন্ডেন্ট, এজটি node ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// এই নোডের সব ডিপেন্ডেন্সি রেজলভ হয়েছে, এখন আমরা এটিকে স্ট্যাকে যোগ করতে পারি।
s.push(node);
}
topologicalSort() {
// সর্টেড অর্ডারে সব এলিমেন্ট ট্র্যাক রাখতে একটি স্ট্যাক তৈরি করুন
let s = new Stack(this.nodes.length);
let explored = new Set();
// আমাদের গ্রাফের প্রতিটি আনভিজিটেড নোডের জন্য, হেল্পার কল করুন।
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}
আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:
উদাহরণ
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort();
আমরা যে গ্রাফটি তৈরি করেছি সেটি দেখতে এরকম:
উদাহরণ
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
আউটপুট
এটি নিচের আউটপুট দেবে:
A B G C D E F
