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

깊이 우선 탐색

• 깊이 우선 탐색 개념

  • 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
  • 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 탐색
  • 해당 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.
  • 모든 노드를 방문하고자 하는 경우에 선택
  • 깊이 우선 탐색(DFS)가 너비 우선 탐색(BFS)보다 간단하다.
  • 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.

• 깊이 우선 탐색(DFS)의 특징

  • 순환 알고리즘의 형태를 갖고 있다.
  • 전위 순회(Pre-Order)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
  • 그래프 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사한다.

코드 설계

• 시작 노드(1)로부터 인접 노드(2, 3)를 모두 방문
• 인접 노드(2, 3)를 스택에 넣고 방문처리
• 시작 노드(1)로부터 인접한 노드 중에 방문하지 않은 노드가 더이상 없는 경우
• 이전의 위치로 돌아와 찾아가지 않은 다른 길로 탐색한다.

코드 구현

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

    public class DFSList {

     static class Graph {
         private int V;
         private LinkedList<Integer>[] adjacent;

         @SuppressWarnings("unchecked")
         public Graph(int V) {
             this.V = V;
             this.adjacent = new LinkedList[V];
             for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
         }

         public void addEdge(Graph graph, int src, int dest) {
             graph.adjacent[src].add(dest);
             graph.adjacent[dest].add(src);
         }

         public void printGraph(Graph graph) {
             for (int v = 1; v < graph.V; v++) {
                 System.out.println("Node [" + v + "]");
                 System.out.print("adjacent Node: ");
                 for (Integer node : graph.adjacent[v]) {
                     System.out.print("[" + node + "]\t");
                 }
                 System.out.println();
             }
         }

         /**
          * 비연결형 그래프의 경우, 모든 정점을 하나씩 방문하는 너비 우선 탐색
          * @param start
          */
         public void dfs() {
             boolean[] visit = new boolean[V];

             for(int i = 1 ; i < V ; i++) {
                 if(visit[i] == false) 
                     dfsUtil(i, visit);
                 System.out.println();
             }
         }

         /**
          * 주어진 노드를 시작한 너비 우선 탐색
          * @param start
          */
         public void dfs(int start) {
             boolean[] visit = new boolean[V];
             dfsUtil(start, visit);
             System.out.println();
         }

         /**
          * 인접한 노드 방문 하는 DFS 재귀함수
          * @param start
          * @param visit
          */
         private void dfsUtil(int start, boolean[] visit) {
             visit[start] = true; // 방문 체크
             System.out.print(start + "\t");

             Iterator<Integer> it = adjacent[start].listIterator(); // 인접한 노드 리스트
             while(it.hasNext()) {
                 int n = it.next();
                 if(!visit[n]) // 방문 확인 false인 경우, 노드 탐색
                     dfsUtil(n, visit);
             }
         }
     }

     public static void main(String[] args) {
         int initSize = 8;

         Graph graph = new Graph(initSize);

         graph.addEdge(graph, 1, 2);
         graph.addEdge(graph, 1, 3);
         graph.addEdge(graph, 2, 3);
         graph.addEdge(graph, 2, 4);
         graph.addEdge(graph, 2, 5);
         graph.addEdge(graph, 3, 6);
         graph.addEdge(graph, 3, 7);
         graph.addEdge(graph, 4, 5);
         graph.addEdge(graph, 6, 7);

         graph.printGraph(graph);

         graph.dfs(4); /* 주어진 노드를 기준으로 BFS 탐색 */
         graph.dfs();
     }
    }

• Graph의 각 노드에 연결된 노드 리스트 및 DFS 결과

    // 노드별 연결 리스트 확인
    Node [1]
    adjacent Node: [2]    [3]    
    Node [2]
    adjacent Node: [1]    [3]    [4]    [5]    
    Node [3]
    adjacent Node: [1]    [2]    [6]    [7]    
    Node [4]
    adjacent Node: [2]    [5]    
    Node [5]
    adjacent Node: [2]    [4]    
    Node [6]
    adjacent Node: [3]    [7]    
    Node [7]
    adjacent Node: [3]    [6]    
    // 주어진 노드를 기준으로 DFS 탐색
    4    2    1    3    6    7    5    
    // 모든 노드 탐색
    1    2    3    6    7    4    5    

분석

• 깊이 우선 탐색(DFS)의 시간 복잡도
  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)