[카테고리:] <span>C언어 알고리즘</span>

이제 C언어로 너비우선 탐색 알고리즘을 구현해 보아요.

여기에서는 큐와 그래프, 경험 정보를 이용해서 구현할 거예요. 이 중에 큐에 관한 코드는 8.1.2 너비 우선 탐색 알고리즘 소스 코드(인접행렬)을 참고하세요. 여기서 사용할 큐에 관한 설명은 하지 않을게요. 이에 관한 설명은 디딤돌 자료구조와 알고리즘 with C언어에 있습니다.

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

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);
}