9.1 인접 행렬을 이용한 너비 우선 탐색 구현

이제 구현해 보기로 해요.

여기에서는 이미 앞에서 구현한 큐와 그래프, 경험 정보를 이용해서 구현할 거예요.

테스트에 사용할 그래프는 인접행렬을 이용한 깊이 우선 탐색과 같아요.

Graph *MakeGraph()
{
    Graph *graph;
    graph = NewGraph(8);//그래프 동적 생성
    AddEdge(graph, 0, 1);//간선 추가
    AddEdge(graph, 0, 2);//간선 추가
    AddEdge(graph, 0, 3);//간선 추가    
    AddEdge(graph, 1, 2);//간선 추가
    AddEdge(graph, 2, 3);//간선 추가
    AddEdge(graph, 2, 4);//간선 추가
    AddEdge(graph, 2, 5);//간선 추가    
    AddEdge(graph, 3, 4);//간선 추가    
    AddEdge(graph, 5, 6);//간선 추가
    AddEdge(graph, 6, 7);//간선 추가    
    ViewGraph(graph);    
    return graph;
}

너비우선 탐색 알고리즘를 구현해 보기로 해요.

입력 인자로 그래프와 출발 정점(v)과 목적 정점(g)을 받게 할게요.

void DoBFSAlgorithm(Graph *graph, int v,int g)
{
    EHQueue *ehq = 0;
    Heuristic *heu = 0;    
    Array *next_heus = 0;
    Iterator seek=0, end=0;

    printf("%d에서 %d로 갈 수 있는 모든 경로\n",v,g);

먼저 큐와 초기 경험 정보를 생성하세요.

    ehq = New_EHQueue();
    heu = MakeInitHeuristic(graph,0,7);

큐에 초기 경험 정보를 보관하는 것으로 출발해요.

    EHQueue_Put(ehq,heu);

큐가 비어있지 않을 때까지 반복합니다.

    while( ! EHQueue_IsEmpty(ehq) )
    {

큐에서 경험 정보를 꺼내오세요.

        heu = (Heuristic *)EHQueue_Get(ehq);

꺼내온 경험 정보에서 갈 수 있는 모든 이웃하는 경험 정보를 조사하세요.

        next_heus = New_Array();
        FindNextHeuristics(heu,next_heus);

조사한 경험 정보를 하나 하나 순차 방문해야겠죠.

        seek = Array_Begin(next_heus);
        end = Array_End(next_heus);
        for(seek=seek; seek != end; ++seek)
        {
            heu = (Heuristic *)(*seek);
            if(IsGoal(heu))
            {

만약 목적지에 도달했으면 경로를 찾은거예요.

경험한 행적을 출력하세요.

                ViewHeuristic(heu);
                DeleteHeuristic(heu);
            }
            else
            {

만약 목적지에 도달하지 못했으면 다시 큐에 보관하세요.

                EHQueue_Put(ehq,heu);
            }
        }
        Delete_Array(next_heus);
    }        
    Delete_EHQueue(ehq);
}