너비 우선 탐색
너비우선탐색이란 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. --위키피디아 출처
깊이우선탐색은 스택을 이용하지만 너비우선탐색은 큐를 이용한다.
말은 간단하다.
한번살펴보자
1에서 시작을 한다면 인접한 정점으로 이동한다.
1에서 인접한 정점은 2와3이다. 그래서
1->2,
1->3으로 이동한다.
그리고 2의 인접한 정점은 4밖에 없다.
2->4
다음은 3의 인접한 정점은 5,6,7 이다
3->5,
3->6,
3->7
이렇게 이동한다.
코드를 보자.
static int[][] BFS = {
{0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0},
{0,1,0,0,1,0,0,0},
{0,1,0,0,0,1,1,1},
{0,0,1,0,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
{0,0,0,1,0,0,0,0},
};
static int rear = 0, front = 0; // 전단과 후단을 나타내는 변수
static int queue[] = new int[10] , search[] = new int[10]; //큐와 방문한 정점을 체크하고 위함
큐를 사용하기 때문에 큐에다 넣을 배열을 만든다.
큐에 넣을때는 rear을 사용 빼야할때는 front를 사용한다.
public static void BFS(int s){
search[s] = 1;
queue[rear++] = s;
//큐에서 다 빼낼때까지
while (front < rear){
s = queue[front++];
for(int i = 1; i <=7; i++){
if(BFS[s][i] == 1 && search[i] != 1){
search[i] = 1;
System.out.println(s + "에서 " + i + "로 이동!");
queue[rear++] = i;
}
}
}
}
이것도 마찬가지로 정점을 방문하지 않고 인접행렬일때만 이동한다.
방문할때 방문했다고 체크해주고 큐에 쌓는다. 그리고 방문이 끝났다면 다시 큐에서 꺼내 꺼낸 값의 정점들을 찾는다.
그럼 결과는 다음과 같을 것이다.
1에서 2로 이동!
1에서 3로 이동!
2에서 4로 이동!
3에서 5로 이동!
3에서 6로 이동!
3에서 7로 이동!