DFS 깊이우선탐색 (java)

DFS는 Depth First Search의 줄임말로, 

깊이 우선 탐색 알고리즘을 의미한다. 

 

넓게 탐색 전 깊게 탐색한다.

모든 노드를 다 방문하고자 할 때 해당 알고리즘을 사용한다. 

 

 

깊이 우선 탐색을 응용하여 풀 수 있는 문제? (관련문제)

단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

 

[순환 알고리즘]의 형태

그래프 탐색 시에는 어떤 노드를 방문했는지 반드시 검사가 필요하다. 

검사 하지 않을 시 무한루프의 위험에 빠지게 된다. 

 

DFS 알고리즘의 구현방법 2가지

1. 순환 호출 이용

2. 명시적인 스택 사용

 

순환 호출을 이용한 구현 방법을 살펴보도록 하자. 

순환호출 [수도코드]

void search(Node root) {
  if (root == null) return;
  // 1. root 노드 방문
  visit(root);
  root.visited = true; // 1-1. 방문한 노드를 표시
  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 4. 방문하지 않은 정점을 찾는다.
      search(n); // 3. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

 

 

순환호출 [JAVA 코드내용 ]

import java.io.*;
import java.util.*;

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

  /** 생성자 */
  Graph(int v) {
      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[V];

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

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

      // 비연결형 그래프의 경우, 모든 정점을 하나씩 방문
      for (int i=0; i<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(); /* 비연결형 그래프의 경우 */
}

}

 

깊이 우선 탐색의 시간복잡도?

DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회

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

*따라서 적은 수의 간선을 갖는 그래프라면 행렬보다는 인접리스트를 사용하는 것이 좋다!

 

 

---

참고한 블로그

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

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