[C언어 알고리즘] 6.2.6 깊이우선탐색(DFS) 알고리즘의 경험 정보 구현

[C언어 알고리즘] 6.2.6 깊이우선탐색(DFS) 알고리즘 경험 정보 구현

---

 초기 경험 정보를 생성하는 함수를 작성합시다.

Heuristic *MakeInitHeuristic(Graph *graph,Vertex start,Vertex goal)

{

    Heuristic *heu = 0;

 경험 정보 크기의 메모리를 할당합니다.

    heu = (Heuristic *)malloc(sizeof(Heuristic));

 이동 경로를 보관할 동적 배열을 생성합니다.

    heu->exprs = New_Array();

 그래프와 출발점, 도착점을 설정합니다.

    heu->graph = graph;

    heu->start = start;

    heu->goal = goal;

 출발점을 이동 경로에 보관합니다.

    Array_PushBack(heu->exprs,(Element)start);

 그리고 현재까지의 총 거리를 0으로 설정한 후에 경험 정보를 반환합니다.

    heu->total_weight = 0;

    return heu;

}

 

 동적으로 생성한 경험 정보를 소멸하는 함수를 작성합시다.

void DeleteHeuristic(Heuristic *now)

{

 이동 경로를 보관하기 위해 할당했던 동적 배열을 소멸한 후에 자신의 메모리를 해제합니다.

    Delete_Array(now->exprs);

    free(now);

}

 

 현재 경험 정보에서 수행할 수 있는 다음 경험 목록을 조사하는 함수를 작성합시다.

void FindNextHeuristics(Heuristic *now, Array *next_heus)

{

    Array *next_vts = 0;

    Iterator seek=0, end=0;

    Vertex next_vt;

    Heuristic *next;

 현재 정점에서 갈 수 있는 이웃 정점 목록을 보관하기 위한 배열을 생성합니다.

    next_vts = New_Array();

 그래프에서 현재 정점의 이웃하는 정점 목록을 구합니다.

    Graph_FindNeighvor(now->graph,GetLastVertex(now),next_vts);

 이웃 정점 목록의 시작과 끝을 구합니다.

    seek = Array_Begin(next_vts);

    end = Array_End(next_vts);

 순차적으로 이동하면서 이웃 정점을 구합니다.

    for(seek = seek; seek != end; ++seek)

    {

        next_vt = (Vertex)(*seek);

 만약 이웃 정점을 방문하지 않았을 때 처리를 합시다. 그리고 특정 정점을 방문한 것인지 확인하는 함수는 별도로 작성합시다.

        if( !IsExistVertex(now,next_vt) )

        {

 현재 경험 정보에 특정 정점을 방문하는 경험 정보를 생성합니다. 이 부분도 별도의 함수로 작성합니다.

            next = MakeNextHeu(now,next_vt);

 생성한 다음 경험 정보를 배열에 보관합니다.

            Array_PushBack(next_heus,next);

        }

    }

}

 

 특정 정점을 방문하였는지 확인하는 함수를 작성합시다.

int IsExistVertex(Heuristic *now, Vertex vt)

{

    Iterator seek=0, end=0;

    Vertex expr_vt;

 방문한 경로의 시작과 끝을 구하세요.

    seek = Array_Begin(now->exprs);

    end = Array_End(now->exprs);

 그리고 순차적으로 이동하면서 방문한 정점을 구합니다.

    for(seek = seek; seek != end; ++seek)

    {

        expr_vt = (Vertex)(*seek);

 

 

 입력 인자로 받은 정점과 같은 정점이면 이미 방문한 정점이므로 1을 반환합니다.

        if(strcmp(expr_vt,vt)==0)

        {

            return 1;

        }

    }

    return 0;

}

 

 현재 경험 정보에 특정 정점을 방문하는 다음 경험 정보를 생성하는 함수를 작성합시다.

Heuristic *MakeNextHeu(Heuristic *now,Vertex vt)

{

    Heuristic *heu = 0;

    Iterator seek=0, end=0;

    Vertex expr_vt;

 먼저 초기 경험 정보를 생성합니다.

    heu = MakeInitHeuristic(now->graph,now->start,now->goal);

 입력 인자로 받은 경험 정보의 방문한 경로의 시작과 끝을 구합니다.

    seek = Array_Begin(now->exprs);

    end = Array_End(now->exprs);

 시작 위치의 정점을 구합니다.

    expr_vt = (Vertex)(*seek);

 초기 경험 정보에서는 출발점을 방문한 상태로 출발합니다. 따라서 seek를 다음 위치로 이동한 후에 순차적으로 정점을 구합니다.

    for(seek++; seek != end; ++seek)

    {

        expr_vt = (Vertex)(*seek);

 새로 생성한 경험 정보의 이동 경로 보관 배열에 정점을 추가합니다. 이 처리를 통해 입력 인자로 받은 경험 정보와 같은 이동 경로를 갖습니다.

        Array_PushBack(heu->exprs,(Element)expr_vt);

    }

 새로 생성한 경험 정보의 총 거리를 입력 인자로 받은 경험 정보의 총 거리로 설정합니다.

    heu->total_weight = now->total_weight;

 총 거리에 마지막 방문한 정점과 새로 추가할 정점의 거리를 더합니다.

    heu->total_weight += Graph_GetWeight(heu->graph,expr_vt,vt);

 그리고 입력 인자로 받은 정점을 방문한 정점 목록에 추가합니다.

    Array_PushBack(heu->exprs,(Element)vt);

    return heu;

}

 

 마지막 방문한 정점을 구하는 함수를 작성합시다.

Vertex GetLastVertex(Heuristic *now)

{

 배열의 마지막 위치를 구합니다.

    Iterator end = Array_End(now->exprs);

 주의할 점은 마지막 위치는 마지막 보관한 자료의 다음 위치입니다. 따라서 위치를 1 감소합니다.

    --end;

 해당 위치에 보관한 정점을 반환합니다.

    return  (Vertex)(*end);

}

 

 도착점에 도달했는지 확인하는 함수를 작성합시다.

int IsGoal(Heuristic *now)

{

 마지막 정점이 도착점인지 비교한 값이 차이가 없는지 여부를 반환합니다.

    return strcmp(now->goal,GetLastVertex(now))==0;

}

 

 경험 정보를 출력하는 함수를 작성합시다.

void ViewHeuristic(Heuristic *now)

{

    Iterator seek=0, end=0;

 총 거리를 출력합시다.

    printf("총 거리:%d ",now->total_weight);

 이동 경로의 시작과 끝을 구합니다.

    seek = Array_Begin(now->exprs);

    end = Array_End(now->exprs);

 순차적으로 방문한 정점을 출력합니다.

    for(seek = seek; seek != end; ++seek)

    {

        printf("%s ",(Vertex)*seek);

    }

 다음 출력할 내용과 구분하기 위해 개행문자를 출력합시다.

    printf("\n");

}