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

참고: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다.
조금 쉽게 얘기하자면 루트노드(또는 임의의 노드)에서 시작해서 다음 분기 (branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방법이다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용된다. 
너비 우선 탐색(BFS)에서는 큐(Queue)가 사용되었다면, 깊이 우선 탐색에서는 스택(Stack)이 사용된다. 
(사실 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에, 스택을 사용하지 않아도 구현이 가능하다) 

깊이 우선 탐색은 탐색기법 자체로는 큰 의미가 없고 이 탐색법을 활용해서 문제를 해결하고 하는 것에 초점을 둔다. (작동원리에 대해서만 빠삭하게 이해하면된다)

 

●  DFS의 특징 

• 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
• 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다
• 단순 검색속도 자체는 너비 우선탐색에 비해서 느리다 
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고있다 (재귀)

전위 순회(Pre-OrderTraversals)를 포함한 다른형태의 트리 순회는 모두 DFS의 한 종류이다. 

전위 순회 개념 (출처: 위키피아)

이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 '어떤 노드를 방문했었는지 여부'를 반드시 검사해야한다. (이를 검사하지 않으면 무한루프에 빠질 위험성이 생긴다)

●  깊이 우선 탐색(DFS)의 구현 

1. 순환 호출 이용
2. 명시적인 스택 이용
   · 명시적인 스택을 사용하여 방문한 정점들은 스택에 저장하였다가 다시 꺼내서 작업한다 

● 깊이 우선 탐색(DFS)의 시간 복잡도 

• DFS는 그래프(정점의 수: N, 간선의수: E)의 모든 간선을 조회한다
  * 인접 리스트로 표현된 그래프: O(N + E)
  * 인접 행렬로 표현된 그래프: O(N^2)
• 즉 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Spare Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다

● 순환 호출을 이용한 DFS구현

package stack;

import java.util.Iterator;
import java.util.LinkedList;

// 인접 리스트를 이용한 방향성 있는 그래프 클래스
public class Graph {
    private int v; // 노드의 개수
    private LinkedList<Integer> adj[]; // 인접 리스

    Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        // 인접 리스트 초기화
        for (int i = 0; i < v; i++)
            adj[i] = new LinkedList<>();
    }

    // 노드를 연결 v -> w
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // DFS에 의해 사용되는 함수
    void DFSUtil(int v, boolean[] visited) {
        // 현재 노드를 방문한 것으로 표시하고 값을 출력
        visited[v] = true;
        System.out.print(v + " ");

        // 방문한 노드와 인접한 모든 노드를 가져온다
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출(재귀)
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // 주어진 노드를 시작 노드로 DFS 탐색
    void DFS(int v) {
        // 노드의 방문 여 판단 (초깃: false)
        boolean visited[] = new boolean[this.v];

        // v를 시작 노드로 DFSUtil 순환 호출
        DFSUtil(v, visited);
    }

    // DFS 탐색
    void DFS() {
        // 노드의 방문 여부 판단 (초깃값: false)
        boolean visited[] = new boolean[this.v];

        // 비연결형 그래프의 경우, 모든 정점을 하나씩 방문
        for (int i = 0; i < this.v; i++) {
            if (visited[i] == false)
                DFSUtil(i, visited);


        }
    }
}

 

 public static void main(String[] args) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        g.DFS(2); // 주어진 노드를 시작 노드로 DFS 탐색
        g.DFS(); // 비연결형 그래프의 경우
        
    }