Module: BFS - پیاده روی عرض


Problem

2/6

BFS: Beginning (Python)

Theory Click to read/hide

BFS (جستجوی اول عرض) یک روش پیمایش گراف است که اغلب در الگوریتم های ساده و پیشرفته استفاده می شود. جستجوی Breadth-First با قدم گذاشتن در سطوح جداگانه نمودار، شروع از گره منبع و دور شدن تدریجی از آن کار می کند. این به وضوح در انیمیشن نشان داده شده است.

برای نوشتن یک BFS ساده، باید بتوانید با یک صف کار کنید، ساختار داده ای که به شما امکان می دهد از ابتدا  بردارید و آن را تا آخر قرار دهید و همچنین بتوانید یک نمودار را در فرم ذخیره کنید. از یک لیست مجاورت.
 
توضیحات رسمی الگوریتم
1) شماره رأسی را که جستجو از آن شروع می شود در صف اولیه خالی قرار دهید.
2) راس U را از ابتدای صف استخراج کنید و آن را به عنوان مورد استفاده در یک آرایه جداگانه علامت گذاری کنید.
3) در انتهای صف، تمام رئوسی را که می توانیم با استفاده از لبه از راس U به آنها برسیم و هنوز علامت گذاری نشده اند، اضافه کنیم.
4) اگر صف خالی باشد، تمام گره های گراف متصل شده اسکن شده اند، در غیر این صورت به مرحله 2 برگردید.
 
سختی کار
از آنجایی که در بدترین حالت، الگوریتم از تمام گره‌های گراف بازدید می‌کند، هنگام ذخیره نمودار در قالب لیست‌های مجاورت، پیچیدگی زمانی الگوریتم O(|V| + |E|) است، که در آن V مجموعه است. از رئوس نمودار، و E مجموعه ای از یال ها است.  ;
به عبارت دیگر، الگوریتم در بدترین حالت برای تعداد یال ها + تعداد رئوس کار می کند.

 

Problem

برخی از روستاها با جاده هایی به هم متصل می شوند که می توان آنها را به عنوان یک گراف جهت نشده نشان داد. رئوس این نمودار روستاها و لبه ها جاده های بین روستاها هستند (گراف ممکن است شامل چرخه باشد). مشخص است که در روستا S یک آرتل دستفروشان. دستفروشان هر روز صبح برای فروش مغازه خرطومی کوچک خود به روستاهایی می روند که هنوز به آنها سر نزده اند و از جاده فعلی به آنها راهی وجود دارد. دستفروشان همیشه به گروه‌هایی تقسیم می‌شوند تا بتوانند در یک روز تمام روستاهایی را که جاده‌ای از روستای کنونی دارند، بچرخند.
دستفروشان چند روز دیگر به همه روستاها سر می زنند؟ یک تابع \(bfs()\) بنویسید که پاسخ مسئله را برمی گرداند.


ورودی
خط اول شامل 3 عدد صحیح n، m، s (\(1 < = n <= 10^5\)، \(0 <= m <= 10^5\)، \(1 <= s <= n\)) - تعداد روستاها، تعداد جاده های بین آنها و تعداد روستایی که گروه دستفروشان در آن مستقر هستند.  ;در خطوط m< /code> زیر شامل 2 عدد u، v(\(1 < = u, v <= n\ )) - شماره دو روستا که بین آنها جاده وجود دارد. روستاها با 1 نمایه می شوند.

حصر
یک عدد چاپ کنید - چند روز طول می کشد که دستفروشان از همه روستاها بازدید کنند.
 
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 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 bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

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