Breadth-First Search
code: python
from collections import deque
# V: 頂点 E: 辺
# O(V + E), O(V)
def bfs(graph, start):
visited = set()
res = []
queue = deque(start)
while queue:
# FIFO
now = queue.popleft()
if now not in visited:
visited.add(now)
res.append(now)
for v in graphnow:
queue.append(v)
return res
graph = {
'A': 'B', 'C', 'D',
'B': 'A', 'E', 'F',
'C': 'A', 'H',
'D': 'A', 'I', 'J',
'E': 'B', 'K',
'F': 'B',
'G': 'H',
'H': 'C', 'G',
'I': 'D',
'J': 'D', 'L',
'K': 'E',
'L': 'J'
}
def test_bfs():
assert bfs(graph, 'A') == 'A', 'B', 'C', 'D', 'E', 'F', 'H', 'I', 'J', 'K', 'G', 'L'