C প্রোগ্রামে 1 থেকে শুরু হওয়া গ্রাফের অভিধানিকভাবে ক্ষুদ্রতম DFS প্রিন্ট করুন।

আমাদের N শীর্ষবিন্দু এবং M প্রান্ত সহ একটি সংযুক্ত গ্রাফ দেওয়া হবে। তাই আমাদের 1 থেকে শুরু হওয়া গ্রাফের অভিধানিকভাবে ক্ষুদ্রতম DFS প্রিন্ট করতে হবে।

শীর্ষবিন্দুগুলিকে 1 থেকে N

পর্যন্ত নম্বর দেওয়া উচিত৷

উদাহরণ

ইনপুট:N =5 M =5 edge(1, 4, arr) edge(3, 4, arr) edge(5, 4, arr) edge(3, 2, arr) edge(1, 5, arr) ) edge(1, 2, arr) edge(3, 5, arr) edge(1, 3, arr)আউটপুট:1 2 3 4 5

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

নীচে দেওয়া অ্যালগরিদমের C++ বাস্তবায়ন নিচে দেওয়া হল।

অ্যালগরিদম

StartStep 1 -> Declare function void lexo(vector* arr, int n) declare bool check[n + 1] ={ 0 } int i=0 এবং i ফাংশন ভয়েড এজ ঘোষণা করুন(int u, int v, vector* arr) Call ar[u].push_back(v) Call ar[v].push_back(u) ধাপ 3 -> ফাংশন ভ্যায়েড গ্রাফ ঘোষণা করুন(ভেক্টর* arr, int src, int n,bool* check) প্রিন্ট src সেট চেক[src] =int i =0 এবং i  In main() Declare int n =5, m =5 STL ভেক্টর  arr[n + ব্যবহার করুন 1] কল প্রান্ত (1,4, arr) কল প্রান্ত (3,4, arr).... কল লেক্সো(arr, n)Stop

উদাহরণ

একটি edgevoid প্রান্ত (int u, int v, vector* arr){ arr[u].push_back(v); arr[v].push_back(u);}// dfs গ্রাফ ট্র্যাভারসালভয়েড গ্রাফের জন্য ফাংশন(ভেক্টর* arr, int src, int n,bool* check){ cout <* arr, int n){ bool check[n + 1] ={ 0 }; জন্য (int i =0; i arr[n + 1]; // একটি প্রান্ত প্রান্ত সন্নিবেশ করার জন্য (1, 4, arr); প্রান্ত (3, 4, arr); প্রান্ত (5, 4, arr); প্রান্ত (3, 2, arr); edge(1, 5, arr); edge(1, 2, arr); প্রান্ত (3, 5, arr); প্রান্ত (1, 3, আরআর); //কল লেক্সো ফাংশন লেক্সো(আর,এন); রিটার্ন 0;

আউটপুট

যদি আমরা উপরের প্রোগ্রামটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে

1 2 3 4 5