티스토리 뷰
BFS는 DFS와 더불어 그래프 이론의 가장 기본적인 탐색기법중 하나로,
그래프의 너비를 우선하여 탐색하는 알고리즘이다.
간단한 그래프를 예시로 들어 설명해보겠다.
다음과 같은 그래프가 있다고 가정하고 1번 정점부터 탐색을 시작한다고 할때,
너비우선탐색을 실행하면 1 >> 2 >> 3 >> 4 >> 5 >> 6 >> 7 >> 8 순으로 탐색을 진행한다.
보다 자세한 과정을 설명하자면 다음과 같다.
1. 현재 정점을 방문처리후 큐에 삽입한다.
2. 큐에서 정점을 꺼내고 정점과 연결된 다른 정점중 방문하지 않은 정점을 현재 정점 취급한다.
3. 1, 2 과정을 큐가 빌때까지 반복한다.
조금 더 자세한 과정의 설명을 위해 위의 그래프를 예시로 들어 보겠다.
꺼낸 정점은 현재 '1' 이므로 '1' 과 연결되어있고 방문하지 않은 정점 '2', '3' 을 순차적으로 큐에 삽입한다.
다음은 다시 큐에서 꺼낸 정점 '2' 와 연결된 정점중 방문하지 않은 정점을 순차적으로 방문처리후 큐에 삽입한다.
역시 다음 정점인 '3' 에 대해서도 같은 과정을 수행한다.
현재 모든 정점을 방문한 상태이므로 더 이상은 큐에 삽입은 이루어지지 않고 큐에 남은 정점을 꺼내는 과정만 진행된다.
따라서 이와 같은 탐색 수행후 방문순서의 결과는
1 >> 2 >> 3 >> 4 >> 5 >> 6 >> 7 >> 8 순으로 진행되는 것을 알 수 있다.
이제 코드로 구현을 해보도록 하겠다.
우선 현재 그래프을 표현할 인접행렬, 방문처리할 배열, 정점의 수, 정점 저장할 큐에 대한 멤버변수 선언을 한다.
큐도 그냥 1차원 배열을 통해 간단히 구현해 사용하도록 하겠다.
// 그래프
private int[][] metrix;
// 방문처리할 배열
private boolean[] visit;
// 정점의수
private int n;
// 큐
private int[] queue;
private int front, rear;
양방향 그래프 이므로 간선을 입력받을 메소드를 하나 만들어준다.
/**
* 양방향 그래프의 간선 입력
* @param a : 정점1
* @param b : 정점2
*/
public void init(int a, int b) {
metrix[a][b] = metrix[a][b] = 1;
}
멤버변수로 선언한 자원에 대해 객체를 생성할 메소드도 하나 만들어준다.
/**
* 인접행렬, 방문처리할배열, 큐 객체 생성
* @param n : 정점의 수
*/
public void setting(int n) {
this.n = n;
metrix = new int[n + 1][n + 1];
visit = new boolean[n + 1];
queue = new int[n];
}
위에서 설명한 로직을 이제 코드로 구현해보자.
1. 현재 정점을 방문처리후 큐에 삽입한다.
- 탐색을 시작할 정점을 인자로 받도록 했다.
public void bfs(int start) {
queue[rear++] = start; // push
visit[start] = true;
}
2. 큐에서 정점을 꺼내고 정점과 연결된 다른 정점중 방문하지 않은 정점을 현재 정점 취급한다.
public void bfs(int start) {
queue[rear++] = start; // push
visit[start] = true;
// 큐에서 정점을 꺼냄
int node = queue[front]; // pop
queue[front++] = 0;
front%=n;
System.out.print(node + "\t"); // 방문순서 출력
for(int i = 1; i <= n; i++) { // 순차적으로 연결된 정점을 찾는다.
if(metrix[node][i] == 1 && !visit[i]) { // 연결되어있으면서 방문하지 않은 정점
visit[i] = true; // 방문처리
queue[rear++] = i; // push
rear%=n;
}
}
}
3. 큐가 비워질 때까지 1 ,2 를 반복한다.
/**
* BFS 알고리즘
* @param start 탐색 시작할 정점
*/
public void bfs(int start) {
queue[rear++] = start; // push
visit[start] = true;
while(queue[front] != 0) {
// 큐에서 정점을 꺼냄
int node = queue[front]; // pop
queue[front++] = 0;
front%=n;
System.out.print(node + "\t"); // 방문순서 출력
for(int i = 1; i <= n; i++) {
if(metrix[node][i] == 1 && !visit[i]) {
visit[i] = true; // 방문처리
queue[rear++] = i; // push
rear%=n;
}
}
}
}
이제 위에 작성한 코드를 실행시키고 예시로 들었던 그래프에 대한 입력을 주어
예상한 결과로 출력되는지 확인해보겠다.
입력)
정점의수 간선의수
한줄에 하나씩 간선입력
8 7
1 2
1 3
2 4
2 5
2 6
3 7
3 8
출력)
1 2 3 4 5 6 7 8
실행결과)
예상한 순서대로 탐색이 진행되는것을 확인 할수 있다.
아래는 코드의 전문이다.
package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* BFS 인접행렬 구현
* @author jaewan song
*
*/
public class BFSImpl {
// 그래프
private int[][] metrix;
// 방문처리할 배열
private boolean[] visit;
// 정점의수
private int n;
// 큐
private int[] queue;
private int front, rear;
/**
* 양방향 그래프의 간선 입력
* @param a : 정점1
* @param b : 정점2
*/
public void init(int a, int b) {
metrix[a][b] = metrix[a][b] = 1;
}
/**
* 인접행렬, 방문처리할배열, 큐 객체 생성
*/
public void setting(int n) {
this.n = n;
metrix = new int[n + 1][n + 1];
visit = new boolean[n + 1];
queue = new int[n];
}
/**
* BFS 알고리즘
* @param start 탐색 시작할 정점
*/
public void bfs(int start) {
queue[rear++] = start; // push
visit[start] = true;
while(queue[front] != 0) {
// 큐에서 정점을 꺼냄
int node = queue[front]; // pop
queue[front++] = 0;
front%=n;
System.out.print(node + "\t"); // 방문순서 출력
for(int i = 1; i <= n; i++) {
if(metrix[node][i] == 1 && !visit[i]) {
visit[i] = true; // 방문처리
queue[rear++] = i; // push
rear%=n;
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine()," ");
BFSImpl bfs = new BFSImpl();
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
bfs.setting(n);
while(m-- > 0) { // 간선입력
st = new StringTokenizer(in.readLine()," ");
bfs.init(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
in.close();
bfs.bfs(1);
/*
* 입력)
* 7 6
* 1 2
* 1 3
* 2 4
* 2 5
* 3 6
* 3 7
*
* 출력)
* 1 2 3 4 5 6 7
*/
/*
* 입력2)
* 9 8
* 1 2
* 1 6
* 2 3
* 2 4
* 2 5
* 6 7
* 6 8
* 6 9
*
* 출력2)
* 1 2 6 3 4 5 7 8 9
*/
}
}'알고리즘 > 구현' 카테고리의 다른 글
| 유클리드 호제법(JAVA) (0) | 2023.09.17 |
|---|---|
| [자료구조] 이진 트리와 순회의 구현(JAVA) (1) | 2023.09.16 |
| [자료구조] 큐(Queue)의 구현(JAVA) (0) | 2023.09.13 |
| [자료구조] 스택(Stack) 구현 (JAVA) (0) | 2023.09.12 |
| DFS(깊이 우선 탐색) 인접 행렬 구현 (JAVA) (0) | 2023.09.03 |