[python] 깊이 우선 탐색(DFS)

그래프의 탐색

그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

Ex) 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 연결되어 있지 않은지

 

 

 

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

깊이 우선 탐색이란?

깊이 우선 탐색(DFS)은 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

 

이와 같은 그래프가 있을 경우 DFS는 한 방향으로 진행된다.

그래프의 시작 정점에서 출발하여 시작 정점 v (1)를 방문하였다고 표시한다. 이어서 v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u (2)를 선택한다. 만약 그러한 정점이 없다면 탐색은 종료된다. 만약 아직 방문하지 않은 정점 u (1 > 2 > 5 > 8의 탐색이 끝난 후에는 3을 선택)가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다. 이러한 과정을 계속 반복한다.

위의 과정을 반복하면 해당 그래프의 순서는 1 > 2 > 5 > 8 > 3 > 6 > 7 > 4가 된다.

 

 

깊이 우선 탐색의 구현

깊이 우선 탐색은 재귀 혹은 스택을 사용하여 구현할 수 있다. 그러나 재귀 또한 함수가 호출될 때 스택 메모리에 계속해서 쌓이는 방식으로 호출되기 때문에, 이론적으론 스택과 동일한 원리로 사용된다고 볼 수 있다.

 

데이터

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']

 

 

구현1 - 리스트 활용

# list 사용
def dfs_list(graph, start_node):
  
  # 항상 두개의 리스트를 별도로 관리
  need_visited, visited = list(), list()
  
  # 시작 노드 설정
  need_visited.append(start_node)
  
  # 방문이 필요한 노드가 있다면
  while need_visited:
    # 그 중에서 마지막 데이터를 추출 (스택 구조 사용)
    node = need_visited.pop()
    
    # 만약 해당 노드가 방문 목록에 없다면
    if node not in visited:
      # 방문 목록에 추가
      visited.append(node)
      
      # 그 노드에 연결된 노드를
      need_visited.extend(graph[node])
  
  return visited

 

구현2 - deque 사용

# deque 사용
def dfs_deque(graph, start_node):
  # deque 패키지 
  from collections import deque
  visited = []
  need_visited = deque()
  
  # 시작 노드 설정
  need_visited.append(start_node)
  
  # 방문이 필요한 리스트가 아직 존재한다면
  while need_visited:
    # 시작 노드를 지정
    node = need_visited.popleft()
    
    # 만약 방문 리스트에 없다면
    if node not in visited:
      # 방문 리스트에 노드를 추가
      visited.append(node)
      
      # 인접 노드들을 방문 예정 리스트에 추가
      need_visited.extend(graph[node])
  
  return visited

 

구현3 - 재귀함수 사용

# 재귀 함수 사용
def dfs_recursive(graph, start, visited = []):
  # 데이터를 추가하는 명령어 / 재귀가 이루어짐
  visited.append(start)
  
  for node in graph[start]:
    if node not in visited:
      dfs_recursive(graph, node, visited)
  
  return visited

 

깊이 우선 탐색의 시간 복잡도

깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 리스트로 표현되어 있다면 시간 복잡도가 O(n+e)이고, 인접 행렬로 표시되어 있다면 O(n^2)이다.

 

 

장단점

장점으로 현재 탐색하고 있는 노드만 기억하면 되기 때문에 비교적 저장 공간에 대한 수요가 적다.

단점으로는 그래프의 깊이가 무한할 경우 해를 찾을 수 없는 가능성이 있다는 점이다. 또한 해를 구하더라고 이것이 최단 경로의 해가 아닐 수 있다.

 

 

참고

https://kmight0518.tistory.com/24

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=183868288

https://data-marketing-bk.tistory.com/44

DFS 완벽 구현하기 - 파이썬

C언어로 쉽게 풀어쓴 자료구조

[알고리즘 이론] 4. 깊이 우선 탐색(DFS)