algorithm => 깊이 우선 검색

깊이 우선 검색 소개

Depth-first search 는 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기위한 알고리즘입니다. 하나는 루트에서 시작하여 역 추적하기 전에 각 분기를 따라 최대한 멀리 탐구합니다. 19 세기 프랑스의 수학자 찰스 피에르 트리 모 (Charles Pierre Trémaux)는 미로 해석을위한 전략으로 깊이 우선 탐색의 한 버전을 조사했습니다.

Depth-first search는 소스 정점에서 도달 할 수있는 모든 정점을 찾는 체계적인 방법입니다. 너비 우선 탐색과 마찬가지로 DFS는 주어진 그래프의 연결된 구성 요소를 가로 지르고 스패닝 트리를 정의합니다. 깊이 우선 탐색의 기본 개념은 모든 에지를 조직적으로 탐구하는 것입니다. 필요에 따라 다른 꼭지점부터 시작합니다. 정점을 발견하자마자 DFS는 BFS와는 달리 탐색을 시작합니다. BFS는 정점을 큐에 놓아 나중에 탐색합니다.

예를 살펴 보겠습니다. 이 그래프를 살펴 보겠습니다.

다음 규칙에 따라 그래프를 탐색합니다.

근원지부터 시작하겠습니다.
노드를 두 번 방문하지 않습니다.
아직 방문하지 않은 노드는 흰색으로 표시됩니다.
방문한 노드는 모든 자식 노드를 방문하지 않았지만 회색으로 표시됩니다.
완전히 가로 지르는 노드는 검은 색으로 표시됩니다.

단계별로 살펴 보겠습니다.

우리는 하나의 중요한 키워드를 볼 수 있습니다. 그것은 뒷받침된다 . 너는 볼 수있어. 5-1 은 후진이라고합니다. 왜냐하면 우리는 노드 -1로 아직 완료되지 않았기 때문에 다른 노드에서 노드 -1로 이동 한다는 것은 그래프에주기가 있음을 의미합니다. DFS에서 한 회색 노드에서 다른 회색 노드로 갈 수 있다면 그래프에주기가 있음을 확신 할 수 있습니다. 이것은 그래프에서주기를 감지하는 방법 중 하나입니다. 소스 노드와 방문하는 노드의 순서에 따라주기의 모든 에지를 뒤에서 찾을 수 있습니다. 예를 들면 : 우리가 1에서 처음으로 5 로 갔다면 우리는 2-1 을 뒤집어 쓴 것으로 알았을 것입니다.

회색 노드에서 흰색 노드로 이동하기 위해 사용하는 에지를 트리 에지 라고 합니다 . 나무 가장자리 만 지키고 다른 나무 들은 제거하면 우리는 DFS 나무를 갖게됩니다.

방향이없는 그래프에서 이미 방문한 노드를 방문 할 수 있다면 그 노드는 뒤집어 져 있어야합니다. 그러나 유향 그래프의 경우 색을 확인해야합니다. 하나의 회색 노드에서 다른 회색 노드로 이동할 수있는 경우에만이를 뒤집기라고합니다 .

DFS에서는 여러 가지 방법으로 사용할 수있는 각 노드의 타임 스탬프를 유지할 수도 있습니다 (예 : Topological Sort).

노드 v 가 흰색에서 회색으로 변경되면 시간은 d [v]로 기록됩니다.
노드 v 가 회색에서 검은 색으로 변경되면 시간은 f [v]로 기록됩니다.

여기서 d [] 는 발견 시간을 의미하고 f [] 는 종료 시간을 의미 합니다 . 우리의 페소 코드는 다음과 같습니다.

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

복잡성:

각 노드와 에지는 한 번 방문됩니다. 따라서 DFS의 복잡성은 O (V + E)입니다 . 여기서 V 는 노드 수를 나타내며 E 는 에지 수를 나타냅니다.

깊이 우선 검색 응용 프로그램 :

무향 그래프에서 모든 쌍 최단 경로 찾기.
그래프에서주기를 감지합니다.
길 찾기.
위상 학적 정렬.
그래프가 bipart인지 테스트하기.
강하게 연결된 구성 요소 찾기.
하나의 솔루션으로 퍼즐 풀기.

Modified text is an extract of the original Stack Overflow Documentation

아래 라이선스 CC BY-SA 3.0

와 제휴하지 않음 Stack Overflow

algorithm
깊이 우선 검색

수색…

깊이 우선 검색 소개