Пошук у ширину
Пошук в ширину використовує структуру даних черга.
Тобто, чим раніше відвідана вершина (поміщається в чергу), тим раніше вона використовується (видаляється з черги). Використання вершини відбувається за допомогою перегляду відразу усіх ще непереглянутих сусідів цієї вершини.
Прикладом обходу в ширину може бути поширення інформації про хворобу вчителя. Спочатку один учень, зазвичай староста, взнає про хворобу вчителя і цю важливу інформацію треба поширити серед учнів школи. Що робить учень, він іде і всім, кого зустрічає, розповідає про це. Потім всі ті, кому відома ця інформація, зустрічають інших, кому ще невідома ця інформація, і повідомляють її. Інформація поширюється майже миттєво.
Теорія
Пошук у ширину.pptxЗадача
g={}
g[0]=[1,3]
g[1]=[0,2,3,4]
g[2]=[1,3,4]
g[3]=[0,1,2]
g[4]=[1,2]
a=0
b=6
cherga=[]
cherga.append(a)
seenFrom=[n]*n
seenFrom[a]=a
while cherga:
if b not in cherga:
k=cherga.pop(0)
else:
break
for i in g1[k]:
cherga.append(i)
if seenFrom[i]==n:
seenFrom[i]=k
# роздрук шляху до вершини зі списку seenFrom
print(b) # друк кінцевої вершини
while seenFrom[b]!=b: # поки значення вершини не рівне її назві
print(seenFrom[b]) # друкуємо значення вершини (це вершина, з якої ми побачили цю)
b=seenFrom[b] # переходимо до вершини, з якої побачили цю