Depth-First Search (queue)
code: python
from collections import deque
# V: 頂点 E: 辺
# O(V + E), O(V)
def dfs(graph, start):
visited = set()
res = []
queue = deque(start)
while queue:
# LIFO
now = queue.pop()
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_dfs():
assert dfs(graph, 'A') == 'A', 'D', 'J', 'L', 'I', 'C', 'H', 'G', 'B', 'F', 'E', 'K'