ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • CS : Algorithm : 최소 비용 신장 트리(MST)
    Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:51
    728x90

    Spanning Tree (스패닝 트리, 신장 트리)

     

     

    1.

    그래프 내의 모든 정점을 포함하는 트리

     

    2.

    최소 연결 = 간선의 수가 가장 적다.

    n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)이고, (n-1)개의 간선으로 연결된 그래프는 필연적으로 스패닝 트리가 된다.

     

    3.

    하나의 그래프에는 많은 스패닝 트리가 있다.

     

     

     


     

     

    MST (Minimum Spanning Tree)

     

     

    1.

    spaniing tree 중, 간선의 가중치의 합이 최소인 트리

     

    2.

    n개의 정점을 가지는 그래프에 대해서, 반드시 (n-1)개의 간선만 이용해야 한다.

     

    3.

    구현 종류

    • Kruskal MST 알고리즘
    • Prim MST 알고리즘

     

     


     

    Kruskal MST 알고리즘

     

    1.

    greedy method를 활용하여 모든 정점을 최소의 가중치로 연결하는 방법을 찾는 알고리즘

     

    2.

    • 그래프의 간선들의 가중치를 기준으로 오름차순 정렬한다.
    • 가중치를 선택해 나아가는데, 이 때 사이클이 형성되지 않는 가장 낮은 가중치를 선택한다.
    • 반복

     

    3.

    간선 선택을 기반으로 하는 알고리즘이다.

    즉, 이전 단계에서 만든 신장 트리와는 관계 없이, 현 단계에서 무조건 최소의 가중치가 되는 간선을 선택한다.

     

     

     

     


     

     

    Prim MST 알고리즘

     

    1.

    시작 정점으로부터, 신장 트리 집합을 단계적으로 확장해나가는 방법

     

    2.

    정점 선택을 기반으로 하는 알고리즘이다.

    즉, 이전 단계에서 만든 신장 트리를 기준을 확장하는 방법

     

     

     

     

     


     

     

    Kruskal과 Prim 비교

     

    1.

    Kruskal의 시간 복잡도 : O(n^2)

     

    2.

    Prim의 시간 복잡도 : O(elog2e)

     

    3.

    간선이 적은 그래프의 경우, Kruskal이 유리하고,

    간선이 많은 그래프의 경우, Prim이 유리하다.

     

     

    728x90

    'Computer Science > Algorithm, Data Structure' 카테고리의 다른 글

    Question : Data Structure  (0) 2021.04.15
    CS : Algorithm : 최단 경로  (0) 2021.04.15
    CS : Data Structure : Tree & Graph  (0) 2021.04.15
    CS : Data Structure : Heap  (0) 2021.04.15
    CS : Data Structure : Stack & Queue  (0) 2021.04.15

    댓글

kxmjhwn@gmail.com