spanning tree(스패닝 트리 알고리즘)

소개글

□ 문제개요

○ 사용자로부터 vertex의 개수와 weight(가중치) 를 입력 받아 트리를 구성한다.
○ 완성된 트리에서 가장 최소의 가중치를 갖는 루트를 찾아낸다.
○ 위의 과정으로 신장트리(spanning tree)를 도출 해 낸다.

컴파일 실행환경

- 문제의 개요
- 문제 분석 및 알고리즘
- 소스 및 주석
- 실행 화면 CAPTURE
- 느낀점

본문내용

□ 분석 및 알고리즘

○ 문제분석
- 다음의 함수들을 사용한다.
a. void input() : 사용자로부터 vertex 개수와 가중치를 입력 받아 트리를 구성한다.
b. void seek_route() : 다음의 가장 최소 가중치로이어지는 vertex를 찾는다.
c. void compare_before() : 지나온 vertex에서 또다른 최소 가중치를 찾아 위의 vertex와 가중치를
비교하여 가장 최소 vertex를 찾는다.
d. void print_route() : 가장 최소의 가중치로 이어지는 vertex들로 spanning tree 를 출력한다.

○ 알고리즘
- matrix를 이용하여 가중치 값을 저장한다. (1～99까지로 값을 한정한다.)
a. matrix 1행 2열의 값은 1에서 2로 이어지는 edge의 가중치값이다.
b. 가중치가 100이면 vertex간의 edge가 존재하지 않는 것이다.
c. 자기 자신으로 가는 self edge의 가중치는 0이므로 행과 열이 같으면 무조건 0값을 갖는다.
d. 이 행렬은 대각선을 중심으로 거울에 반사된 것 같은 똑같은 데이터 값을 같게된다.
- spanning tree를 찾아내는 알고리즘

a. 특정 vertex에서 시작해서 인근의 vertex중 가중치가 가장 적은 곳을 향한다.
b. 스타트 지점과 위에서 선택한 vertex에서 인접한 vertex의 가중치가 가장 적은 곳을 향한다.
c. 역시 새로 향한 vertex와 지금까지 지나온 vertex에서 인접한 vertex의 가중치가 가장 적은 곳을 향한다.
d. 이와 같이 계속 반복하다가 똑같은 vertex를 지나게 된다거나, vertex-1 만큼 looping 을 마쳤음에도
edge의 수가 vertex-1의 개수보다 적다면 spanning tree가 존재하지 않는 것이다.

- 결과 스냅샷으로 사용한 트리


- 위의 트리를 만들기 위해 user가 입력 한 행렬은 다음과 같다.
.. 이하 생략..

압축파일 내 파일목록

main.cpp
prim.h
spanning tree.hwp

참고 자료

없음