DFS, BFS

참고:

https://developer-mac.tistory.com/64

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

 

• DFS, BFS 시간복잡도

인접 리스트 : O(접점 + 간선)
인접 행렬 : O(접점^2)

 

 

DFS (Depth First Search) : 깊이 우선 탐색

이미지 출처 :https://developer-mac.tistory.com/64

 

• 정의

노드들이 포함된 브랜치 하나를 완벽하게 탐색 후 다른 브랜치 탐색

 

 

• 과정

1. 탐색 시작 노드를 스택에 삽입, visited 처리

2. 스택의 top 노드에 인접 & visited 처리되지 않은 노드를 스택에 삽입, visited 처리

3. 모든 인접 노드가 visited 처리됐을 시 스택의 top 노드를 꺼냄

(2, 3 반복)

 

 

• 구현

재귀함수 or 스택으로 구현

 

 

 

• 코드

//재귀

    dfs(int vertex, boolean[] visited){ //시작 정점, 방문 여부 배열

        visited[vertex] = true;
        sb.append(vertex).append(" ");

        for (int i=0;i<graph.get(vertex).size();i++){
            if (!visited[graph.get(vertex).get(i)]){ //하위 노드들 visited 여부 확인
                dfs(graph.get(vertex).get(i), visited);  //하위 노드들 접근
            }
        }

    }

 

 

 

• 장단점

장점 :

현 경로의 노드만 기억하면 되므로 저장 공간 수요가 비교적 적음

목표 노드가 깊은 단계에 있을 때 해를 빨리 구할 수 있음

 

단점 :

해가 없는 경로에 깊이 빠질 수 있어 미리 깊이 제한 지정하는 방법 권장됨

목표 노드에 다다르면 탐색을 끝내므로 얻은 해는 최적이 아닐 수 있음

 

 

 

BFS (Breadth First Search) : 너비 우선 탐색

이미지 출처 :https://developer-mac.tistory.com/64

 

• 정의

시작 노드 또는 임의 노드와 인접한 노드들 우선 탐색

=> 최단 경로 탐색에 활용

 

 

• 과정

1. 탐색 시작 노드를 큐에 삽입, visited 처리

2. 큐에서 노드를 꺼낸 후 해당 노드에 인접 & visited 처리 안 된 노드를 모두 큐에 삽입, visited 처리

(2 반복)

 

 

• 구현

큐로 구현

 

 

• 코드

    void bfs(int vertex){ //시작 정점

        boolean visited[] = new boolean[N+1]; //방문 여부 배열

        Queue<Integer> queue = new LinkedList<Integer>();
        
        queue.offer(vertex); //시작 정점 큐에 추가
        visited[vertex] = true; //시작 정점 방문 처리

        while (!queue.isEmpty()){
            int nearVertex = queue.poll(); //큐에 저장된 인근 노드(처음엔 시작 노드) poll
            sb.append(nearVertex).append(" ");

            for (int i=0;i<graph.get(nearVertex).size();i++){
                if (!visited[graph.get(nearVertex).get(i)]){ //하위 노드들 방문 여부 확인
                    queue.add(graph.get(nearVertex).get(i)); //큐에 추가
                    visited[graph.get(nearVertex).get(i)] = true;
                }
            }
        }

    }

 

 

 

• 장단점

장점 : 최단(최적) 경로 구할 수 있음

단점 : 경로가 매우 긴 경우, 탐색 가지가 급증해 저장 공간이 비교적 많이 필요함