*훈* 스토어

*훈*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

3개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

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

데이터 구조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에 비용과 경로를 저장한다.이렇게 연산 과정이 끝나면, 사용자가 지정한 정점과 최소비용의 다른 정점이 무엇인지 알 수 있게 되고, 이 두 정점의 인접정점들은 스택에 저장되어있다. 그 이후의 알고리즘은 다음과 같다.* 스택에서 한 정점을 pop한다. (스택은 지금까지 구해진 최소비용덩어리의 인접정점들이다.).* pop한 정점과, 지금까지 구해진 최소비용의 정점들에 대해 연결이 있는지 찾는다. 최소 1개의연결이 있다. 애초에 저장하는 조건이 연결이 있을시 저장하는 것이기 때문이다. 찾은 연결 중에서 최소의 비용을 가진 연결을 찾는다.* pop한 정점의 저장 Node의 ‘경로’ 부분에 찾은 정점의 저장 Node의 ‘경로’를 복사한다. 그후 복사한 경로 최상위에 pop한 정점을 적는다. 이렇게 하면, 최소경로가 완성된다. 그런 식으로 비용도 저장한다.* 마지막으로 pop한 정점에 인접한 정점들을 스택에 넣는다. 단 이미 최소비용덩어리의 정점이라면 넣지 않는다.* 스택이 빌 때까지 위 과정을 반복한다.이 알고리즘을 좀 더 알기 쉽게 설명하면 다음과 같다. 최소경로가 구해진 정점이 있고, 그 정점들의 인접한 정점이 있다. 인접한 정점에서 하나를 뽑아 최소경로를 구하고, 뽑은 정점의 인접 정점들을 인접한 정점들의 리스트에 추가를 한다. 이런 식으로 계속 연산을 하다가, 인접한 정점이 없으면 작동이 멈추는 것이다.3) 최소비용의 출력최소 비용의 출력은 연산자 오버로딩을 이용한다. 최소 경로와 비용이 저장 Node를 저장 되어 있기 때문에 loop를 돌며 해당하는 값을 출력한다. 단 비용이 초기값 -1인 경우 기준 정점과 연결이 되지 않은 경우 이므로, 무한대 표시를 해준다3. 문제 해결main.cpp#include #include "path.h"#include "Node.h"using namespace std;void main(){path ex1;// 객체의선언cin >> ex1;// 그래프의입력ex1.ShortPath();// 경로의탐색cout < ex1;// 경로의출력}Node.h#include >(istream &,path &);friend ostream &operator (istream &,path &);friend ostream &operator (istream &is,path &h){char more;int i,k,j,tail,head,waste;cout < "정점의계수를입력하세요: ";cin >> i;h.size = i;// 정점의사이즈를클레스에저장h.matrix = new int*[i];// 인접행렬의동적할당for(k=0;k

공학/기술| 2011.09.30| 11페이지| 1,500원| 조회(1,469)

데이터, 구조, 이진트리, 데이터구조, 최단거리, 최단거리 탐색, 최단거리 검색

미리보기

닫기