데이터 구조의 DFS(깊이 우선 탐색): 정의, 주문 및 응용

데이터 구조에서 DFS의 의미

깊이 우선 탐색이라고도 하는 데이터 구조의 DFS는 그래프 또는 트리 데이터 구조의 모든 정점을 검색하는 데 주로 사용되는 재귀 알고리즘입니다. 순회는 그래프의 모든 노드를 방문하는 것입니다. 알고리즘은 루트 노드(그래프의 루트 노드로 임의의 노드일 수 있음)에서 시작하여 역추적하기 전에 각 분기를 따라 최대한 멀리 이동합니다.

아이디어는 루트 또는 임의의 노드에서 시작하여 노드를 표시한 상태로 유지하는 것입니다. 그런 다음 표시되지 않은 인접 노드로 이동하고 표시되지 않은 인접 노드가 없을 때까지 이 루프를 계속해야 합니다. 그런 다음 역추적하고 표시되지 않은 다른 노드를 검사하고 통과합니다. 마지막 단계는 경로 내의 노드를 인쇄하는 것입니다.

연산

노드의 인덱스와 방문한 배열을 취하는 재귀 함수를 공식화하십시오.

1. 현재 노드를 방문한 것으로 표시된 상태로 유지한 다음 인쇄합니다.
2. 인접한 모든 메모와 표시되지 않은 메모를 순회하고 인접한 노드의 인덱스로 재귀 함수를 호출합니다.

인기 있는 소프트웨어 엔지니어링 과정 살펴보기

속성

데이터 구조에서 DFS의 시간과 공간 분석은 응용 분야에 따라 다릅니다. 이론적으로 DFS는 주로 전체 그래프를 교차하는 데 사용되며 |V| 정점의 수를 나타내고 |E| 모서리의 수를 나타냅니다. 이 그래프는 선형입니다.

이러한 응용 프로그램에서 공간 O(|V|)는 검색 경로에 저장된 정점 스택과 이미 방문한 정점 집합을 유지하기 위한 최후의 수단으로도 사용됩니다. 따라서 시간 및 공간 경계 설정은 너비 우선 탐색과 유사합니다. 여기서 사용된 두 알고리즘은 복잡성에 덜 의존하고 두 알고리즘에 의해 생성된 정점 차수의 다양한 특성에 더 많이 의존합니다.

웹 크롤링이나 AI에서 솔루션 찾기와 같이 특정 도메인과 관련된 데이터 구조에서 DFS를 적용하는 경우 순회가 필요한 그래프는 전체를 방문하기에는 너무 방대할 수 있습니다. 이러한 경우 검색은 제한된 수심까지만 실행됩니다. 디스크 공간이나 메모리와 같은 한정된 리소스 때문입니다. 데이터 구조는 일반적으로 이전에 방문한 모든 정점 집합을 추적하는 데 사용되지 않습니다. 제한된 깊이에 대해 수행된 검색은 확장된 가장자리 및 정점의 단위와 관련하여 여전히 시간을 선형으로 만듭니다.

그러나 일부 정점은 여러 번 검색되고 다른 정점은 검색되지 않을 수 있으므로 이 숫자가 전체 그래프와 동일한 크기를 갖지 않는다는 점을 기억하십시오.

이러한 경우 DFS는 더 유망한 분기를 선택하기 위해 휴리스틱 방법도 사용합니다. 마지막으로 적절한 깊이 한계를 결정할 수 없을 때 선험적으로 반복적인 심화 DFS가 일련의 성장 한계를 통해 반복적으로 적용됩니다.

세계 최고의 대학에서 온라인으로 소프트웨어 개발 과정 을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.

깊이 우선 탐색 알고리즘

표준 DFS 구현에서 그래프의 각 꼭짓점은 두 가지 범주 중 하나로 나뉩니다.

1. 방문하지 않음
2. 방문

알고리즘은 각 정점을 정확히 찾아 방문으로 표시하는 동시에 주기를 피하는 데 사용됩니다.

DFS 알고리즘이 작동하는 방식은 다음과 같습니다.

1. 그래프의 특정 정점을 스택에 넣습니다.
2. 스택 맨 위에 있는 항목은 방문 목록에 추가되어야 합니다.
3. 해당 꼭짓점의 인접 노드 목록을 만들고 스택 맨 위에 방문한 목록에 없는 노드를 추가합니다.
4. 스택이 비워질 때까지 이전 단계를 계속 반복합니다.

DFS 주문

정점 순서: DFS에서 그래프 또는 트리의 정점을 선형으로 정렬하는 네 가지 방법이 있습니다.

1. DFS 알고리즘이 가장 먼저 방문한 정점의 목록을 사전 정렬(pre-ordering)이라고 합니다. 검색 진행 상황을 설명하는 간결한 방법입니다.
2. 알고리즘이 마지막으로 방문한 정점의 목록을 사후 정렬(post-ordering)이라고 합니다.
3. 첫 번째 방문과 반대 순서의 정점 목록은 역 선주문입니다. 따라서 포스트 오더로 오인해서는 안됩니다.
4. 마지막 방문과 반대 순서의 꼭짓점 목록은 역 후위 순서입니다. 선주문으로 착각하시면 안됩니다.

또한 이진 트리에 대한 순서 지정 및 역 순서 지정이 있습니다.

그래프에 대한 깊이 우선 탐색 또는 DFS

그래프의 DFS는 트리의 DFS와 거의 동일합니다. 유일한 차이점은 그래프에는 나무와 달리 주기가 있을 수 있다는 것입니다. 노드를 여러 번 방문할 수 있으며 노드 처리를 피하기 위해 부울 방문 배열이 사용됩니다.

깊이 우선 검색의 출력

깊이 우선 탐색은 탐색에서 이미 도달한 정점의 스패닝 트리 측면에서 더 쉽게 묘사됩니다. 이 스패닝 트리를 기반으로 원래 그래프 가장자리는 트리의 노드가 하위 항목 중 하나를 가리키는 앞쪽 가장자리, 노드가 조상 중 하나를 가리키는 뒤쪽 가장자리 및 교차 가장자리의 세 가지 클래스로 나뉩니다. , 이전 기능을 수행하지 않습니다.

깊이 우선 탐색(DFS)의 응용

깊이 우선 검색은 다음 알고리즘에서 빌딩 블록으로 사용됩니다.

• 연결된 구성 요소를 검색합니다.
• 2-(정점 또는 모서리) 연결된 구성 요소 찾기.
• 그래프의 다리 찾기.
• 3-(정점 또는 모서리) 연결된 구성 요소 찾기.
• 위상 정렬.
• 강력하게 연결된 구성 요소를 찾습니다.
• 종이 계통 발생 수의 한 종 또는 다른 종과 유사한지 알아내기.
• 평면성 테스트.
• 그룹의 한계 집합을 결정하기 위해 단어를 생성합니다.
• 미로와 같이 단 하나의 솔루션만 있는 퍼즐을 푸십시오.
• 미로 세대 .
• 그래프에서 이중 연결성을 검색합니다.

Python의 DFS 의사 코드 및 구현

init() 함수는 아래 의사 코드의 모든 노드에서 실행되어 모든 정점이 방문되었는지 확인합니다. 그래프에 다양한 연결이 끊긴 영역이 있을 수 있으므로 이는 특히 중요합니다.

의사 코드는 다음과 같습니다.

DFS(지,유)

u.visited = 사실

각 v ∈ G.Adj[u]에 대해

v.visited == false인 경우

DFS(G,v)

초기화() {

각 u ∈ G에 대해

u.visited = 거짓

각 u ∈ G에 대해

DFS(지,유)

}

다음은 Python의 DFS 구현입니다.

그래프 = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'삼' : [],

'4' : ['6'],

'7' : []

}

방문 = set()

def dfs(방문, 그래프, 노드):

노드가 방문하지 않은 경우:

인쇄(노드)

방문.add(노드)

그래프[노드]의 이웃:

dfs(방문, 그래프, 이웃)

print("DFS입니다:")

dfs(방문, 그래프, '5')

산출:

이것은 DFS: 5

인기 있는 소프트웨어 엔지니어링 과정 살펴보기

깊이 우선 탐색의 복잡성

John Reif는 깊이 우선 탐색의 계산 복잡성을 탐구했습니다. 정확히는 그래프에서 주어진 팩트가 G이고 O를 반복 DFS 알고리즘에 의해 결정되는 표준 차수라고 하자. G는 그래프를 나타내고 O는 중복 DFS 알고리즘의 순서 지정 출력을 나타냅니다. 이 출력을 사전식 DFS 정렬이라고 합니다.

결론

DFS 알고리즘의 주요 목표는 대상 그래프에서 주기를 피하는 모든 단일 정점을 방문하는 것입니다. 검색 작업 또는 주문 작업의 고급 구현에 참여하려면 깊이 우선 검색 및 데이터 구조에서 프리미엄 및 전체론적 과정을 추구하는 것을 반드시 고려해야 합니다.

upGrad 에는 컴퓨터 과학 석사 및 빅 데이터 전문화 와 같은 일부 최상위 DFS 과정이 있습니다.

다음 단계로 나아가기 위해 고군분투하고 전문적인 조언을 찾고 있다면 upGrad Mentorship 은 업계 최고의 직업 카운슬러 및 전문가와 일대일 세션을 제공하려고 합니다.