반응형
-너비 우선 탐색(BFS)란?
그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. (또한 너비 우선 탐색은 두 정점 사이의 최단 거리를 구하거나 임의의 경로를 구할 때 사용한다고 하는데, 필자도 현재까지는 단순한 구현과 개념의 이해정도 수준에 그치기 때문에 후에 추가적으로 작성할 예정이다.) 그중 너비 우선 탐색은 아래와 같은 순서를 따른다.
- 시작 정점(V)을 방문한다.
- V에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하며 큐(Queue)에 삽입한다.
- 인접한 정점을 모두 방문했다면, 큐에 삽입했던 정점을 반환 후 2번을 반복한다.
- 큐가 공백이 될 때 까지 2~3을 반복한다.
즉 너비 우선 탐색의 경우에는 인접한 정점을 모두 방문하면서 큐에 삽입하는 방식이다. 너비 우선 탐색의 구현에 사용되는 자료구조는 1) 각 노드에 방문여부를 표시할 배열, 2) 정점의 저장을 위한 큐 정도가 될 수 있다. 물론 추가적으로 그래프의 구현을 위한 작업이 필요할 수 있지만, 여기선 ArrayList를 활용하여 인접 노드를 단순히 표현하도록 하겠다.
import java.util.*;
// 데이터는 1~7까지의 자료를 대상으로 한다.
public class BFS {
static int arr[] = new int[8]; // 정점의 방문여부를 체크 할 배열
static ArrayList<int[]> arrayList = new ArrayList<int[]>(); //그래프의 표현을 위한 ArrayList
public static void bfs(int start) { // BFS 메소드 시작 정점을 인자로 받는다
Queue<Integer> queue = new LinkedList(); // 방문했던 정점을 저장하기 위한 Queue
queue.offer(start); // 시작 정점을 방문했으므로 enQueue
arr[start] = 1; // 시작 정점을 방문했으므로 1로 체크해준다.
while(!queue.isEmpty()) { // 공백Queue가 될 때 까지 반복한다.
int x = queue.poll(); // deQueue연산을 통해 방문했던 정점을 반환한다.
System.out.println(x); // Output
for(int i=0;i<arrayList.get(x).length;i++) { // 인접한 정점의 수 만큼 반복한다.
int y = arrayList.get(x)[i];
if(!(arr[y]==1)) { // 인접한 정점을 방문하지 않았었다면,
queue.offer(y); // enQueue연산 후
arr[y]=1; // 방문여부 체크
}
}
}
}
public static void main(String[] args) {
arrayList.add(0,new int[] {0}); // 1~7의 데이터를 사용하므로 0번 인덱스는 0으로 채워둔다.
arrayList.add(1,new int[] {2,3}); // 1번 정점과 연결 된 정점들
arrayList.add(2,new int[] {1,3,4,5}); // 2번 정점과 연결 된 정점들
arrayList.add(3,new int[] {1,2,6,7});
arrayList.add(4,new int[] {2,5});
arrayList.add(5,new int[] {2,4});
arrayList.add(6,new int[] {3,7});
arrayList.add(7,new int[] {3,6});
bfs(1); // bfs 호출
}
}
이후 출력 결과는 1,2,3,4,5,6,7의 순서대로 나오게 된다.
반응형