BFS 구현

BFS 개념: https://yongdeok.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84

DFS를 완전히 이해하면 더 쉽게 이해할 수 있다.

compile with

CircularQueue → https://yongdeok.tistory.com/7

LinkedList → https://yongdeok.tistory.com/3

Bfs.c

void BFShowGraphVertex(ALGraph *pg, int startV)
{
    Queue queue;
    int visitV = startV;
    int nextV;

    QueueInit(&queue);

    VisitVertex(pg, visitV);

    while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)
    {
        if (VisitVertex(pg, nextV) == TRUE)
            Enqueue(&queue, nextV);
        while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE)
        {
            if (VisitVertex(pg, nextV) == TRUE)
                Enqueue(&queue, nextV);
        }
        
        if (QIsEmpty(&queue) == TRUE)
            break;
        else
            visitV = Dequeue(&queue);
    }
    memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

DFS와의 유일하게 다른 코드이다. 이 역시 코드를 그려가면서 정리하다보면 금방 이해가 될 것이다. 물론 Stack대신 Queue를 include해야 한다!.

Bfs.cpp

void ALGraph::BFShowGraphVertex(int startV)
{
    Queue queue;
    int visitV = startV;
    int nextV;

    queue.QueueInit();

    VisitVertex(visitV);

    while (adjList[visitV].LFirst(&nextV) == true)
    {
        if (VisitVertex(nextV) == true)
            queue.EnQueue(nextV);
        while (adjList[visitV].LNext(&nextV) == true)
        {
            if (VisitVertex(nextV) == true)
                queue.EnQueue(nextV);
        }
        
        if (queue.QIsEmpty() == true)
            break;
        else
            visitV = queue.DeQueue();
    }
    memset(visitInfo, 0, sizeof(int) * numV);
}