알고리즘 기초 탐욕 알고리즘 연습문제 레포트

소개글

출판사 : 홍릉과학출판사
저자 : Richard Neapolitan
역자 : 도경구

연습문제 레포트 입니다.
윈도우 7 , visual studio 2013

목차

없음

본문내용

2. 프림 알고리즘(알고리즘 4.1)을 이용하여 다음 그래프의 최소비용 신장트리를 구하시오. 그리고 수행되는 절차를 단계별로 보이시오.

(중략)

초기 distance 행렬을 모두 1로 초기화 시킨다.
처음 정점은 v1에서 시작한다. v1에서 인접한 정점인 v2 , v4 중에 가장 짧은 거리인 v4를 택하고, distance 행렬을 v1에서 v4를 거쳐 가는 거리와 v1에서 곧바로 가는 거리 중 최솟값으로 갱신 시킨다. 그렇게 생신된 정점에서의 거리가 가리가 가장 낮은 정점을 택하여 위의 방식을 반복한다. 그렇게 해서 얻어진 경로는 아래와 같다.

(중략)

3. 다음 배열을 보고 아래 물음에 답하시오.

(중략)

책에 나와 있는 배열에서 2번의 행과 2번의 열의 입력과정에서 (2,2) 성분에 0을 넣지 않고 2번 열을 입력 했다고 판단되어 나름대로 오류를 수정하여 시행하였다.

(a) 마디 v4 에서 시작하여 프림 알고리즘을 적용하여 위 배열이 표현하는 그래프의 최소비용 신장 트리를 찾으시오.

참고 자료

없음