جواب «BFS Order» چالش 5 از جلسهی 35
سؤال
ورودی: یالهای یک گراف بدون جهت <a> <b> تا end و سپس یک خط گرهی شروع. با BFS و deque گرهها را به ترتیب بازدید با فاصله چاپ کنید؛ همسایههای هر گره را به ترتیب الفبایی بررسی کنید. (گره شروع حتماً در گراف هست.)
راهنما
هنگام افزودن به صف علامت بازدید بزنید، نه هنگام برداشتن؛ وگرنه یک گره چند بار وارد صف میشود.
یک جواب درست
from collections import defaultdict, deque
graph = defaultdict(list)
while True:
line = input()
if line == "end":
break
a, b = line.split()
graph[a].append(b)
graph[b].append(a)
start = input()
seen = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in sorted(graph[node]):
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)
print(*order)
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن