DFS?

목차

1.DFS?

2.DFS의 특징

3.원리 및 구현

 

1.DFS?

dfs는 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다. 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만,

항상 완전탐색으로 사용되지는 않는다. DFS는 주로 반복문을 활용하거나, 재귀문을 통하여 구현된다.

2.DFS의 특징

깊이 우선 탐색

• DFS는 가능한 한 깊이로 먼저 탐색을 진행하며, 더 이상 갈 수 없을 때 이전 단계로 돌아와 다른 경로를 탐색합니다.
• 특정 노드에서 모든 경로를 끝까지 탐색해야 하는 경우에 적합합니다.

경로 탐색

• DFS는 시작 노드에서 특정 목표 노드까지의 모든 가능한 경로를 탐색하거나, 특정 조건에 맞는 경로를 찾는 데 유용합니다.
• 예: 미로 찾기, 퍼즐 문제 해결 등.

재귀적 성질

• DFS는 재귀 호출을 사용하여 구현할 수 있으며, 함수 호출 스택이 자동으로 탐색 경로를 관리합니다.
• 스택 자료구조를 사용한 반복문으로도 구현 가능합니다.

순서가 중요하지 않음

• 탐색 순서는 그래프에서 노드의 인접 리스트를 어떻게 정의하느냐에 따라 달라집니다.
• 동일한 그래프에서도 탐색 순서는 구현 방식에 따라 다를 수 있습니다.

공간 효율성

• DFS는 방문한 노드를 기록하고, 탐색 중인 경로를 저장하기 위해 스택(혹은 재귀 호출 스택)을 사용합니다.
• 공간 복잡도는 그래프의 깊이에 따라 달라지며, 일반적으로 O(V)O(V)O(V)입니다. (여기서 VVV는 그래프의 정점 수)

사이클 및 방문 처리

• DFS는 그래프 탐색 중 방문한 노드를 기록하여 사이클을 감지하거나, 중복 방문을 방지합니다.
• 방향 그래프 또는 무방향 그래프에서 사이클 탐지에 유용합니다.

최단 경로 탐색이 아님

• DFS는 가중치가 없는 그래프에서도 최단 경로를 보장하지 않습니다.
• 특정 목표까지 빠르게 도달하기보다는 모든 경로를 탐색하는 데 더 적합합니다.

그래프 연결성 확인

• DFS를 사용하여 그래프의 모든 노드를 방문할 수 있으며, 연결된 컴포넌트(Connected Components)를 확인하는 데 사용할 수 있습니다.

3.원리 및 구현

DFS의 원리는 다음과 같습니다.

1. 시작 노드를 방문하고, 방문 처리합니다.
2. 해당 노드의 인접 노드 중 방문하지 않은 노드를 재귀적으로 또는 스택을 사용하여 탐색합니다.
3. 더 이상 방문할 노드가 없을 때 탐색을 종료합니다.

DFS는 보통 스택(Stack) 자료구조를 사용합니다. 재귀를 사용하는 경우 함수 호출 스택이 이를 대신합니다.

 

스택으로 구현을 한 경우

import java.util.*;

class DFS {
    static ArrayList<Integer>[] adj; // adjacency list representation of the graph
    static boolean[] visited; // array to keep track of visited vertices

    public static void dfs(int v) {
        Stack<Integer> stack = new Stack<>();
        stack.push(v);
        visited[v] = true;

        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.print(vertex + " ");

            for (int neighbor : adj[vertex]) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; // number of vertices
        adj = new ArrayList[n];
        visited = new boolean[n];

        // initialize adjacency list and visited array
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            visited[i] = false;
        }

        // add edges to the graph
        adj[0].add(1);
        adj[0].add(2);
        adj[1].add(2);
        adj[2].add(0);
        adj[2].add(3);
        adj[3].add(3);

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }
}

 

재귀를 사용해서 구현을 한 경우

import java.util.*;

class DFS {
    static ArrayList<Integer>[] adj; // adjacency list representation of the graph
    static boolean[] visited; // array to keep track of visited vertices

    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; // number of vertices
        adj = new ArrayList[n];
        visited = new boolean[n];

        // initialize adjacency list and visited array
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            visited[i] = false;
        }

        // add edges to the graph
        adj[0].add(1);
        adj[0].add(2);
        adj[1].add(2);
        adj[2].add(0);
        adj[2].add(3);
        adj[3].add(3);

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }
}

 

 

참고

https://olrlobt.tistory.com/35#dfs-%EC%98%88%EC%8B%9C-%EB%AC%B8%EC%A0%9C

[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란?