deque로 BFS, DFS 구현

BFS

DFS

소스코드

• 주의사항!
  • 각 노드에 연결된 자식 노드들은 꼭 정렬이 되어 있어야 한다!
  • bfs, dfs 둘 다 앞에서부터 빠져나가는 식으로 구현했으므로 popleft를 사용함
  • dfs의 경우 extendleft로 왼쪽에 자식 노드를 추가해서 맨앞부터 빠져나가기 편하게 구현! 
  • extendleft를 사용할 때 예를 들어 [1, 2, 3]을 extendleft하면 [3, 2, 1] 순으로 deque의 왼쪽에 붙으므로 한번 reversed 해서 붙여줌!

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

from collections import deque

def bfs(graph, start_node):
    visited = list()  # 방문한 노드
    need_visit = deque()  # 방문할 노드

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:  # 방문한 적이 없다면
            visited.append(node)  # 방문한 노드에 추가
            need_visit.extend((graph[node]))  # 꺼낸 노드와 인접한 노드를 넣어줌

    return visited

def dfs(graph, start_node):
    visited = list() #방문한 노드
    need_visit = deque() #방문할 노드

    need_visit.append(start_node)

    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit.extendleft(reversed(graph[node]))

    return visited

print(bfs(graph, 'A'))
print(dfs(graph, 'A'))