BFS (Breadth-First Search)

들어가기전, 큐

https://devfunny.tistory.com/710

큐 (Queue)

 

 

BFS

- 너비 우선 탐색

- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

- 큐 자료구조를 이용한다.

 

[수행 과정]
1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다
2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다

 

 

BFS 동작 예시

0) 아래 그래프를 번호가 낮은 인접 노드부터 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

1) 노드 '1'을 큐에 삽입하고 방문한다.

https://freedeveloper.tistory.com/273?category=888096

 

2) 노드 '1'을 꺼낸다. 그리고, 노드 '1'에 인접 노드인 '2', '3', '4' 를 큐에 삽입하고 방문 처리한다.

https://freedeveloper.tistory.com/273?category=888096

 

3) 큐에서 노드 '2'를 꺼낸다. 그리고, 노드 '2'에 인접한 노드 '7'을 큐에 삽입하고 방문 처리한다.

https://freedeveloper.tistory.com/273?category=888096

 

4) 큐에서 노드 '3'을 꺼내고, 방문하지 않은 인접 노드 '4', '5'를 큐에 삽입하고 방문 처리한다.

https://freedeveloper.tistory.com/273?category=888096

 

5) 큐에서 노드 '8'을 꺼내고, 방문하지 않은 인접 노드가 없으므로 무시한다. 

https://freedeveloper.tistory.com/273?category=888096

 

6) 이러한 과정을 반복한다.

결과

https://freedeveloper.tistory.com/273?category=888096

 

 

BFS 구현코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * BFS
 */
public class M8_BFS {

    // 방문 여부
    public static boolean[] visited = new boolean[9];

    // 그래프
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        // 방문처리
        visited[start] = true;

        // 큐가 빌때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 원소를 뽑는다.
            int x = q.poll();
            System.out.println(x + " ");

            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입한다.
            for (int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);

                if (!visited[y]) { // 방문하지 않았을 경우 실행
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);

        // 노드 2에 연결된 노드 정보 저장
        graph.get(2).add(1);
        graph.get(2).add(7);

        // 노드 3에 연결된 노드 정보 저장
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);

        // 노드 4에 연결된 노드 정보 저장
        graph.get(4).add(3);
        graph.get(4).add(5);

        // 노드 5에 연결된 노드 정보 저장
        graph.get(5).add(3);
        graph.get(5).add(4);

        // 노드 6에 연결된 노드 정보 저장
        graph.get(6).add(7);

        // 노드 7에 연결된 노드 정보 저장
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

        // 노드 8에 연결된 노드 정보 저장
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }
}