11-1 최소 신장 트리

1. 최소 신장 트리

① 신장 트리의 조건

  - 모든 정점을 포함

  - 모든 정점은 직,간접적으로 연결되어야 함.

  - 트리의 속성 만족해야 함.

 

② 최소 신장 트리

  - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리.

  - 프림 알고리즘, 크루스칼 알고리즘이 대표적

  - 신장 트리의 비용을 최소로 만드는 것은 실제 응용 분야에서

    경제성이나 효율성 등을 고려할 때 매우 중요한 문제.

  - 본사와 각 지역에 있는 지점의 통신 네트워크를 구성하고자 할 때 네트워크를

    어떤 방법으로 구성하느냐에 따라 통신 비용이 달라질 수 있음.

  - 정의 : 그래프 G의 모든 변의 가중치 합을 총 가중치라고 했을 때,

               G의 신장 트리 중 총 가중치가 가장 작은 신장 트리를 최소 신장 트리라고 함.

 

2. 크루스칼 알고리즘

① 크루스칼 알고리즘

  - 사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소 신장 트리를 만듦.

  - 이 간선과 연결되어 있지 않은 간선이라도 가중치가 가장 작은 간선을 순서대로 신장 트리에 추가

 

3. 프림 알고리즘

① 프림 알고리즘 

  - 정점 하나를 기준으로 삼아 연결된 다른 정점으로 갈 때 가장 적은 비용이 드는 정점과 간선으로

     이어주며 진행해 나가는 알고리즘

  - 첫번째로 이어진 간선에 의한 정점들과 연결된 모든 간선들 중 가중치가 가장 작은 간선 선택

  - 프림 알고리즘과 크루스칼 알고리즘을 통해서 서로 다른 최소 신장 트리가 만들어질 수 있지만,

    가중치의 합은 둘 다 동일한 최소의 값을 가진다.

  - n개의 정점에 대하여 n-1개의 간선이 연결되면 종료