Module: BFS - Genişlik Yürüyüşü


Problem

2/6

BFS: Başlangıç ​​(Python)

Theory Click to read/hide

BFS (genişlik öncelikli arama), hem basit hem de gelişmiş algoritmalarda sıklıkla kullanılan bir grafik çaprazlama yöntemidir. Genişlik Öncelikli Arama, kaynak düğümden başlayarak ve kademeli olarak ondan uzaklaşarak grafiğin bireysel seviyeleri arasında adım atarak çalışır. Bu, animasyonda açıkça gösterilmiştir.

Basit bir BFS yazmak için, bir kuyrukla çalışabilmeniz, baştan alıp sona koymanıza olanak tanıyan bir veri yapısı ve ayrıca formda bir grafik depolayabilmeniz gerekir. bir komşuluk listesi.
 
Algoritmanın resmi açıklaması
1) Aramanın başladığı köşe numarasını başlangıçta boş olan kuyruğa yerleştirin.
2) Kuyruğun başından U köşesini çıkarın ve ayrı bir dizide kullanılmış olarak işaretleyin.
3) Kuyruğun sonuna, U köşesinden kenarı kullanarak ulaşabileceğimiz ve henüz işaretlenmemiş tüm köşeleri ekleyin.
4) Kuyruk boşsa, bağlı grafiğin tüm düğümleri taranmıştır, aksi halde 2. adıma dönün.
 
İşin zorluğu
En kötü durumda, algoritma grafiğin tüm düğümlerini ziyaret ettiğinden, grafiği bitişik listeler biçiminde saklarken, algoritmanın zaman karmaşıklığı O(|V| + |E|), burada V kümedir grafiğin köşelerinin sayısı ve E kenarların kümesidir.  ;
Başka bir deyişle, algoritma kenar sayısı + köşe sayısı için en kötü durumda çalışır.

 

Problem

Bazı köyler, yönsüz bir grafik olarak temsil edilebilecek yollarla birbirine bağlıdır. Bu grafiğin köşeleri köyler ve kenarları köyler arasındaki yollar (grafik döngüler içerebilir). Köyde S bir artel Seyyar satıcılar. Her sabah seyyar satıcılar, küçük tuhafiyelerini satmak için henüz gidilmemiş ve şimdiki yoldan yol bulunan köylere giderler. Seyyar satıcılar arteli, mevcut köyden yolu olan bütün köyleri bir günde dolaşsınlar diye hep gruplara ayrılır.
Seyyar satıcılar bütün köyleri kaç günde ziyaret ederler? Sorunun yanıtını döndürecek bir \(bfs()\) işlevi yazın.


Girdi
İlk satır 3 tam sayı içerir n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - köy sayısı, aralarındaki yol sayısı ve seyyar satıcı çetesinin bulunduğu köyün numarası.  ;Aşağıdaki m< /code> satırlarının her biri 2 sayı içerir u, v(\(1 < = u, v <= n\ )) - aralarında yol bulunan iki köyün sayısı. Köyler 1 ile dizine eklenir.

Künye
Tek bir sayı yazdırın - seyyar satıcıların tüm köyleri ziyaret etmesi kaç gün sürer.
 
 
Örnekler

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
# Girdi Çıktı
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
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!