টপোলজিক্যাল বাছাই

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

যেহেতু আমরা জানি যে উত্স শীর্ষবিন্দুটি গন্তব্য শীর্ষস্থানের পরে আসবে, তাই আমাদের পূর্ববর্তী উপাদানগুলি সংরক্ষণ করতে একটি স্ট্যাক ব্যবহার করতে হবে। সমস্ত নোড সম্পূর্ণ করার পরে, আমরা কেবল স্ট্যাক থেকে তাদের প্রদর্শন করতে পারি।

ইনপুট এবং আউটপুট

ইনপুট:0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 00 1 0 0 0 01 1 0 0 0 01 0 1 0 0 0 আউটপুট:টপোলজিকাল সাজানো অর্ডারের পরে নোডগুলি:5 4 2 <31 /প্রে> 
অ্যালগরিদম
 

 topoSort(u, পরিদর্শন করা, স্ট্যাক) 
 

 ইনপুট - স্টার্ট vertex u, কোন নোড পরিদর্শন করা হয়েছে বা না তা ট্র্যাক রাখার জন্য একটি অ্যারে। নোড স্টোর করার জন্য একটি স্ট্যাক। 
 আউটপুট - স্ট্যাকের মধ্যে শীর্ষবিন্দুগুলিকে টপোলজিক্যাল ক্রম অনুসারে সাজানো।
 
 u-এর সংলগ্ন সমস্ত শীর্ষবিন্দু v-এর জন্য u-কে পরিদর্শন করা হিসাবে চিহ্নিত করুন, যদি v পরিদর্শন না করা হয়, তাহলে topoSort(c, পরিদর্শন করা, স্ট্যাক) করা হয়েছে uকে একটি স্ট্যাকের মধ্যে ঠেলে
 

 পারফর্ম টপোলজিক্যাল সর্টিং(গ্রাফ) 
 

 ইনপুট - প্রদত্ত নির্দেশিত অ্যাসাইক্লিক গ্রাফ। 
 আউটপুট - নোডের ক্রম।
 
শুরু করুন গ্রাফের সমস্ত নোড v-এর জন্য সমস্ত নোডকে দেখা না হওয়া হিসাবে চিহ্নিত করুন, যদি v ভিজিট না করা হয়, তাহলে topoSort(i, পরিদর্শন করা, স্ট্যাক) পপ করে স্ট্যাকএন্ড থেকে সমস্ত উপাদান প্রিন্ট করুন।
 
উদাহরণ
 
#include#include#define NODE 6 ব্যবহার করে namespace std;int গ্রাফ[NODE][NODE] ={ {0, 0, 0, 0, 0, 0}, {0, 0, 0 , 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0}};void topoSort(int u, bool visited[], stack&stk) { পরিদর্শন করা[u] =সত্য; নোড v হিসাবে সেট করুন (int v =0; v stk; bool vis [NODE]; for(int i =0; i 
আউটপুট
 
টপোলজিক্যাল সাজানো অর্ডারের পরে নোড:5 4 2 3 1 0