너비 우선 탐색_BFS(Breadth First Search)

BFS(Breadth First Search)

BFS는 그래프를 완전탐색하는 방법 중 하나로 너비를 우선하여 탐색하는 방법입니다. 즉, 출발하는 지점(시작노드)에서 인접 노드(가장 가까이 있는 노드를 우선적으로)를 모두 방문하고, 방문한 노드에서 다시 인접노드를 모두 방문하는 것을 반복하면서 탐색하는 방법입니다.

위의 그래프에서 탐색을 하는 과정을 순서대로 보면 다음과 같습니다 [1 -> 2 -> 3 -> 4 -> 5]

1. 1번노드를 시작 노드라고 한다면 1번과 인접한 노드인 2, 3번 노드를 방문하게 됩니다.
2. 2번 노드와 인접한 4, 5번 노드를 방문합니다. (모든 노드 탐색 끝)
3. 3번 노드와 인접한 1, 5번 노드, 4번 노드와 인접한 2, 5번 노드, 5번 노드와 인접한 2, 3, 4번 노드는 앞에서 모두 탐색했으므로, 방문하지 않습니다. [BFS를 활용한 알고리즘을 해결할 때는 이렇게 방문 표시를 할 수 있는 변수 또는 배열이 있으면 좋습니다.] 

그렇다면 위의 그래프를 탐색하는 코드를 확인해보면서 실행 과정을 보겠습니다.

가장 먼저 큐에 시작 노드가 들어오게 됩니다. 방문 표시를 먼저 해주고, 큐에 enqueue한 다음, 방문 합니다.

방문한 1번 노드와 인접한 2, 3번 노드에 방문 표시를 먼저 해주고, 큐에 enqueue해줍니다. 먼저 들어온 노드부터 방문합니다. 위 그림상황에서는 2번 노드를 먼저 방문합니다.

방문한 2번 노드와 인접한 4, 5번 노드에 방문표시를 먼저 해주고, 큐에 enqueue합니다. 그런다음 큐에 front에 있는 요소를 꺼내 그 노드를 방문합니다. 그렇다면 3번 노드를 방문하게 됩니다. 3번 노드와 인접한 1번 5번 노드를 보니 이미 방문표시가 되어 있습니다. 따라서 별도의 작업없이 해당 반복을 종료합니다. 그다시 큐에 front에 위치한 요소를 빼서 방문합니다. 여기서 부터는 큐의 저장된 순서대로 4, 5번을 방문하는데 위의 3번 노드와 같이 방문한 후 인접노드를 봤지만 모두 방문표시가 되어 있기 때문에 별도의 작업없이 반복을 종료합니다. 

위와 같은 이유로 방문 표시를 먼저 해주는 것입니다. 인접한 노드를 매번 큐에 추가하기 전에 방문 여부를 확인하고 방문하지 않은 곳이라면 큐에 넣기 때문입니다.

나머지는 아래 소스 코드를 참고하여 실행 과정을 비교해보시기 바랍니다.

package BFS;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class bfs {
    //노드의 최대값
    static final int MAX_N = 10;
    static int N, E;
    //인접배열로 그래프 표현하기
    static int[][] Graph = new int[MAX_N][MAX_N];
    
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        //노드의 개수
        N = sc.nextInt();
        //간선의 개수
        E = sc.nextInt();
        
        //간선의 개수가 이동할 수 있는 경로 이므로 간선의 개수만큼 반복하면서 노드의 쌍을 읽어들인다.
        for(int i=0; i<E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            //u노드에서 v노드로 갈 수 있다는 의미이므로 1로 셋. 방향성이 없는 그래프이므로 v -> u로 가능 방향도 같기 때문에 같이 1로 셋해준더ㅏ. 
            Graph[u][v] = Graph[v][u] = 1; 
        }
        //입력으로 시작노드의 위치를 전달한다.
        bfs(0);
    }
 
 
 
    private static void bfs(int node) {
        // TODO Auto-generated method stub
        //초기값은 false로 저장됩니다. 
        boolean []visited = new boolean[MAX_N];
        
        //자료구조로 큐를 사용
        Queue<Integer> q = new LinkedList<>();
        //푸시하기 전에 해당 위치에 방문했다는 표시를 해줍니다. 
        //DFS와는 달리 큐의 구조는 FIFO이므로 어차피 먼저  큐에 들어온 요소가 제일 먼저 나가게 됩니다.[제일 먼저 탐색을 합니다]
        //따라서 방문을 하고 나서 방문 표시를 하는 것은 동일한 요소를 큐에 또 넣은 것이기 때문에 의미가 없습니다.
        //즉, 방문 표시를 하고! enqueue한 다음! 큐에 가장 먼저 들어온 노드부터 방문을 시작합니다.
        visited[node] = true; 
        q.add(node);
        
        //큐가 빌때까지 -> 모든 노드를 탐색할 때까지
        while(!q.isEmpty()) {
            //큐에 가장 먼저 들어온 요소를 뽑아서 방문합니다. 
            int curr = q.remove();
            
            System.out.print(curr + " ");
            
            //1번 노드와 인접한 노드를 방문합니다.
            for(int next = 0; next<N;++next) {
                //방문하지 않았거나, 현재위치 curr에서 다음 위치next로 넘어갈 수 있는 경우.(간선으로 연결되어 이동할 수 있는가?) 
                //graph배열은 노드를 연결하는 간선의 여부, 즉 이동가능한 경로를 저장한 배열입니다. 
                //(0:간선x) (1:간선o)  
                if(!visited[next] && Graph[curr][next] != 0) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }
 
}
 

 

[정리]

• 가까운 인접노드를 먼저 방문하면서 모든 노드를 방문합니다.
• 방문순서를 정하기 위해서 큐 자료구조를 사용합니다. 
• 방문 표시를 먼저 해주고 큐에 노드정보를 넣어줍니다.