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

DFS(Depth-First Search) 

깊이우선 탐색 

그래프 완전탐색 기법 중 하나 - 스택을 이용해서 그래프의 모든노드 탐색

그래프의 시작노드에서 출발 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 탐색하는 알고리즘

기능	특징	시간복잡도
그래프 완전 탐색	재귀함수로 구현  Stack 자료구조 이용(FILO) - 먼저 들어온 데이터가 나중에 나간다	O(V + E ) v : 노드 수 E : 에지 수

* 재귀함수 : 스택 오버플로 유의

 

 깊이우선탐색 핵심이론

• 한번 방문한 노드를 방문하면 안됨 : 노드 여부를 체크할 배열이 필요
• 그래프 : 인접리스트
• 후입선출의 특징 가지고 있음 / 스택을 이용한 탐색

public class Dfs {
    public static void main(String[] args) {
        int start = 1; // 시작 노드
        dfs(start);
    }
 
    // 각 노드가 연결상태를 2차원 배열로 표현
    // 해당 graph의 인덱스번호의 배열은 해당 노드에서 연결된 노드를 갖는다.
    //                      0번  1번    2번    3번     4번    5번   6번   7번
    static int[][] graph = {{}, {2, 3}, {4}, {5, 6}, {2}, {5, 7}, {3}, {7}};
 
    // 방문처리에 사용 할 배열
    static boolean[] visited = new boolean[graph.length];
 
    static void dfs(int index) {
        // 현재 노드를 방문 처리
        visited[index] = true;
 
        // 방문 노드 출력
        System.out.print(index + " -> ");
 
        // 방문한 노드에 인접한 노드 찾기
        for (int node : graph[index]) {
            // 인접한 노드가 방문한 적이 없다면 재귀 호출
            if(!visited[node]) {
                dfs(node);
            }
        }
    }
}