12.최소 신장 트리 (Minimum Spanning Tree)

Q. 그래프의 최소 신장 트리 (Minimum Spanning Tree) 알고리즘 중 프림 (Prim) 알고리즘과 크루스칼 (Kruskal) 알고리즘의 차이점과 사용 사례에 대해 설명해 주세요

A. 프림 알고리즘 (정점에 focus)

-임의의 정점(Node)에서 시작

-현재 트리에서 가장 가중치가 낮은 길을 따라 확장

-모든 정점(노드)이 트리에 포함될때까지 반복 (또는 N-1간선)

A. 크루스칼 알고리즘 (간선 focus)

-가장 가중치 낮은 간선부터 순서대로 트리에 넣음

-사이클 발생시 하나 건너띈다

-모든 정점이 트리에 포함될 때까지 반복

 

 

 

 

 

•임의의 Undirected 그래프에서, 모든 Vertex를 최소한의 Edge를 사용해 연결하는 것

•이때 Cycle이 있으면 안됨 (특정 지점에서 시작해서, 길을 따라가다 보니 시작 지점으로 돌아왔다 -> Cycle)

•이때 N개의 Vertex가 있다면, 임의의 신장 트리(= 최소연결트리) 는 N – 1개의 Edge를 사용했을 것

•DFS, BFS 등으로 모든 Vertex(정점,노드)를 탐색하고, 그 도중에 사용된 Edge(간선)만 모으면 만들 수 있음

•신장 트리는 통신망, 도로망 구축 등에 유용함

아래그림) 

신장 트리들 중에서, 사용된 Edge들의 가중치 합이 최소인 트리를 최소 신장 트리라고 함

 

 

 

크루스칼 알고리즘이란?

1.주어진 그래프의 Edge들을 가중치의 오름차순으로 정렬한다 (가중치가 낮은 Edge가 처음에 온다)

2.정렬된 Edge들에서, 순서대로 Cycle을 형성하지 않는 Edge들을 선택한다 (신장 트리에 포함시킨다)

3.2번 동작을 모든 Vertex가 신장 트리에 포함될 때까지 반복한다

 

cf) 신장트리 -- 가중치가 없음  -> 최소신장트리: 가중치 합이 제일 작음 -> 크루스칼 알고리즘

 

프림 알고리즘이란?

1.시작 Vertex를 신장 트리에 포함시킨다

2.현재 신장 트리에 포함된 Vertex들에 인접한 Vertex들 중에서, 가장 낮은 가중치로 연결된 Vertex를 신장 트리에 포함시킨다

3.2번 작업을 모든 Vertex가 신장 트리에 포함될 때까지 반복한다

 

 

크루스칼 알고리즘  - 간선의 영향받음

•크루스칼 알고리즘은 먼저 모든 Edge를 가중치 순으로 정렬해야 한다 (시간 복잡도에 가장 큰 영향)

•Edge의 수를 E라 할때, 효율적인 정렬 알고리즘을 사용하면, 정렬의 시간 복잡도는 O(E log E)가 된다 

 

 

프림 알고리즘 - 노드영향받음

•프림 알고리즘에서는 (Vertex의 수를 V라 할때)

1.하나씩 모든 Vertex를 신장 트리에 포함시킴 (총 V번 반복)

2.각 단계마다 모든 Vertex를 검색해서 가장 낮은 가중치로 연결된 Vertex 찾기 (총 V번 반복)

•따라서 시간 복잡도는 O(V^2) 가 된다

 

•크루스칼 알고리즘의 시간 복잡도 = O(E log E)

•프림 알고리즘의 복잡도 = O(V^2) 가 된다

 

•만약 V가 크다면 (희소 그래프) 크루스칼이 유리

•V작으면 (밀집 그래프) 프림 알고리즘이 유리