BFS

너비 우선 탐색

꼼꼼하게 좌우를 살피며 다니자

구현을 위해 큐(QUEUE)가 필요

 

1. 시작 정점을 '방문했음' 표시하고 큐에 삽입

2. 큐로부터 정점을 제거. 제거한 정점의 인접 정점 중 아직 방문하지 않은 곳을

    '방문했음' 표시하고 큐에 삽입

3. 큐가 비면 탐색 종료.

void BFS( Vertex* V, LinkedQueue* Queue )
{
    Edge* E = NULL;
 
    printf("%d ", 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 )
            {
                printf("%d ", V->Data);
                V->Visited = Visited;
                LQ_Enqueue( Queue, LQ_CreateNode( V ) );
            }
 
            E = E->Next;
        }
    }
}