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

깊이 우선 탐색(DFS, Depth-First Search)

개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

사용하는 경우 : 모든 노드를 방문 하고자 하는 경우 dfs가 bfs보다 간단하다. 단순 검색 속도는 bfs보다 느리다.

특징

순환 알고리즘 형태이다. 탐색 시 노드를 방문 했었는지 여부를 검사해야한다. 아니면 무한루프에 빠진다.

구현 방법

1. 재귀함수 호출
2. 스택(Stack) 사용

시간 복잡도

DFS(정점의 수:N, 간선의 수:E)의 모든 간선을 조회한다.

• 인접리스트로 표현된 그래프 : O(N+E)
• 인접행렬로 표현된 그래프 : O(N^2)

DFS 구현 코드 예시

//----------------------재귀함수 DFS
public static void dfs(int i) {
    visited[i] = true; //먼저 방문했다고 표시
    System.out.print(i + " ");

    for(int j = 1; j <= n; j++) {//한쪽을 깊게
      if(arr[i][j] == 1 && !visited[j]) { //이어져있고 방문 안한 곳
        dfs(j);
      }
    }
  }
}


//------------ 스택을 이용한 DFS

public static void bfs(int start) {

    Stack<T> stack = new Stack<T>(); // 객체 선언

    stack.push(start); // 시작점

    visited[start] = true; // 방문 표시
    System.out.print(start + " ");

    while(!stack.isEmpty()) {

      int temp = stack.pop();
      System.out.print(temp + " ");

      for(int j = 1; j <= n; j++) {

        if(arr[temp][j] == 1 && !visited[j]) { // 이어져있고 방문 안한 곳

          stack.push(j); // 스택에 넣고
          visited[j] = true; // 방문 표시
        }
      }
    }
}

요약

• 스택과 재귀함수로 구현한다.
• DFS는 한쪽을 먼저 다 검색한다.