[python/자료구조] DFS 와 BFS

 

1. DFS ( Depth First Search ) _ 깊이 우선 탐색이란?

---

하나의 경우의 수에 대하여 모든 경우의 수를 조사하면서 해를 찾는 과정으로 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택(후입선출)의 자료구조 또는 재귀함수를 활용한다.

위 그래프의 경우 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5 순서대로 탐색하며 코드로 구현하면 다음과 같다.

  
  def dfs(graph, v, visited):
     visited[v] = True   # 현재 노드를 방문 처리
     print(v, end=' ')
     for i in graph[v]:   # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
         if not visited[i]:
             dfs(graph, i, visited)
             
  graph = [ [ ], [2,3,8], [1,7], [1,4,5], [3, 5], [3,5], [7], [2,6,8], [1,7] ]

  visited = [False] * 9

  dfs(graph, 1, visited)
 

< 실행 결과 >

1 2 7 6 8 3 4 5

 

2. BFS ( Breadth First Search ) _ 너비 우선 탐색이란?

---

하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정으로 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐(선입선출)의 자료구조를 활용한다.

위 그래프의 경우 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6 순서대로 탐색하며 코드로 구현하면 다음과 같다.

  from collections import deque

  def bfs(graph, start, visited):
      queue = deque( [start] )  # deque 라이브러리 사용
      visited[start] = True  # 노드 방문 처리
      while queue :
          v = queue.popleft()  # 원소를 뽑아 출력
          print( v, end=' ' )
          for i in graph[v]:  # 방문하지 않은 진접한 원소들을 큐에 삽입
              if not visited[i]:
                   queue.append(i)
                   visited[i] = True
                   
  graph = [ [ ], [2,3,8], [1,7], [1,4,5], [3, 5], [3,5], [7], [2,6,8], [1,7] ]

  visited = [False] * 9

  dfs(graph, 1, visited)
                       

< 실행 결과 >

1 2 3 8 7 4 5 6