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

이제 우선 순위 큐를 이용해서 너비 우선 탐색 알고리즘을 구현해 보기로 해요.

여기에서도 깊이 우선 탐색 알고리즘에서 만든 그래프와 경험 정보를 사용할 거예요.

먼저 테스트에 사용할 그래프를 생성하는 함수를 작성하세요.

이 부분은 깊이 우선 탐색에서 만든 것과 같아요.

Graph * InitSimulation()
{
    Graph *graph = New_Graph();		
    Graph_AddVertex(graph,"A");
    Graph_AddVertex(graph,"B");
    Graph_AddVertex(graph,"C");
    Graph_AddVertex(graph,"D");
    Graph_AddVertex(graph,"E");
    Graph_AddVertex(graph,"F");
    Graph_AddVertex(graph,"G");
    Graph_AddVertex(graph,"H");
    
    Graph_AddEdge(graph,"A","B",5);
    Graph_AddEdge(graph,"A","D",4);
    Graph_AddEdge(graph,"A","E",4);
    Graph_AddEdge(graph,"B","D",4);
    Graph_AddEdge(graph,"B","H",2);
    Graph_AddEdge(graph,"C","D",2);
    Graph_AddEdge(graph,"C","G",3);
    Graph_AddEdge(graph,"D","H",5);
    Graph_AddEdge(graph,"D","E",3);
    Graph_AddEdge(graph,"D","F",3);
    Graph_AddEdge(graph,"E","F",3);
    Graph_AddEdge(graph,"F","G",6);
    Graph_AddEdge(graph,"G","H",3);
    
    Graph_View(graph);
    return graph;		
}

우선 순위 큐에서 사용할 비교 알고리즘을 구현하기로 해요.

int CompareHeu(void *v1,void *v2)
{
    Heuristic *h1 = (Heuristic *)v1;
    Heuristic *h2 = (Heuristic *)v2;
    return h1->total_weight - h2->total_weight;
}

이제 구체적으로 너비 우선 탐색 알고리즘을 구현해 보아요.

int main()
{
    PriQueue *pq = 0;
    Heuristic *result = 0;
    Heuristic *heu = 0;
    Graph *graph = 0;
    Array *next_heus = 0;
    Iterator seek=0, end=0;

그래프와 우선 순위 큐를 생성하세요.

    graph = InitSimulation();
    pq = New_PriorityQueue(CompareHeu);

출발지와 목적지를 설정한 초기 경험을 생성하여 큐에 보관하세요.

    heu = MakeInitHeuristic(graph,"A","G");
    PriQueue_Put(pq,heu);

큐가 비어있지 않다면 다음을 반복합니다.

    while( ! PriQueue_IsEmpty(pq) )
    {

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

        heu = (Heuristic *)PriQueue_Get(pq);

현재 경험 정보를 출력할게요.

        ViewHeuristic(heu);

현재 경험 정보에서 방문할 수 있는 다음 경험 정보 목록을 조사하세요.

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

조사한 경험 정보를 순차적으로 확인하세요.

        seek = Array_Begin(next_heus);
        end = Array_End(next_heus);
        for(seek=seek; seek != end; ++seek)
        {
            heu = (Heuristic *)(*seek);            
            if((result ==0)||(result->total_weight > heu->total_weight))
            {

만약 목적지에 도달했으면 결과에 대입하세요.

                if(IsGoal(heu))
                {
                    if(result)
                    {
                        DeleteHeuristic(result);
                    }
                    result = heu;
                }
                else
                {

그렇지 않다면 다시 큐에 보관하세요.

                    PriQueue_Put(pq,heu);
                }
            }           
        }
        Delete_Array(next_heus);
    }

이제 결과를 출력하세요.

    printf("최단 거리\n");
    ViewHeuristic(result);
    Delete_Graph(graph);	
    Delete_PriQueue(pq);    
    return 0;
}

▷ 실행 결과

정점 개수:8
A
B
C
D
E
F
G
H
간선 개수:13
(A ,B):5
(A ,D):4
(A ,E):4
(B ,D):4
(B ,H):2
(C ,D):2
(C ,G):3
(D ,H):5
(D ,E):3
(D ,F):3
(E ,F):3
(F ,G):6
(G ,H):3
총 거리:0 A 
총 거리:4 A D 
총 거리:4 A E 
총 거리:5 A B 
총 거리:6 A D C 
총 거리:7 A D E 
총 거리:7 A D F 
총 거리:7 A E D 
총 거리:7 A E F 
총 거리:7 A B H 
총 거리:8 A D B 
총 거리:9 A D H 
총 거리:9 A B D 
최단 거리
총 거리:9 A D C G