[카테고리:] <span>자료구조와 알고리즘</span>

이제 구현해 보기로 해요.

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

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

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