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


Problem

2/12

DFS: Start (Python)

Theory Click to read/hide

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


Problem

روشی بنویسید def dfs(v) که عمق یک گراف بدون جهت را از راس شروع S طی می‌کند و همه راس‌ها را به ترتیب پیمایش خروجی می‌دهد، با شروع از راس < code>S با یک فاصله در یک خط جدا شده است.

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

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

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

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def dfs(start):      
n, m, s = map(int, input().split())
Visited = [False]*(n+1)
V = [set() for i in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    V[u].add(v)
    V[v].add(u)

dfs(s)

     

Program check result

To check the solution of the problem, you need to register or log in!