데이터 구조 - 최단거리 검색/탐색

소개

최단거리를 탐색하는 프로그램을 제작하는 데이터 구조 자료입니다.

레포트 내용과 소스까지 전부 포함하였습니다.

목차

1. 문제 제기
2. 문제 분석
1) 그래프의 저장
2) 최단거리(저번 과제의 비용 알고리즘 이용시 -> 최소비용)의 계산
3) 최소비용의 출력
3. 문제 해결
4. 결과 화면
5. 느낀점

본문내용

데이터 구조
<최단경로 탐색>
1. 문제 제기
그래프를 저장하고, 한 정점으로부터 다른 정점으로까지의 최단거리를 구하여라
2. 문제 분석
1) 그래프의 저장
그래프의 저장은 저번과제에서 나왔던 인접행렬로 저장하였다. 인접리스트를 쓰지 않은 이유는 인접리스트에서 지정된 좌표의 값을 찾으려면 탐색을 해야 하고, 그 비용이 공간의 이점을 훨씬 뛰어넘기 때문이다. 저장의 방법은 저번 과제와 동일 하므로, 더 설명하지 않겠다.
2) 최단거리(저번 과제의 비용 알고리즘 이용시 -> 최소비용)의 계산
최소비용의 계산에 쓰이는 기본적인 변수는 다음과 같다.
* 각 정점의 최소경로를 통한 비용을 저장할 double형 변수
* 각 정점의 최소경로를 저장할 int형 포인터
* 최소경로에 인접해있는 정점을 저장할 int형 배열
위에서 최소경로와 비용은 Node라는 클래스의 private로 선언하였다. 처음에 최소비용 계산 함수에서 class 맴버 변수로 선언된 Node 객체 포인터를 그래프의 크기만큼 동적 할당해준다. 예를 들어 이 소스 코드에서는 Node *head 라고 맴버 변수를 선언해 주었고, 이 맴버 변수를 head = new Node[size] 이렇게 동적 할당을 한 것이다. 그 후 이 동적 할당된 Node들의 private을 초기화 해주는데, 최소경로를 저장할 int형 포인터는 그래프의 크기만큼 배열로 동적 할당 해주고, double형 변수로 선언한 비용은 -1로 초기화 해준다. 여기서 double형을 쓴 이유는, 배열에서 쓰인 각각의 연결비용이 int형으로 저장되어서 float형일 경우는 데이터 손실이 일어나기 때문이다. 이렇게 각각 초기화가 끝나면, 최소 비용을 구할 기준 정점을 입력 받는다. 그 입력을 받은 후에는 다음과 같은 과정이 있다.
* 정점의 저장 Node에 각각의 값을 저장한다. 비용은 0, 경로는 정점(숫자)를 스택에 넣는다.
* Loop를 통해 정점에 연결된 다른 정점 중에서 최소 비용을 가진 정점을 찾는다.
* 최소비용이 아닐 경우, 함수 내부의 스택에 넣는다.
* 위의 3과정이 끝나면, 최소 비용의 정점 1개와 나머지 정점들이 스택에 넣어져 있는 상태가 된다.
* 최소 비용의 정점에 연결되어있는, 기준 정점을 제외한 모든 정점을 스택에 넣는다.
* 최소 비용 정점의 저장 Node에 비용과 경로를 저장한다.
이렇게 연산 과정이 끝나면, 사용자가 지정한 정점과 최소비용의 다른 정점이 무엇인지 알 수 있게 되고, 이 두 정점의 인접정점들은 스택에 저장되어있다. 그 이후의 알고리즘은 다음과 같다.

참고자료

· 없음