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

이제 깊이우선탐색 알고리즘의 Heuristic 을 구현합시다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

총 거리를 출력합시다.

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

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

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


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.