dfs(depth first search) / bfs(breadth first search)

[WonYong-Jang]

dfs

==> 스택 으로도 구현 가능!!!! 알아보기

• 해가 존재할 가능성이 있으면 재귀호출을 이용하여 계속 깊게 전진 후 더이상
• 스택의 특징(Last In First Out)
• 장점 : 목표노드가 깊은 단계에 있을 경우 해를 빨리 찾을 수 있음
• 단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음
• 시간 복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E) ==> 모든 정점을 한번씩 방문하며, 정점을 방문 할 때 마다 인접한 모든간선을 검사하기 때문 ( 한 정점을 검사하는 dfs()를 수행하면 모든 간선을 정확히 한 번(방향 그래프의 경우) 혹은 두 번(무향 그래프의 경우) 확인하므로 )
• 공간 복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E)

  bfs

• 생성된 순서에 따라 노드를 확장한다. ( 시작 정점을 출발로 큐 구조에 방문한 정점을 넣어가며 탐색을 함)
• 다음 레벨의 노드를 조사하기 전에 트리의 같은 레벨의 노드 부터 검사 하는 방법 (자식의 자식들이 고려되기 전에 현 노드의 바로 밑에 있는 자식 노드가 조사된다는 것을 의미)
• 큐의 특징(First In First Out)
• 장점 : 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다
• 단점 : 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 시간 복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E) ==> 모든 정점을 한번씩 방문하며, 정점을 방문 할 때 마다 인접한 모든간선을 검사하기 때문
• 공간 복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E)

  소스 코드

public static int[][] map = new int[1002][1002]; // 인접 행렬
public static int[] visited = new int[1002]; // 방문 기록 
public static void dfs(int v) {

    if(visited[v] == 1 ) return; // base case 
    visited[v] = 1; // 방문 체크
    System.out.print(v+" ");
    for(int i= 1; i<= V ; i++) {
        if(map[v][i] == 1) { 
            dfs(i); //  다음 노드로 이동
        }
    }

}
public static void bfs(int v) {
    Queue<Integer> que = new LinkedList<Integer>();
    que.add(v); // 시작점 
    visited[v]=1;

    while(!que.isEmpty()) {
        int num = que.peek();
        System.out.print(num+" ");
        que.poll();

        for(int i= 1; i<= V ; i++) {
            if(map[num][i] == 1 && visited[i] == 0) { // 방문 기록이 없다면
                visited[i] = 1;
                que.add(i);
            }
        }
    }
}