[DataStructure&Algorithm] BFS, 너비 우선 탐색

BFS, Breadth-First Search

 

---

개념 - BFS란?

BFS란, Breadth-First Search의 약자로 너비 우선 탐색을 의미합니다.

BFS는 그래프 구조에서 사용하는 탐색 알고리즘 중 하나로 루트노드부터 리프노드까지 동일한 레벨들의 노드들을 탐색을 진행하는 알고리즘이다. 루트노드에서 간선을 타고, 다음 노드로 이동하게 된다면, 동일한 거리만큼 떨어져있는 노드들을 전부 조사하고, 해당 노드들의 방문 여부를 처리하면서 탐색을 진행하는 알고리즘입니다.

 

BFS가 진행되는 과정

 

순서

1. 특정 노드 혹은 루트 노드에서 시작

2. 해당 노드로부터 동일한 거리(레벨)에 떨어져 있는 노드 조사 후 큐에 삽입

3. 반복문을 통해 해당 노드들에서 갈 수 있는 노드들이 있는지 조사

4. 모든 노드들을 방문했다면 종료

 

이러한 순서대로 BFS를 진행한다. 하지만 이렇게만 보면 정확하게 감이 생기지 않을 수 있어서 코드와 함께 설명할 예정이다.

---

특징

• 재귀적으로 동작하지 않는다. -> 반복문을 통해 순서대로 처리해야한다.
• 반드시 방문 여부를 체크해야한다.
• FIFO 구조를 가지고 있어, Queue 자료구조를 사용해야한다.
• Dijkstra 알고리즘과 비슷하다.

---

구현

public static void bfs(int[][] graph,int start_idx){
		
    // 방문 여부를 표시하기 위한 visited 배열
    boolean[] visited = new boolean[graph.length];

    // BFS 알고리즘을 구현하기 위한 Queue
    // Queue는 LinkedList Interface를 통해 구현
    Queue<Integer> q = new LinkedList<>();

    // 루트노드 정보 삽입
    q.add(start_idx);

    while(!q.isEmpty()){
    	// 현재 노드
        int cur = q.poll();
		
        // 방문하지 않았다면, poll
        if(!visited[cur]){
        
        	// 방문 여부 표시
            visited[cur] = true;
            System.out.print(cur+" ");
            
            // 현재 노드에서 방문할 수 있는 노드가 있으면서,
            // 방문하지 않은 노드라면 Queue에 add
            for(int i = 0; i< graph[cur].length; i++){
                if(graph[cur][i] == 1 && !visited[i]){
                    q.add(i);
                }
            }
        }
    }
}

 

2차원 배열인 graph를 넣고, start_index를 넣어주면 해당 노드부터 BFS를 수행하여 출력하는 함수이다.

 

설명

	1	2	3	4
1	0	1	1	1
2	1	0	0	1
3	1	0	0	1
4	1	1	1	0

0은 방문 불가, 1은 방문 가능 // DFS의 graph와 동일

노드의 상태

 

위와 같은 방문 가능 여부를 가지는 graph가 존재한다고 할 때, 1번 노드부터 BFS를 진행한다고 가정하자.

 

1번 노드는 2, 3, 4번 노드를 방문 할 수 있으니까, 아래와 같은 Queue 상태와 방문 여부 visited를 갖게 될 것이다.

 

Queue와 visited의 상태 변화

 

2, 3, 4번 노드를 Queue에 삽입하고, 1번 노드의 방문 여부를 1로 설정하였다.

그 다음으로 움직이면서, 2번 노드로 이동하고 해당 노드의 방문 여부를 파악하고, 또 다른 노드로 갈 수 있는 지를 파악하여 Queue에 삽입한다. 반복문을 통해서 DFS와는 다르게 재귀적이지 않으면서, 들어오는 데이터를 순서대로 처리하고 있는 것을 확인 할 수 있다.

 

마무리

이렇게 이전 포스팅과 이번 포스팅을 통해서 DFS와 BFS의 기본적인 개념과 구현 방법, 로직들을 살펴봤다.

비록 간단하게만 알아봤을 뿐이지만, 정리하면서 머리에 이해가 되는 시간이였다.

 

---

참고

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog