[C언어 알고리즘] 6.2.7 깊이우선탐색(DFS) 알고리즘 테스트 코드 작성

[C언어 알고리즘] 6.2.7 깊이우선탐색(DFS) 테스트 코드 작성

---

 먼저 알고리즘에 사용할 그래프를 생성하여 구성하는 함수를 작성합시다.

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",2);

    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;

}

 

 깊이우선탐색(DFS) 알고리즘 테스트 코드 작성 전에 다시 한 번 동적 알고리즘의 의사코드를 확인합시다.

 

동적 알고리즘

    초기 경험 정보를 생성

    스택에 초기 경험 정보 Push

    반복(스택이 빌 때까지)

        스택에서 경험 정보를 Pop

        꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사

        반복(다음 경험 정보들을 순차적으로)

            조건(결과에 도달하지 않았다면)

                스택에 경험 정보를 Push

            그렇지 않다면

                결과에 보관

 

int main()

{

    EHStack *ehs = 0;

    Heuristic *heu = 0;

    Graph *graph = 0;

    Array *next_heus = 0;

    Iterator seek=0, end=0;

 알고리즘 테스트에 사용할 그래프를 생성합니다.

    graph = InitSimulation();

 스택을 생성합니다.

    ehs = New_EHStack();

 초기 경험 정보를 생성합니다. 여기에서는 A점을 출발점으로 하고 H점을 도착점으로 할게요.

    heu = MakeInitHeuristic(graph,"A","H");

 초기 경험 정보를 스택에 보관합니다.

    EHStack_Push(ehs,heu);

 스택에 경험 정보가 남아있다면 반복 수행합니다.

    while( ! EHStack_IsEmpty(ehs) )

    {

 스택에 보관한 경험 정보를 꺼내옵니다.

         heu = (Heuristic *)EHStack_Pop(ehs);

 다음 경험 정보 목록을 보관할 동작 배열을 생성합니다.

         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{    EHStack_Push(ehs,heu);    }

        }

 임시로 다음 경험 정보 목록을 보관했던 배열을 소멸합니다.

        Delete_Array(next_heus);

    }

    Delete_Graph(graph);

    Delete_EHStack(ehs);

    return 0;

}

총 거리:16 A E F G H

총 거리:23 A E F G C D H

총 거리:24 A E F G C D B H

총 거리:15 A E F D H

총 거리:18 A E F D C G H

총 거리:16 A E F D B H

총 거리:12 A E D H

총 거리:19 A E D F G H

총 거리:15 A E D C G H

총 거리:13 A E D B H

총 거리:9 A D H

총 거리:16 A D F G H

총 거리:19 A D E F G H

총 거리:12 A D C G H

총 거리:10 A D B H

총 거리:7 A B H

총 거리:14 A B D H

총 거리:21 A B D F G H

총 거리:24 A B D E F G H

총 거리:17 A B D C G H