Java의 DFS 알고리즘

DFS 알고리즘은 탐색 알고리즘으로 줄여서 깊이 우선 탐색이라고 정의되는 탐색 알고리즘으로, 그래프 구조처럼 보이는 트리 구조에서 탐색하므로 그래프 알고리즘이라고도 합니다. 아래 그래프와 함께 다른 가지로 루트 및 횡단합니다. 일반적으로 Java의 DFS 알고리즘은 초기 지점의 루트 노드에서 시작하여 마지막 분기의 마지막 노드에 도달할 때까지 각 분기로 깊이 들어가는 트리 또는 그래프 구조를 순회하는 탐색 알고리즘으로 정의됩니다. 깊이우선탐색으로 preorder, inorder, postorder 순회탐색의 3가지 DFS 방식을 제공합니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

알고리즘:

DFS는 최적이 아닌 솔루션을 생성하는 통일된 알고리즘이며 DFS 알고리즘은 다음과 같이 작동합니다.

1단계: 특정 그래프 또는 트리의 루트 노드부터 시작합니다.

2단계: 이제 루트 노드를 그래프의 첫 번째 노드로 간주하고 이 노드를 스택 또는 목록의 맨 위에 배치합니다.

3단계: 이제 첫 번째 노드인 루트 노드의 인접 노드를 찾고, 이러한 인접 노드를 다른 인접 노드 목록에 추가합니다.

4단계: 그런 다음 루트 노드 뒤에 스택이나 목록에 있는 각 노드의 인접 노드를 계속 추가합니다.

5단계: 그래프에서 마지막 분기의 끝 노드에 도달하거나 인접 노드 목록이 비어 있을 때까지 3~4단계를 계속합니다.

따라서 Java의 DFS 알고리즘은 초기 노드부터 끝 노드까지 깊이 탐색하는 순회 탐색 알고리즘 중 하나입니다. 그러나 왼쪽 분기를 통해서든 오른쪽 분기를 통해서든 그래프를 탐색할 때 혼란스러울 때가 있습니다. 이를 해결하기 위해 지정된 순서에 따라 트리를 순회하는 3가지 유형의 DFS preorder, inorder 및 postorder가 있습니다.

DFS 알고리즘은 예제와 어떻게 작동하나요?

Java에서 DFS 알고리즘은 위에서 설명한 알고리즘에 따라 작동합니다. 무방향 그래프에 대한 DFS 알고리즘은 먼저 이 루트 노드를 방문된 노드를 보유하는 방문 스택으로 간주될 수 있는 하나의 스택에 배치한 다음 루트 노드의 모든 인접한 노드를 이 스택에 배치하여 루트 노드에서 시작합니다. 루트 노드가 존재하는 스택을 방문했습니다. 그런 다음 그래프를 순회한 다음 각 루트의 인접 노드의 인접 노드를 찾고 그래프의 마지막 노드까지 계속하고 모든 노드를 다른 스택에 배치하여 이러한 노드를 순회하므로 검색이 완료된 후 방문한 스택이 표시됩니다. 그래프를 통과한 노드.

예시 #1

이제 연결이 끊긴 그래프에서 Java 프로그래밍 언어로 구현된 간단한 DFS 알고리즘 예제를 살펴보겠습니다.

코드:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

출력:

위의 예에서는 먼저 이 클래스 정점이 그래프의 정점을 저장하는 그래프의 루트 및 대상 정점을 선언할 클래스 정점을 정의합니다. 그런 다음 graphstruc 클래스를 정의하여 루트 노드의 인접 정점을 선언하고 이러한 인접 노드를 목록에 추가합니다. 인접한 정점을 저장하고 나중에 이러한 정점의 인접한 정점을 목록에 추가합니다. 그런 다음 DFS를 수행하기 위해 주어진 그래프에서 현재 노드를 식별하는 DFS 클래스를 선언하고 계속해서 각 노드의 인접 노드를 식별하고 인접 목록 노드를 추가합니다. 그런 다음 마지막으로 메인 클래스에서는 총 노드 수와 함께 그래프 정점 목록을 배열로 정의하고 DFS 함수를 호출한 후 위 스크린샷과 같이 DFS 검색 목록에 목록을 표시합니다. , 이것이 출력입니다.

예시 #2

이제 Java에서 선주문, 중순, 후순 순회와 같은 다양한 유형의 순회 순서를 사용하여 DFS 구현을 살펴보겠습니다. 아래에서는 Java로 선주문 구현을 살펴보겠습니다.

코드:

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

출력:

위의 예는 이전 예와도 유사합니다. 여기서 유일한 차이점은 DFS 알고리즘에서 트래버스 순서를 정의한다는 것입니다. 여기서는 선주문 순회 순서만 정의합니다. 정의되면 깊이 우선 그래프를 루트 노드, 왼쪽 노드, 오른쪽 노드 순서로 순회합니다. 따라서 여기서는 노드 2를 루트 노드로, 노드 3을 왼쪽 노드로, 노드 6을 오른쪽 노드로 선언했습니다. 출력은 위 스크린샷과 같습니다.

결론

이 기사에서는 Java의 DFS 알고리즘이 마지막 노드를 방문할 때까지 그래프를 깊이 찾거나 검색하는 순회 알고리즘이라고 결론지었습니다. DFS 알고리즘의 시간 복잡도는 일반적으로 O(E+V)로 표시됩니다. 여기서 E는 그래프의 모서리이고 V는 그래프의 정점입니다. 그래프를 통한 중순, 선순, 후순 DFS 순회로 분류되는 순회 순서를 기반으로 DFS 알고리즘을 다양하게 적용할 수 있습니다.

위 내용은 Java의 DFS 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!