DFS는 비최적의 솔루션을 생성하지만 더 깊은 검색 도메인으로 빠르게 통과하는 데 유용할 수 있는 또 다른 알지 못하는 그래프 순회 알고리즘입니다. 깊이 첫 번째 검색은 우리가이 튜토리얼에서 다루는 이전에 덮여 첫 번째 검색과 매우 유사하다 : 자바에서 첫 번째 검색은 비 재귀 그래프에 깊이 첫 번째 검색 / 순회를 수행하는 자바 프로그램의 소스 코드입니다. 이 프로그램은 성공적으로 컴파일 및 윈도우 7에서 IDE IntelliJ 아이디어를 사용하여 테스트됩니다. 프로그램 출력도 아래와 같습니다. 예를 들어 다음 그래프에서는 정점 2에서 통과를 시작합니다. 정점 0에 도달하면 인접한 모든 정점을 찾습니다. 도 2는 인접한 정점 0입니다. 방문한 정점을 표시하지 않으면 2가 다시 처리되고 종료되지 않는 프로세스가 됩니다. 다음 그래프의 깊이 첫 번째 순회는 2, 0, 1, 3입니다.
위의 코드는 지정된 소스 정점에서 연결할 수 있는 정점만 트래버스합니다. 지정된 정점(예: 연결이 끊긴 그래프)에서 모든 정점에 연결할 수 없습니다. 이러한 그래프의 완전한 DFS 통과를 수행하려면 모든 정점마다 DFSUtil()을 호출해야 합니다. 또한 DFSUtil()을 호출하기 전에 DFSUtil()의 다른 호출에 의해 이미 인쇄되었는지 확인해야 합니다. 다음 구현은 노드에 연결할 수 없는 경우에도 전체 그래프 통과를 수행합니다. 위의 코드의 차이점은 아래 코드에서 강조 표시됩니다. 이것은 비 재귀 그래프에 깊이 첫 번째 검색 / 순회를 수행하는 자바 프로그램입니다. 위의 구현은 지정된 정점에서 연결할 수 있는 정점만 인쇄합니다. 예를 들어 가장자리를 0-3 및 0-2로 제거하면 위의 프로그램은 0만 인쇄합니다. 그래프의 모든 정점을 인쇄하려면 모든 정점마다 DFS를 호출해야 합니다.
다음은 동일한 구현입니다. 예를 들어, 아래 그래프의 DFS는 “0 3 4 2 1”, 다른 가능한 DFS는 “0 2 1 3 4″입니다. 재귀 통과와 마찬가지로 반복 구현의 시간 복잡성은 O(V + E)입니다. 다음은 반복 DFS의 구현입니다. 구현은 BFS와 유사하며 유일한 차이점은 큐가 스택으로 대체된다는 것입니다. 이 모든 자습서에서 코드를 지우는 수단으로 모든 그래프 순회 클래스가 확장되고 준수되는 추상 클래스에 추가하려고합니다. 이에 대한 소스 코드는 다음과 같습니다 : 시간 복잡성 : n이 배열의 요소 수인 O (n2). 우리는 노드 40으로 시작합니다. 그런 다음 직접 연결되는 노드 20, 노드 50, 노드 70을 각각 방문합니다. 그 후 노드 20으로 역추적하고 노드 60, 노드 30 및 노드 10을 각각 방문합니다.
우리는 이전 게시물에서 DFS의 재귀 구현에 대해 논의했습니다. 게시물에서 반복 DFS에 대해 설명합니다. 재귀 구현함수 호출 스택을 사용합니다. 반복 구현에서 명시적 스택은 방문한 정점을 보유하는 데 사용됩니다. 시간 복잡성: V가 그래프의 정점 수이고 E가 그래프의 가장자리 수인 O(V+E)입니다. 깊이 우선 통과 – 깊이 우선 검색(DFS)은 트리 또는 그래프 데이터 구조를 트래버스 또는 검색하기 위한 알고리즘입니다. 하나는 루트에서 시작하여(그래프의 경우 임의의 노드를 루트로 선택) 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색합니다. 출처 – 위키1.
함수 depthFirstSearch() 에서 부울 배열이 만들어지고 소스의 방문된 값이 true로 설정됩니다. 2. 그런 다음 스택이 만들어지고 소스 정점이 추가됩니다. 3. 루프 while(!stack.isEmpty()))은 스택이 비어 있는 때까지 다각적입니다. 4. 중첩 루프for이(i=0; i<matrix.length; i++)는 스택에서 현재 팝된 정점의 모든 이웃을 통과합니다. 5. 조건 (행렬[x-1][i] == 1 & 방문 [i] == false) 현재 폴링 된 정점의 모든 이웃을 찾고 스택에 현재 정점을 밀어 후 첫 번째 비 방문 된 이웃을 통과 하는 경우.