জাভাস্ক্রিপ্ট ডিএফএস ব্যবহার করে টপোলজিক্যাল বাছাই

নির্দেশিত গ্রাফের একটি টপোলজিকাল বাছাই বা টপোলজিকাল ক্রম হল এর শীর্ষবিন্দুগুলির একটি রৈখিক ক্রম যাতে শীর্ষবিন্দু u থেকে শীর্ষবিন্দু v পর্যন্ত প্রতিটি নির্দেশিত প্রান্ত UV-এর জন্য, ক্রমানুসারে v এর আগে u আসে। এটি শুধুমাত্র নির্দেশিত গ্রাফগুলিতেই বোঝা যায়৷

এমন অনেক জায়গা আছে যেখানে টপোলজিকাল সাজানোর অনেক অর্থ হয়। উদাহরণ স্বরূপ, ধরা যাক আপনি একটি রেসিপি অনুসরণ করছেন, এতে কিছু ধাপ রয়েছে যা পরবর্তী ধাপে যাওয়ার জন্য আবশ্যক। তবে এর মধ্যে কিছু সমান্তরালভাবে সম্পাদন করা যেতে পারে। একইভাবে, কলেজের সময় কোর্স নির্বাচন করার সময়, আরও উন্নত কোর্সের জন্য কিছু পূর্বশর্ত রয়েছে যা পরবর্তী কোর্সের জন্য পূর্বশর্ত হতে পারে। যেমন −

উদাহরণ

 /** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | /* CS540*/

উপরের গ্রাফে, বিবেচনা করুন আপনি যদি কোর্সটি একটি স্তরে নিতে চান তবে আপনাকে প্রথমে এটির উপরের স্তর থেকে সংযুক্ত সমস্ত কোর্স নিতে হবে৷ উপরের গ্রাফ -

CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540 

 জাভাস্ক্রিপ্টে এটি বাস্তবায়ন করা যাক। আমরা গ্রাফটিকে পুনরাবৃত্তভাবে চিহ্নিত করতে এবং অন্বেষণ করতে সাহায্য করার জন্য 2টি ফাংশন, টপোলজিকাল সর্ট এবং টপোলজিক্যাল সর্টহেল্পার লিখব। 
 
উদাহরণ
 
টপোলজিকালসোর্টহেল্পার(নোড, অন্বেষণ করা, গুলি) { explored.add(node); // এই নোডটিকে পরিদর্শন করা হিসাবে চিহ্নিত করে এবং নোডগুলিতে চলে যায় // যেগুলি এই নোডের উপর নির্ভরশীল, প্রান্তটি নোড ----> n this.edges[node].forEach(n => { if (!explored. আছে(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); } }); যখন (!s.isEmpty()) { console.log(s.pop()); }}
 

 আপনি − 
 ব্যবহার করে এটি পরীক্ষা করতে পারেন 
উদাহরণ
 
 let g =new Graph();g.addNode("A");g.addNode("B");g.addNode("C");g.addNode("D");g.addNode("D"); ("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 * / | \ * গ | বি*\ | | *ডি জি* | *ই* | * F*/
 
আউটপুট
 

 এটি আউটপুট দেবে −
 
ABGCDEF