알고리즘 깊이 우선 탐색(DFS)

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

 

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때 까지 계속 다가다 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 넓게 탐색하기 전에 깊에 탐색하는 것이다.
• 사용하는 경우 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

깊이 우선 탐색(DFS)의 특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
2. 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다
3. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
4. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

 

깊이 우선 탐색(DFS)의 구현 방법 2가지

1. 순환 호출 이용
2. 명시적인 스택 사용 - 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장했다가 다시 꺼내서 작업한다.

 

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

DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)
• 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

 

 

참조

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://en.wikipedia.org/wiki/Depth-first_search