[알고리즘 C언어] 8.2.2 너비 우선 탐색 알고리즘 구현(정점과 간선으로 표현한 그래프 이용)

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

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

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

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

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