최소 스패닝 트리(Minimum Spanning Tree)

스패닝 트리(Spanning Tree)는 그래프에서 모든 정점을 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 그래프 내에서 가장 작은 비용을 가지는 간선을 선택하고, 이어진 정점을 그래프에서 제외하여 생성된다. 스패닝 트리는 그래프 내에서 여러 개를 가질 수 있으며, 최소 스패닝 트리(Minimum Spanning Tree)는 스패닝 트리 중에서 가장 작은 가중치의 합을 가지는 스패닝 트리를 의미한다.

스패닝 트리는 다음과 같은 분야에서 널리 사용된다.

• 네트워크 설계
• 전기 회로
• 라우팅 등의 문제

그럼 최소 스패닝 트리 생성에 사용되는 알고리즘은 어떤 것이 있을까요?

다익스트라 알고리즘

다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로, 시작 정점에서부터 각 정점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 음의 가중치를 가지는 간선이 없는 그래프에서 사용할 수 있다.

다익스트라 알고리즘의 동작 방식

1. 출발 노드를 설정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
5. 3번과 4번의 과정을 반복한다.

다익스트라 알고리즘은 최소 스패닝 트리를 생성하는데에도 사용될 수 있다.

프림 알고리즘

프림 알고리즘의 동작 방식

1. 임의의 정점을 선택하고, 해당 정점에 연결된 간선들을 간선 리스트에 삽입한다.
2. 간선 리스트에서 최소 가중치를 가지는 간선을 선택한다.
3. 해당 간선에 연결된 정점을 트리에 추가한다.
4. 추가된 정점과 연결된 간선들 중, 트리에 포함되지 않은 정점과 연결된 간선들만 간선 리스트에 삽입한다.
5. 2번부터 4번의 과정을 반복한다.

프림 알고리즘은 간선 수가 적은 밀집 그래프에서 유리하며, 다익스트라 알고리즘과 마찬가지로 최소 스패닝 트리 생성에 사용된다.

크루스칼 알고리즘

크루스칼 알고리즘의 동작 방식

1. 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 간선을 선택한다.
3. 선택한 간선이 사이클을 형성하는지 확인한다.
4. 사이클을 형성하지 않는 경우 해당 간선을 선택한다.
5. 모든 정점이 선택될 때까지 2번부터 4번의 과정을 반복한다.

크루스칼 알고리즘은 간선 수가 많은 희소 그래프에서 유리하며, 최소 스패닝 트리 생성에 사용된다.