Module: جستجوی عمیق DFS


Problem

1/12

DFS: شروع (C++)

Theory Click to read/hide

DFS DFS
جستجوی اول عمق (DFS) یکی از الگوریتم های اصلی در نمودارها است. الگوریتم در O(N + M) اجرا می شود.
 
الگوریتم
برای شروع، از بالا شروع می کنیم، فرزندان این بالا را در نظر می گیریم و اگر هرگز آنها را وارد نکرده ایم، DFS را از آنها شروع می کنیم.


Problem

روشی بنویسید void dfs (int v) که عمق یک گراف بدون جهت را از راس شروع S می‌پیماید و همه رئوس را به ترتیب پیمایش خروجی می‌دهد و از راس شروع می‌شود. S با یک فاصله در یک خط جدا شده است.

خط اول شامل سه عدد N ؛ - تعداد رئوس در نمودار، M - تعداد یال‌ها، S - شروع راس در خطوط M زیر، 2 متغیر Ui و Vi ارائه می شوند ، شرح لبه های نمودار. همه اعداد در ورودی از 1000 تجاوز نمی کنند.

خروجی همه رئوس به ترتیب پیمایش توسط DFS.

در برنامه فوق، g[i][j] به این معنی است که بین رئوس i و j یک یال وجود دارد و در آرایه استفاده شده علامت گذاری می کنیم که آیا از این پیک بازدید کرده ایم.