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

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다. 너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다. 검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 ..
알고리즘/이론 2021. 7. 3. 18:28
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형
250x250