[그래프의응용] 그래프의 응용

목차

없음

본문내용

최소경비 신장트리(MST)
그래프의 모든 노드를 연결하고 그 가중치의 합이 최소인 신장트리
<정의>: 최소경비 신장트리
가중치 그래프 G=(V, E, W)에서 경로 P=(v0, v1,..., vn)가 있는 서브 그래프의 가중치의 합
가 최소인 비싸이클 그래프를 최소경비 신장트리(MST)라 한다.
Kruskal 알고리즘
T: n 노드로 구성된 노드의 집합으로 초기에는 empty
E: 에지의 집합으로 초기에는 모든 에지를 포함
while (edge_nr(T)<n-1 and E≠ε) do
- E로부터 가중치가 최소인 에지 (v, w)∈E를 택한다.
- E=E - {v, w)
- 그리고 (v, w)가 T에서 싸이클을 이루지 않으면 T=T∪{w}
od
if (T가 n-1에지 보다 적은 에지를 갖으면)
then
printf("no spanning tree");
Prim 알고리즘
1) 그래프에서 임의의 출발 노드 x를 정한다. 그리고 다음과 같이 초기화한다.
V1={x}; // 신장트리를 구성하는 노드집합
V2={0}; // V1에 속한 노드들에 인접해 있는 후보노드 집합
V3=V-{V1}; // 아직 신장트리와 무관한 노드의 집합
E1={0}; // 신장트리를 구성하는 에지집합
E2={0}; // (V1, V2)의 관계에 놓인 후보에지로서 같은 노드에 두개의
에지가 있을 경우에는 최소 가중치를 갖는 에지로 구성.

2) while (V1≠V) do // 그래프의 모든 노드가 신장트리를 구성할 때까지
2.1) 정해진 노드로부터 신장트리를 구성할 수 있는 후보에지와 노드를 결정
2.1.1) for (x∈V1 and y∈V2: ∃(x, y)) do // 중첩 후보에지 결정
if (모든 x∈V1에 대해서 노드 y에 에지가 여러개 있으면)
- 가중치가 가장 작은 에지만 남겨두고 모든 에지를 후보에지에서 삭제한다.
E2=E2-{e}∪(x, y)
2.1.2) for (x에 인접한 노드 z∈V3에 대하여) do // 후보노드 결정
{ V2=V2∪{z};
V3=V3-{z};
E2=E2∪(x, z);

참고 자료

없음