오늘은 너비우선탐색에 대하여 알아보고자 합니다.

개요

너비우선탐색,즉 BFS는 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 뒤에 다시 방문했던 정점을 시점으로 하여 인접한 정점들을 차례대로 방문하는 방식입니다.

간단히 말하자면, 가까운 정점들을 먼저 방문하고 멀리있는 정점은 나중에 방문하는 순회 방식입니다.

근처에 있는 정점들을 차례대로 다시 탐색해야 하는 특성상 자료구조중에 선입선출의 구조를 가진 큐를 사용합니다.

순서

1. 시작 정점 v를 결정하여 방문합니다.

2. 정점 v에 인접한 정점중에서 방문하지 않는 인접한 정점이 있다면 차례대로 방문히고 방문된 정점대로 큐에 넣습니다.

3. 만약 방문하지 않은 정점이 없다면 큐에서 빼내어 구한 정점을 v로 맞추고 다시 두번째 순서를 반복합니다.

4. 큐가 공백으로 될 때까지 두번째 순서를 반복합니다.

의사코드

for(i<-0;i<n;i<-i+1)do{
    visit[i]<-false;
}
queue<-create();
visit[v]<-true;
v.visit();
while(not isEmpty(queue)) do{
    while(visit[w]=false)do{
        visit[w]<-true;
        w.visit();
        enqueue(Q,W);
    }
    v<-dequeue(Q);
}