깊이 우선 탐색(DFS) 란?

그래프의 탐색

그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색은 아주 중요하다 

 

• 도시를 연결하는 그래프가 있을 때, 특정 도시에서 다른 도시로 갈 수 있는지 없는지는 탐색하여 체크

 

그래프의 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다.

이 글에서는 깊이 우선 탐색에 대하여 알아보겠다.

 

 

 

깊이 우선탐색(DFS : depth first search) 

• 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이라는 점을 명심하자)

• 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사

 

 

위와 같은 그림의 그래프 처럼 탐색을 하는 것이 DFS 탐색이라고 할 수 있다.  그러면 진행되는 과정을 자세히 한번 공부해보려 한다.

 

 

DFS 탐색은 어디에서 사용될까? 

미로 탐색에 사용된다. 

• 미로 탐색시 한 방향으로 갈 수 있을 때까지 계속 탐색.
  
  
• 모든 노드를 방문하고자 하는 경우에 사용

 

 

 

그래프에서 깊이 우선 탐색은 어떻게 진행될까?

• 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 시작 정점 0을 방문하였다고 표시

• 이어서 v에 인접한 정점들 중에서 아직 방문하지 않은 정점 1을 선택한다.

• 그리고 만약 그러한 정점이 없다면 탐색은 종료한다. 

• 만약 아직 방문하지 않은 정점이 남아 있다면 그 정점을 시작으로 하여 탐색을 다시 시작한다.

• 깊이 우선 탐색도 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 가지고 있다.

 

 

깊이 우선 탐색의 구현(인접 행렬)

깊이 우선 탐색을 구현하는 데는 2가지의 방법이 있다. 

• 첫 번째 : 순환 호출을 이용

• 두 번째 : 명시적인 스택을 이용 

 

이번에는 자바를 이용해서 순환 호출을 이용하는 방법으로 구현해보려고 한다. 

 

import java.util.LinkedList;
 
public class Graph {
    public int V;   //노드의 개수
    public LinkedList<Integer>[] adj;  //인접 리스트
    boolean[] visited;
 
    //생성자
    public Graph(int v){
        V = v;
        adj = new LinkedList[v];
        visited = new boolean[V];
 
        for(int i=0; i<v; i++){
            adj[i] = new LinkedList();
        }
    }
 
    void addEdge(int v, int w){
        adj[v].add(w);
    }
 
    void DFS(int v){   //순환 호출을 이용해서 구현
        visited[v] = true;
        System.out.print(v + " ");
 
        for(int k : adj[v]){
            if(!visited[k]){
                DFS(k);     //순환 호출
            }
        }
 
    }
}
 

 

  
package Data_Structure.DFS;
 
public class Test {
    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를 구현하였다. 그리고 DFS 공부를 했는데 어느정도 어떤 탐색인지는 알겠지만 아직 응용은 안될 것 같다. 열심히 공부해야지 

 

 

 

깊이 우선 탐색의 분석

깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 리스트로 표현되어 있다면 시간 복잡도가 O(n+e)이고, 인접 행렬로 표시되어 있다면 O(n*n)이다.

 

이는 희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리함을 뜻한다.