최소 신장 트리

크루스칼 알고리즘 크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 최소 신장 트리를 구하는 방법 중 하나입니다. MST는 간선 가중치의 합이 최소, 사이클이 발생하지 않는다는 특징을 이용하여, 그래프의 전체 간선 중에서 사이클이 발생하지 않으며 가중치가 가장 작은 간선을 선택하며 MST를 완성합니다. 그래프의 간선을 가중치 오름차순으로 정렬합니다. 정렬된 순서대로 하나씩 해당 간선이 사이클을 발생하시키는지 확인합니다. 사이클이 발생하지 않는다면 MST 간선 집합에 해당 간선을 추가합니다. 2, 3번의 과정을 간선의 개수가 n-1이 될 때까지 반복합니다. 구현 방법 간선을 이루는 두 노드가 이미 같은 집합이라면 해당 간선을 MST 간선 집합에 추가했을 때 사이클이 발생합니다. 0-4 간선 선택 예시) { 0..

프림 알고리즘 프림 알고리즘은 최소 신장 트리를 구하는 방법 중 하나입니다. 하나의 정점을 시작으로 MST 정점 집합을 점차 넓혀가는 방법입니다. 시작 정점을 집합에 추가합니다. 집합 내부의 정점들과 인접한 정점들 중 간선의 가중치가 최소로 연결된 정점을 집합에 추가합니다. 집합 내부의 정점 개수가 n개가 될 때가지 2번의 과정을 반복합니다. 구현 방법 집합에 포함된 정점들과 인접한 간선들 중 최소 가중치를 가지는 간선을 효과적으로 찾기 위해서는 우선순위 큐를 활용하는 것이 좋습니다. 만약 일반 배열을 사용한다면 매번 간선들의 최소 값을 찾기 위해 $n^2$의 시간을 사용하게 됩니다. 1) 초기 상태 시작 정점을 0번으로 하기 때문에 우선순위 큐에는 (0, 0)을 삽입합니다. 2) (0, 0) 추출 0번..

신장 트리 신장트리(Spanngin Tree) 란, 무방향 그래프에서 그래프 내의 모든 정점을 포함하며, 최소한의 간선 개수만을 가지는 서브 그래프입니다. 최소한의 간선만을 사용해야 하므로 사이클이 발생하면 안되고, 놓치는 정점이 발생하면 안됩니다. 이는 이름에서도 알 수 있듯이 트리의 형태입니다. 따라서 간선의 개수는 (정점의 개수 - 1) 입니다. 정점의 개수가 N개라면 신장트리의 간선 개수는 N-1 이 됩니다. 최소 신장 트리 (MST) 하나의 그래프에서 여러개의 신장트리가 만들어 질 수 있습니다. 이 중에서 각 간선의 가중치 합이 최소가 되는 신장트리가 최소 신장 트리(MST) 입니다. MST는 다음과 같은 특징을 가집니다. 사이클이 존재하지 않는다. n개의 정점을 가지는 그래프에서 항상 n-1 ..