[알고리즘] BFS(넓이 우선 탐색) - 코딩밥상

넓이 우선 탐색(Breadth First Search)이란?

'꼼꼼히 좌우를 살피며 다니자'는 원칙으로 그래프를 순회하는 알고리즘입니다.

넓이 우선 탐색에서는 시작 정점을 지난 후 깊이가 1인 모든 정점을 방문하고 그 다음에는 깊이가 2인 모든 정점을 방문합니다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점을 방문하다가 더 이상 방문할 정점이 없을 때 탐색을 종료합니다.

대표적인 이용 방법은 그래프의 최단경로에 사용됩니다.

 

알고리즘의 동작 방식을 구체적으로 정리하자면,

1. 시작 정점을 '방문했음'으로 표시하고 큐에 삽입합니다.
2. 큐로부터 정점을 제거합니다. 제거한 정점의 인접 정점 중에서 아직 방문하지 않은 곳을 '방문했음'으로 표시하고 큐에 삽입합니다.
3. 최종적으로 큐가 비면 탐색이 끝납니다.

출처 : 위키백과

---

코드 구현

void BFS(Vertex* V, LinkedQueue* Queue){
    Edge* E = NULL;
    
    cout<<V->Data<<' ';
    V->Visited = Visited;
    
    LQ_Enqueue(Queue, LQ_CreateNode(V));    //시작 정점을 큐에 삽입
    
    while(!LQ_Isempty(Queue)){  //큐가 비어있는지 검사
        Node* Popped = LQ_Dequeue(Queue);   //큐의 전단 제거
        V = Popped->Data;
        E = V->AdjacencyList;
        
        while(E != NULL){   //제거한 정점의 인접 정점을 조사
            V = E->Target;
            
            if(V != NULL && V->Visited == NotVisited){  //미방문 정점만 방문
                cout<<V->Data<<' ';
                V->Visited = Visited;
                LQ_Enqueue(Queue, LQ_CreateNode(V));
            }
            
            E = E->Next;
        }
    }
}