- 크루스칼 알고리즘과 프림 알고리즘의 특성을 이해하고, 이를 이용하여 최소 신장 나무를 구할 수 있다.
- 다익스트라 알고리즘의 특성을 이해하고, 이를 이용하여 단일 출발점 최단 경로를 구할 수 있다.
- 플로이드 알고리즘의 특성을 이해하고, 이를 이용하여 모든 쌍 최단 경로를 구할 수 있다.
용어설명
- 신장나무:주어진 그래프의 모든 노드들을 포함하는 연결된 부분 그래프 중 나무인 것
- 최소 신장나무:신장 나무 중에서 간선의 가중치의 합이 가장 작은 나무
- 최단 경로(shortest path):정점 u에서 v까지의 경로 중 간선의 가중치의 합이 가장 작은 경로
- 다음은 프림(Prim)의 알고리즘으로 최소신장나무를 구하는 과정을 나타낸 것이다. 굵은 선으로 표시된 간선이 이미 선택된 간선들이라면 다음에 선택될 간선은? [2004학년도 기말시험]
- (c,f)
- (b,c)
- (a,d)
- (d,e)
정답:2
정답:2
정답:3
정답:3
정답:4
정답 : 13
그래프II
학습목표
(1) 최소 신장 나무
▶
최소 신장 나무(MST, minimum spanning tree)란 신장 나무 중에서
간선의 가중치 합이 작은 것
→ 신장 나무: 주어진 그래프의 모든 노드들을 포함하는 나무
▶
크루스칼 방법과 프림의 방법 → 두 방법 모두 욕심쟁이 방법이 적용됨
▶
크루스칼 알고리즘
→ 간선이 하나도 없는 숲에서 시작하여 사이클을 만들지 않는
최소 간선들을 하나씩 추가해 나가는 방법
→ 알고리즘에서 사이클의 존재 여부를 조사하기 위해 합-찾기 연산이
사용됨
→ 시간 복잡도 O(|E|lg|E|)
▶
프림 알고리즘
→이미 선택된 정점에 부수된 최소 간선을 추가해 나가는 방법
= 이미 선택된 정점 집합 S와 V-S를 잇는 최소의 간선을 선택해서
추가하는 방법
→ 시간 복잡도: 인접행렬 - O(|V|²), 인접리스트 - O((|V|+|E|)lg|V|)
(2) 단일 출발점 최단 경로
▶
음의 가중치를 갖는 간선이 없는 가중 그래프에서 한 출발
정점x에서 다른 모든 정점까지 가중치 합이 최소인 경로를 찾는 문제
▶
다익스트라 알고리즘
→ 욕심쟁이 방법 적용
→ 출발점에서 시작하여 거리가 최소인 정점을 선택해 나감으로
최단 경로를 구하는 방법
→ 정점 v의 거리 D[v]는 시작 정점 s로부터 현재까지 선택된 정점 집합
U를 경유하여 정점 v에 이르는 최소 경로의 길이를 의미
→ 적용 방법: ⓐ 미선택 정점 집합 V-U에서 거리 D가 최소인 정점 w를
선택ⓑ w의 인접 정점들에 대하여 w를 경유하는 거리와 기존 거리
중에서 작은 것을 새 거리값으로 조정
→ 시간 복잡도: 인접행렬- O(|V|²), 인접 리스트 - O((|E|+|V|)lg|V|)
(3) 모든 쌍 최단 경로
▶
모든 정점쌍 간의 최단 경로를 구하는 문제
(경로의 길이가 음인 사이클이 그래프에 존재하지 않는 것을 가정)
→ 단일 출발점 최단 경로를 구하는 다익스트라 알고리즘을 각 정점을
출발점으로 하여 반복적으로 적용해서 구할 수도 있다 → O(|V|³)
▶
플로이드 알고리즘
→ 동적 프로그래밍 방법 적용
→
: 정점 번호가 k 이하인 정점만을 경유하여 정점 i에서
정점 j까지의 최단 경로 길이
→ 점화식:

→ O(|V|³)
'방송대 > 알고리즘' 카테고리의 다른 글
| [알고리즘]기말정리요약 (0) | 2010/06/30 |
|---|---|
| [알고리즘]그래프II (0) | 2010/06/29 |
| [알고리즘]그래프I (0) | 2010/06/29 |
| [알고리즘]11강 기하 알고리즘II (0) | 2010/06/29 |
| [알고리즘]10강 기하 알고리즘1 (0) | 2010/06/29 |
2009-정보통신망_워크북.zip
[2005-8학년도 1학기 기말시험] 정보통신망.hwp
[2006학년도 1학기 기말시험] 정보통신망(해설.pdf