깊이 우선 탐색
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
깊이 우선 탐색(DFS)은 그래프 또는 트리 구조를 탐색하는 알고리즘으로, 시작 노드에서 최대한 깊이 탐색한 후, 막히면 이전 노드로 돌아가 다른 경로를 탐색하는 방식이다. 깊이 제한을 두어 무한정 깊이 탐색하는 것을 막고, 백트래킹을 통해 탐색 경로를 조절한다. DFS는 재귀적 또는 비재귀적으로 구현할 수 있으며, 시간 복잡도는 \(O(|V| + |E|)\)이고, 공간 복잡도는 최악의 경우 \(O(|V|)\)이다. DFS는 연결 요소 찾기, 위상 정렬, 미로 풀이 등 다양한 알고리즘의 구성 요소로 활용되며, 전위, 후위, 역 전위, 역 후위 순서로 정점을 정렬할 수 있다. 제한된 깊이까지 탐색하는 깊이 제한 탐색과, 깊이 제한을 반복적으로 늘려가며 탐색하는 반복적 심화 깊이 우선 탐색(IDDFS)과 같은 변형 알고리즘도 존재한다.
더 읽어볼만한 페이지
- 검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다. - 검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다. - 그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다. - 그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
| 깊이 우선 탐색 | |
|---|---|
| 알고리즘 정보 | |
| 종류 | 검색 알고리즘 |
| 자료 구조 | 그래프 |
| 시간 복잡도 (명시적 그래프, 반복 없이 순회) | |
| 시간 복잡도 (암시적 그래프, 분기 계수 b, 깊이 d) | |
| 공간 복잡도 (전체 그래프, 반복 없이 순회) | |
| 공간 복잡도 (암시적 그래프, 중복 노드 제거 없음) | O(가장 긴 탐색 경로 길이) = |
| 완전성 | 예 (무한 경로가 가능하지 않은 경우) |
| 최적성 | 아니오 (일반적으로 최단 경로를 찾지 않음) |
2. 깊이 제한과 백트래킹
탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(''depth bound'')을 사용한다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 되돌아와서, 부모 노드에 이전과는 다른 동작자를 적용하여 새로운 자식 노드를 생성한다. 여기서 부모 노드로 되돌아오는 과정을 '''백트래킹'''(''backtracking'')이라 한다.
그래프를 탐색할 때는 몇 가지 수정이 필요하다.
3. 알고리즘
먼저 그래프에서 깊이(''depth'')를 정해야 한다. 보통 그래프에서는 루트 노드의 깊이를 0으로 하고, 다른 노드의 깊이는 그 부모 노드 중 가장 얕은 깊이에 1을 더한 값으로 정의한다. 따라서 그래프에서 깊이 우선 탐색은 아직 방문하지 않은 노드(OPEN) 중 가장 깊은 것을 골라 탐색한다. 새로 찾은 노드(''후계 노드'')가 이미 방문했던 노드(OPEN이나 CLOSED)에 있다면, 깊이를 다시 계산해야 한다.
일반적인 그래프를 탐색하더라도 탐색 과정에서 나오는 노드와 포인터들은 탐색 트리를 형성한다. 즉, 포인터는 하나의 부모 노드만 가리킨다.[5]
3. 1. 재귀적 구현
깊이 우선 탐색(DFS)의 재귀적 구현은 다음과 같다.[5]
'''절차''' DFS(''G'', ''v'')
재귀적 구현은 예제 그래프의 노드를 A, B, D, F, E, C, G 순서로 방문한다.[6]
3. 2. 비재귀적 구현
깊이 우선 탐색(DFS)의 비재귀적 구현은 너비 우선 탐색(BFS)과 유사하지만, 다음과 같은 차이점이 있다.[6]
1. 스택을 사용한다. (큐 대신)
2. 정점을 스택에서 꺼낼 때 발견 여부를 확인한다. (추가하기 전에 검사하지 않음)[6]
예제 그래프에서 재귀적 구현은 노드를 A, B, D, F, E, C, G 순으로 방문하지만, 비재귀적 구현은 A, E, F, B, D, C, G 순으로 방문한다. 즉, 각 정점의 이웃을 서로 반대 순서로 방문한다.[6]
일반 그래프에서 반복적 깊이 우선 탐색 구현의 스택을 큐로 대체하면 다소 비표준적인 너비 우선 탐색 알고리즘이 생성된다.[7]
노드 이웃 목록의 반복자 스택을 사용하는 또 다른 비재귀적 구현 방식도 가능하다. 이 방식은 재귀적 DFS와 동일한 순회를 생성한다.[8]
4. 시간 및 공간 복잡도
이론 컴퓨터 과학에서 깊이 우선 탐색(DFS)은 전체 그래프 탐색에 사용되며, 시간 복잡도는 이다.[4] 여기서 는 정점의 수이고, 는 간선의 수이다. 이는 그래프 크기에 선형적이다. 깊이 우선 탐색은 현재 검색 경로에 있는 정점의 스택과 이미 방문한 정점 집합을 저장하기 위해 최악의 경우 공간을 사용한다. 따라서 시간 및 공간 복잡도는 너비 우선 탐색과 동일하며, 어떤 알고리즘을 사용할지는 복잡성보다는 두 알고리즘이 생성하는 정점 순서의 다른 특성에 따라 결정된다.
인공지능 또는 웹 크롤링과 같이 특정 도메인에 관련된 경우, 탐색할 그래프는 너무 크거나 무한할 수 있다. 이때는 깊이 제한 탐색으로 제한된 깊이까지만 탐색한다. 제한된 깊이까지 검색을 수행하면 시간은 확장된 정점 및 간선의 수에 대해 여전히 선형적이지만, 공간 복잡도는 깊이 제한에 비례하여 너비 우선 탐색보다 훨씬 작다. 반복적 심화 깊이 우선 탐색은 일련의 증가하는 제한으로 깊이 우선 탐색을 반복적으로 적용하여 적절한 깊이 제한을 찾는다.
깊이 우선 탐색은 그래프 노드의 표본을 수집하는 데에도 사용될 수 있지만, 불완전한 깊이 우선 탐색은 차수가 높은 노드에 대해 편향될 수 있다.
5. 장점과 단점
- 장점
- * 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
- * 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
- 단점
- * 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
- * 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
6. 응용
- 연결 요소 찾기
- 위상 정렬
- 2-(간선 또는 정점)-연결 요소 찾기
- 3-(간선 또는 정점)-연결 요소 찾기
- 그래프의 다리 찾기
- 군의 극한 집합을 그리기 위한 단어 생성
- 강하게 연결된 요소 찾기
- 계통 발생 트리에서 종이 다른 종보다 더 가까운지 여부 결정
- 평면성 검사[9][10]
- 미로와 같이 단 하나의 해만 있는 퍼즐 풀기 (깊이 우선 탐색(DFS)은 현재 경로의 노드만 방문 집합에 포함시켜 미로의 모든 해를 찾도록 조정할 수 있다.)
- 미로 생성은 무작위 깊이 우선 탐색(DFS)을 사용할 수 있습니다.
- 그래프의 이중 연결성 찾기
- 장자 상속은 영연방 왕국이 공유합니다.[11]
7. 정점 순서
깊이 우선 탐색을 사용하여 그래프 또는 트리의 정점을 선형으로 정렬할 수 있다. 정렬 방법에는 네 가지가 있다.
- '''전위 순회(Preorder)''': 깊이 우선 탐색 알고리즘에 의해 처음 방문한 순서대로 정점을 나열한다. 표현 트리의 전위 순회는 폴란드 표기법의 표현식이다.
- '''후위 순회(Postorder)''': 알고리즘에 의해 마지막으로 방문한 순서대로 정점을 나열한다. 표현 트리의 후위 순회는 역 폴란드 표기법의 표현식이다.
- '''역 전위 순회(Reverse Preorder)''': 전위 순회의 반대, 즉 처음 방문한 순서의 반대 순서로 정점을 나열한다. 역 전위 순회는 후위 순회와 동일하지 않다.
- '''역 후위 순회(Reverse Postorder)''': 후위 순회의 반대, 즉 마지막 방문 순서의 반대 순서로 정점을 나열한다. 역 후위 순회는 전위 순회와 동일하지 않다.
이진 트리의 경우 '''중위 순회(Inorder)''' 및 '''역 중위 순회(Reverse Inorder)'''가 추가로 있다.
예를 들어, 노드 A에서 시작하여 아래 방향 그래프를 탐색할 때, 가능한 전위 순회는 A B D C와 A C D B이고, 가능한 후위 순회는 D B C A와 D C B A이며, 가능한 역 후위 순회는 A C B D와 A B C D이다.
역 후위 순회는 모든 방향 비순환 그래프의 위상 정렬을 생성한다. 이 정렬은 제어 흐름 분석에서도 유용하게 활용된다.
8. 반복적 심화 깊이 우선 탐색
반복적 심화 깊이 우선 탐색은 적절한 깊이 제한을 미리 알 수 없을 때, 일련의 증가하는 제한으로 깊이 우선 탐색을 반복적으로 적용하는 방식이다. 분기 계수가 1보다 큰 경우, 반복적 심화는 올바른 깊이 제한을 아는 경우에 비해 실행 시간을 상수 배만큼 증가시킨다. 반복적 심화 깊이 우선 탐색(IDDFS)은 무한 루프를 피하고 모든 노드에 도달할 수 있게 한다.
참조
[1]
간행물
Charles Pierre Trémaux
Académie de Macon
2010-12-02
[2]
서적
Graph Algorithms
https://books.google[...]
Cambridge University Press
[3]
서적
Algorithms in C++: Graph Algorithms
Pearson Education
[4]
문서
[5]
문서
[6]
문서
Algorithm Design
[7]
웹사이트
Stack-based graph traversal ≠ depth first search
https://11011110.git[...]
2020-06-10
[8]
서적
Algorithms in Java.
http://worldcat.org/[...]
Addison-Wesley
2010
[9]
논문
Efficient planarity testing
https://ecommons.cor[...]
[10]
논문
Trémaux Trees and Planarity
[11]
논문
Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado
https://books.google[...]
American Mathematical Society
[12]
학술지
Depth-first search is inherently sequential
[13]
서적
Algorithms and Data Structures: The Basic Toolbox
http://people.mpi-in[...]
Springer
[14]
논문
A random ''NC'' algorithm for depth first search
[15]
논문
An ''NC'' algorithm for minimum cuts
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com