알고리즘 4장 탐욕적 방법 연습문제

소개글

"알고리즘 4장 탐욕적 방법 연습문제"에 대한 내용입니다.

목차

없음

본문내용

2. 프림 알고리즘(알고리즘 4.1)을 이용하여 다음 그래프의 최소비용 신장트리를 구하시오. 그리고 수행되는 절차를 단계별로 보이시오.
v1에서 시작하여 최소비용 신장트리를 구해보면 distacne[] 는 아래의 표와 같다.
선택된 정점을 S라는 배열에 넣어주면 처음은 S = {v1} 이라고 표시할 수 있다.
1) S = {v1} 에서 가장 가중치가 적은 정점 v4를 택한다.

<중 략>

10. 컴퓨터 네트워크에서 어떤 두 컴퓨터도 서로 연결될 수 있다고 가정하자. 각 링크간의 추정 비용이 주어진 상태에서 알고리즘 4.1(프림 알고리즘)을 사용할지, 아니면 알고리즘 4.2(크루스칼 알고리즘)를 사용할 지를 판정하시오. 그리고 왜 그런 답이 나오는 지를 설명하시오.
정점의 개수가 n, 이음선의 개수가 m 이라고 하면 n-1<= m<= n(n-1)/2 이 성립한다.
프림 알고리즘과 크루스칼 알고리즘을 비교하면 프림 알고리즘은 시간복잡도가 Θ(n^2) 이고 크루스칼 알고리즘은 시간복잡도가 Θ(m logm) 이거나 Θ(n^2 logn) 이다.
그래프에서 연결선의 개수가 드문 경우(저밀도 그래프일 경우)에는 프림 알고리즘은 시간복잡도가 Θ(n^2), 크루스칼 알고리즘은 시간복잡도가 Θ(n logn) 이므로 크루스칼 알고리즘이 유리하다.
그래프에서 연결선의 개수가 밀집되어 있을 경우(고밀도 그래프일 경우)에는 프림 알고리즘은 시간복잡도가 Θ(n^2), 크루스칼 알고리즘은 Θ(n^2 logn) 이므로 프림 알고리즘이 유리하다.

12. 다익스트라 알고리즘(알고리즘 4.3)을 사용하여 연습문제 3의 배열이 나타내는 그래프에서 마디 에서 다른 모든 마디로 가는 최단경로를 구하시오. 그리고 수행되는 절차를 단계별로 보이시오.
처음 시작 정점이 v5이기 때문에 최단경로 S={5} 라고 표시한다. distance[]를 아래와 같은 표로 작성하고 가장 가중치가 적은 순서대로 정점을 택한다.

참고 자료

없음