BFS, DFS in Python

BFS(Breadth First Search) : 너비 우선 탐색

• 우선 순위를 너비에 먼저 두는 탐색 알고리즘

List 활용(Queue)

• 인접 노드 중 방문하지 않았던 노드의 정보만 List.append()를 통해 입력하고 List.pop(0)을 통해 출력

  def BFS_with_list(graph, root):
      visited = []
      list = [root]
  
      while list:
          n = list.pop()
          if n not in visited:
              visited.append(n)
              list += graph[n] - set(visited)
      return visited
  

  • 시간복잡도가 $O(N)$이라 비효율적인 코드 생산

Queue 활용

• 인접 노드 중 방문하지 않았던 노드의 정보만 Queue에 넣어 먼저 Queue에 있던 노드부터 방문

  from collections import deque
  
  def BFS_with_adj_list(graph, root):
      visited = []
      queue = deque([root])
  
      while queue:
          n = queue.popleft()
          if n not in visited:
              visited.append(n)
              queue += graph[n] - set(visited)
      return visited
    
  print(BFS_with_adj_list(graph_list, root_node))

• Deque
  • 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요
  • Deque는 O(1)로 접근 가능
  • Push/Pop 문제들의 경우 빠르게 해결 가능

DFS(Depth First Search) : 깊이 우선 탐색

• 우선 순위를 깊게 탐색하는거에 두는 탐색 알고리즘

Stack 활용

• 먼저 방문한 노드에 연결된 노드보다 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 이동 가능

def DFS_with_stack(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited