[알고리즘] BFS/DFS

0. 그래프

0.1 그래프

• 정점(node 혹은 vertex)과 간선(edge)로 이루어지 자료구조
  • 정점: 데이터를 저장하는 위치
  • 간선: 정점을 연결하는 선
  • 인접 정점: 간선에 의해 직접 연결된 정점 (ex. 1과 2는 인접 정점)
  • 차수: 무방향 그래프에서 하나의 정점에 인접한 정점의 수
    • ex. 1의 차수: 2와 5

0.2 그래프 구현 방법

0.2.1 인접 행렬 (Adjacency Matrix)

• 2차원 배열 이용
• matrix[ i ][ j ] == true 라면 i -> j로의 간선이 있음의미
  • int 행렬의 경우 1 = true, 0 = false
• 배열 구성 → 간선 정보 조회빠름 O(1)
• 간선의 개수 무관하게 항상 n^2의 메모리 공간 차지
• 인접한 노드를 찾기 위해 모든 노드 전부 순회해야함

0.2.2 인접 리스트(Adjacency List)

• 연결리스트를 이용하여 모든 정점을 인접리스트에 저장
• 연결된 노드의 개수와 딱 맞는 크기의 리스트 만들기에 메모리 사용량 상대적으로 적음
• 노드 추가삭제 빠름
• 간선 정보 확인이 상대적으로 오래걸림

*BFS/DFS 예제 그래프

 

//그래프
public static void main(String[] args) {
	ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    for(int i = 0; i<10; i++){
        graph.add(new ArrayList<>());
    }
        
	//각 노드에 연결된 노드 저장
    graph.get(1).add(2);
    graph.get(1).add(5);

    graph.get(2).add(1);
    graph.get(2).add(3);
    graph.get(2).add(4);

    graph.get(3).add(2);

    graph.get(4).add(2);

    graph.get(5).add(1);
    graph.get(5).add(6);
    graph.get(5).add(9);

    graph.get(6).add(5);
    graph.get(6).add(7);
    graph.get(6).add(8);

    graph.get(7).add(6);

    graph.get(8).add(6);

    graph.get(9).add(5);

	//1부터 시작
    bfs(1);
    dfs(1);
 }

1.BFS

• Breadth First Search ⇒ 너비 우선 탐색
• 시작 정점 방문 후 가까운 정점 우선 방문
• 넓게 탐색하는 방법
• 두 노드 사이 최단거리, 최단 경로 구할때 보통 사용
  • 장점
    • 최적해 찾음 보장
  • 단점
    • 최소 실행보다 오래걸림
• 위의 그래프를 탐색한다고 할때 과정

1.1 BFS 과정

1. 1번 노드에서 시작
2. 2,5번 노드로 갈수 있음 → 갈수 있는 모든 경로를 큐에 삽입
3. 2번 노드에서 갈 수 있는 모든 경로를 큐에 삽입
4. 5번 노드에서 갈 수 있는 모든 경로를 큐에 삽입
5. … 3,4,6,7 노드에서 갈 수 있는 모든 경로를 순서대로 큐에 삽입

⇒ 결과: 1 → 2 → 5 → 3 → 4 → 6 → 9 → 7 → 8 로 탐색

1.2 BFS 코드

public static boolean[] visited = new boolean[10];
public static void bfs(int start){
    LinkedList<Integer> queue = new LinkedList<>();

    //현재노드 방문 처리
    queue.offer(start);
    visited[start] = true;

    //큐가 빌때까지 반복
    while (!queue.isEmpty()){
        int target = queue.poll();
        System.out.print(target + " ");

        //target과 인접한 노드 방문처리
        for(int i = 0; i<graph.get(target).size(); i++){
            int next =  graph.get(target).get(i);
            if(!visited[next]){
                queue.offer(next);
                visited[next] = true;
            }
        }
    }
}

2.DFS

• Depth First Search ⇒ 깊이 우선 탐색
• 시작 정점 방문 후 다음 분기로 넘어가기 전 해당 분기 완벽하게 탐색
• 트리에서 보면 노드 방문 후 자식노드 우선 방문
• 깊게 탐색하는 방법
  • 장점
    • 최선의 경우 빠르게 해를 찾음
  • 단점
    • 찾은 해가 최적 해 아닐 가능성 있음
    • 최악의 경우 해 찾는데 가장 오랜 시간 걸림

2.1 DFS 과정

1. 1번 노드에서 시작
2. 2,5번 노드로 갈수 있음 ⇒ 숫자가 더 작은 2번 노드로(전략은 마음대로 설정)
3. 3,4번 노드로 갈 수 있음 ⇒ 3번 노드로 감
4. 3번 노드에서는 갈수 있는 곳이 없어 다시 2번 노드로 올라감
5. 2번 노드에서 ⇒ 4번 노드로 감
6. 4번 노드에서 갈수있는곳이 없음 2번 노드로 돌아감
7. 2번 노드에서도 자식노드에서 갈 곳이 없어 1번 노드로 돌아감
8. 1번노드에서 ⇒ 5번 노드로 감
9. … 이런식으로 반복해서 하나의 분기를 끝내고 다음 분기로

⇒ 결과: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9

2.2 DFS 코드

public static boolean[] visited = new boolean[10];
public static void dfs(int v){
        //현재 노드 방문 처리
        visited[v] = true;
        System.out.print(v + " ");

        //현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for(int i = 0; i<graph.get(v).size(); i++){
            int nextV = graph.get(v).get(i);
            if(!visited[nextV]) dfs(nextV);
        }
    }

3.BFS/DFS 비교

• BFS: Queue 로 구현 가능, DFS: 재귀함수로 구현 가능
• 시간복잡도는 둘다 동일하며, 그래프 구현에 따라 시간 복잡도 달라짐
  • 연결리스트로 구현: O(n+m) (n: 노드의 수, m: 에지의 수)
  • 행렬로 구현한 그래프: O(n^2)
• 일반적으로 BFS가 조금 더 빠름
• 경로의 특징을 저장해야하는 경우 → DFS
• 최단경로를 구해야하는 경우 → BFS