MST (4) 썸네일형 리스트형 128. Borůvka's Algorithm 보르부카 알고리즘(Borůka's Algorithm) 또는 솔린 알고리즘(Sollin's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 세 번째 알고리즘이며 다음과 같이 작동한다. 1. 각각의 컴포넌트에 연결된 간선들 중 가중치가 가장 작은 간선을 하나씩 선택한다. 2. 간선을 차례로 최소 스패닝 트리에 추가하는데, 간선이 연결하는 두 정점이 이미 같은 컴포넌트에 존재한다면 추가하지 않는다. 3. 컴포넌트가 하나로 줄어들 때까지 1번과 2번 과정을 반복한다. 이번에도 설명이 짧게 끝났다. 다시 예시를 가지고 살펴보자.처음에는 정점들이 모두 다른 컴포넌트에 존재하므로, 각 정점과 연결된 간선들 중 가중치가 가장 작은 것 하나를 모두 고른다.$\text{A}: \text{D}.. 127. Prim's Algorithm 프림 알고리즘(Prim's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 두 번째 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 그래프에서 정점 하나를 임의로 골라서 $v$라고 한다. 2. 연결하는 한쪽 정점이 $v$와 연결된 정점들의 집합에 포함되고 다른 정점은 집합에 포함되지 않는 간선들 중 가중치가 가장 작은 간선 하나를 선택하고 최소 스패닝 트리에 추가한다. 3. 모든 정점이 $v$와 연결될 때까지 2번 과정을 반복한다. 이것도 설명이 짧아서 예시를 같이 살펴보면 편할 것이다. 앞에서 나온 그래프에서 정점 $\text{H}$가 $v$로 선택되었다면 다음과 같이 스패닝 트리가 만들어지게 된다.먼저 정점 $\text{H}$와 연결된 간선 중 가중치가 가장 작은 간.. 126. Kruskal's Algorithm 크루스칼 알고리즘(Kruskal's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 알고리즘 중 하나로, 다음과 같은 방법으로 작동한다. 1. 확인하지 않은 간선들 중 가중치가 가장 작은 간선 하나를 고른다. 2. 현재까지의 최소 스패닝 트리에서 선택한 간선이 연결하는 두 정점이 연결되어 있지 않다면, 이 간선을 최소 스패닝 트리에 추가한다. 3. 모든 간선을 확인했다면 종료한다. 그렇지 않다면 1번으로 돌아간다. 설명이 매우 간단하게 끝난다. 예시를 통해서 자세히 살펴보자.앞에서 나온 그래프이다. 여기서 가중치가 작은 간선들부터 하나씩 확인하면서 최소 스패닝 트리를 만든다. 먼저 가중치가 $2$인 간선들이 최소 스패닝 트리에 추가된다.다음으로 가중치가 $3$인 간선을 확인.. 125. Minimum Spanning Tree 무향 연결 그래프의 스패닝 트리(신장 트리, Spanning Tree)는 그래프의 모든 정점을 포함하는 트리이다. 쉽게 말해서 그래프에서 (그래프가 분리되지 않도록) 간선들을 제거해서 트리 구조가 남았을 때 이를 스패닝 트리라고 한다. 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있다. 간선에 가중치가 있는 그래프는 스패닝 트리에 포함되는 간선의 가중치의 합이 다양하게 나올 수 있는데, 이중 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리(최소 신장 트리, Minimum Spanning Tree, MST)라고 한다. 이 최소 스패닝 트리가 꽤 다양한 곳에서 사용되므로 알아 두면 좋다. 무향 연결 그래프에서 최소 스패닝 트리를 구하는 방법은 여러 가지가 있는데, 이 블로그에서는 세 가지를 .. 이전 1 다음
