[JAVA] BFS 기본 코드 (큐 사용)

BFS

BFS는 Breadth First Search의 줄임말로 너비 우선 탐색입니다.

DFS와 같이 기본적인 그래프 알고리즘 중 하나로, 시작 정점에서 연결된 모든 정점을 방문하고, 다시 방문한 하나의 정점을 시작점으로 해서 또 연결된 모든 정점을 방문하는 식으로 구현됩니다.

아래의 예시를 보면, 0부터 시작하여, 0에 연결된 1과 2를 방문하고, 다시 1을 시작점으로 1에 연결된 3과 4를 방문하고, 2로 와서 방문할 점을 찾았는데 더 이상 방문할 점이 없고, 3과 4에서 연결 점을 찾았는데 둘 다 없으므로 종료하는 식으로 동작합니다.

0 > 1 > 2 > 3 > 4 순으로 방문

 

JAVA BFS 구현

위의 이미지를 구현해보면 아래와 같습니다.

 

DFS와 동일하게 간선(Node)나 정점(Edge)의 정보는 ArrayList의 배열로 저장을 하였습니다.

BFS는 큐(Queue)를 이용해서 보통 구현을 하는데, 방문을 하면서 큐에 넣고, 큐에서 빼서 다음 방문할 정점을 찾는 식으로 동작합니다.

• Queue는 ArrayDeque라는 자료구조를 사용하여 구현 (ArrayDeque로 Statck과 Queue 모두 구현이 가능하고, 속도가 빠르고 저장공간의 제약이 없지만 단일 쓰레드 환경에서만 정상 동작)
• nodeList는 List<Integer>의 배열로 nodeList[0]은 0에 연결된 정점의 ArrayList ( [1,2] )가 저장됨
• visited 배열은 방문했는 여부를 저장하여 방문한 정점은 재 방문하지 않기 위한 배열로 visited[0]은 0 정점을 방문했는지 여부이고, 그 값이 0이면 미방문 / 1이면 방문
• N과 nodes라는 위의 이미지와 동일한 입력 데이터를 임의로 작성
• 입력받은 간선 정보를 nodeList에 저장 (무방향성인 경우 nodeList[0].add(1) / nodeList[1].add(0) 양방향 모두 저장)
• 0부터 출발한다고 하였을 때, 0을 방문처리(vdisited[0]=1)하고 큐에 0을 저장하고 bfs 알고리즘 수행
• 큐에서 가장 먼저 넣은 정점을 꺼내고 연결된 모든 정점을 검사하며 방문을 안 했으면 방문을 하고 해당 정점을 큐에 저장 > 다시 큐에 가장 먼저 넣은 정점을 꺼내고 위의 동작을 반복 > 큐에 아무것도 없게 될 때까지 반복 

import java.util.*;

public class Bfs_cd {
    static List<Integer>[] nodeList;
    static int[] visited;
    // 큐 용도로 사용 할 Array Deque 정의
    static ArrayDeque<Integer> queue = new ArrayDeque<>();
    public static void main(String[] args) throws Exception {
        // 입력 데이터
        int N = 5;
        int[][] nodes = {{0,1},{0,2},{1,3},{1,4}};

        // 리스트, 배열 초기화
        nodeList = new ArrayList[N];
        for(int i=0; i<N; i++) nodeList[i] = new ArrayList<>();
        visited = new int[N];

        // 입력받은 간선을 간선 리스트에 저장
        // ex) 1-2 : nodeList[1].add(2); nodeList[2].add(1); 
        // 무방향성이므로 양쪽을 저장 
        for(int[] e : nodes){
            nodeList[e[0]].add(e[1]);
            nodeList[e[1]].add(e[0]);
        }

        queue.clear(); // 큐 초기화
        bfs(0); // 0부터 출발
    }
    static void bfs(int start) {
        visited[start] = 1; // 0은 방문 처리
        queue.add(start); // 0을 큐에 저장

        while(!queue.isEmpty()){ // 큐에 아무것도 없을때까지 동작
            int cur = queue.poll(); // 큐에서 제일 먼저 넣은 정점을 꺼냄
            for(int next : nodeList[cur]) {
                if(visited[next] == 0) { // 이어진 점이 방문한 곳이 아니면
                    visited[next] = 1; // 방문 처리하고
                    queue.add(next); // 큐에 방문한 정점을 저장
                }
            }
        }
    }
}