깊이 첫 번째 검색 또는 깊이 먼저 통과 재귀 알고리즘 검색에 대한 모든 꼭지점의 그래프 또는 나무 데이터는 구조입니다. 순회 란 그래프의 모든 노드를 방문하는 것을 의미합니다.

깊이 첫 번째 검색 알고리즘

표준 DFS 구현을 둔 각각의 정점 그래프 하나로 두 개의 카테고리:

1. 방문
2. 방문하지 않

목적의 알고리즘을 표시하는 것입니다 각각의 정점으로 방문하는 동안 피하는 주기입니다.,

DFS 알고리즘은 다음과 같이 작동합니다:

1. 시작하여 모든 하나의 그래프의 정점에 최고의 스택이다.
2. 스택의 맨 위 항목을 가져 와서 방문한 목록에 추가하십시오.
3. 해당 정점의 인접 노드 목록을 만듭니다. 방문한 목록에없는 것을 스택의 맨 위에 추가하십시오.
4. 스택이 비어있을 때까지 2 단계와 3 단계를 계속 반복하십시오.

Depth First Search Example

Depth First Search 알고리즘이 예제와 함께 어떻게 작동하는지 살펴 보겠습니다. 우리는 5 개의 꼭지점이있는 무 방향 그래프를 사용합니다.,

우리는 정점에서 시작 0,DFS 알고리즘에 의해 시작을 방문한 목록과 모든 인접한 정점에 스택입니다.

다음에,우리는 우리를 방문하는 요소에서 최고의 스택,즉 1 동으로 인접 노드입니다. 0 이 이미 방문되었으므로 대신 2 를 방문합니다.,

정점을 2 는 인접 방문하지 않은 꼭지점 4 에서는,그래서 우리는 우리 것을 추가하여 최고의 스택이고 그것을 방문하는 것입니다.

후에 우리를 방문 마지막 요소 3,그것은 없 인접 방문하지 않은 노드,우리가 완료되었는 깊이 우선 탐색의 그래프입니다.,

DFS Pseudocode(재귀 구현)

DFS 에 대한 pseudocode 는 아래와 같습니다. Init()함수에서 모든 노드에서 DFS 함수를 실행한다는 것을 알 수 있습니다. 이 때문에 그래프에 있는 두 개의 서로 다른 연결을 확인하는 것을 우리는 모든 꼭지점,우리는 실행할 수도 있습니다 DFS 알고리즘에서 모든 노드입니다.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

Python,Java 및 C/c++에서의 DFS 구현

예제와 함께 Depth First Search 알고리즘의 코드는 아래에 나와 있습니다. 다른 세부 사항보다는 알고리즘에 집중할 수 있도록 코드가 단순화되었습니다.

의 복잡성을 깊이 첫 번째 검색

시간 복잡도의 DFS 알고리즘의 형태로 표현된O(V + E),어디V은 수의 노드E은 수의 가장자리입니다.알고리즘의 공간 복잡도는

O(V)입니다.,

응용 프로그램의 DFS 알고리즘

1. 을 찾기 위한 길
2. 을 테스트하는 경우에는 그래프 이분
3. 를 찾기 위해 강하게 연결된 구성요소의 그래프
4. 을 검출하는 사이클에서는 그래프