깊이 우선 탐색(DFS)알고리즘
August 18, 2020
탐색 알고리즘을 공부하다 보면 깊이 우선 탐색(이하 DFS) 알고리즘과 너비 우선 탐색(이하 BFS) 알고리즘을 주로 다룬다.
오늘은 깊이 우선 탐색(DFS) 알고리즘에 대해 공부한 내용을 작성하고자 한다.
개념
위키백과에 따르면 DFS알고리즘의 개념은 다음과 같다.
깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.
이 정의를 쉽게 풀어쓰면 다음과 같다.
자식을 갖고 있는 트리(tree)구조를 띄고 있을 때 형제 노드가 아닌 자식 노드를 먼저 방문하는 알고리즘
DFS 알고리즘은 2가지 방법을 사용하여 구현이 가능하다. 주로 재귀(순환 알고리즘)호출을 사용하는 것과 스택(Stack)구조를 사용하여 구현하는 방법이 있다.
특징
- 재귀적인 순환 알고리즘의 형태이다.
- 어떤 노드를 방문 했는지 반드시 검사 해야한다.
시간 복잡도
DFS의 시간 복잡도는 다음과 같다. (정점의 수: N, 간선의 갯수: E)
- 리스트로 구현된 그래프 : O(N+E)
- 행렬로 구현된 그래프 : O(N^2)구현
python을 사용하여 DFS 알고리즘을 구현하면 다음과 같다.
-
재귀를 이용한 구현
def dfs(graph, start_node, visit = list()): visit.append(start_node) for node in graph[start_node]: if node not in visit: dfs(graph, node, visit) return visit -
스택을 이용한 구현
def dfs(graph, start_node): visit = list() stack = list() stack.append(start_node) while stack: node = stack.pop() if node not in visit: visit.append(node) stack.extend(graph[node]) return visit
DFS와 BFS의 차이
- 그림에서 볼 수 있듯이 BFS는 시작 접점을 시작으로 가장 인접한 노드를 방문한다.
- 반면 DFS는 방문한 접점을 기준으로 자식 노드를 방문하게 된다.
