** DFS와 BFS

DFS

깊이 우선 탐색. 한 갈래를 정해서 바닥까지 내려간 후, 다시 루트 노드로 올라와 그 다음 갈래로 내려감.

• DFS는 스택으로 구현.
• 인접노드를 나타내는 딕셔너리를 미리 만들어두고 진행해야만 함.

graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
}


def dfs_stack(adjacent_graph, start_node):
  stack = [start_node]
  visited = []
  
  while stack:
    current_node = stack.pop()
    visited.append(current_node)
    for adjacent_node in adjacent_graph[current_node]:
      if adjacent_node not in visited:
        stack.append(adjacent_node)
  return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

BFS

너비 우선 탐색. 한 레벨씩 훑으면서 내려감.

• BFS는 큐를 이용함.
• 인접노드를 나타내는 딕셔너리를 미리 만들어두고 진행해야만 함.

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
  1: [2, 3, 4],
  2: [1, 5],
  3: [1, 6, 7],
  4: [1, 8],
  5: [2, 9],
  6: [3, 10],
  7: [3],
  8: [4],
  9: [5],
  10: [6]
}

def bfs_queue(adj_graph, start_node):
  queue = [start_node]
  visited = []

  while queue:
      current_node = queue.pop(0)
      visited.append(current_node)
      for adjacent_node in adj_graph[current_node]:
          if adjacent_node not in visited:
              queue.append(adjacent_node)

  return visited

print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

• 참고 자료