열혈 자료구조 - 14.4 최소 비용 신장 트리

사이클의 이해

- 단순 경로 : 정점에서 정점으로 이동하는 경로

    -> 중복 간선을 포함하지 않음

- 사이클 : 시작점과 끝점이 같은 단순 경로

    -> 사이클이 형성되면 폐구간이 만들어짐

- 사이클을 형성하지 않는 그래프를 신장 트리라고 부름

- 사이클을 형성하지 않는 그래프를 회전시키면 트리 형태가 나오기 때문에 신장 그래프가 아닌 신장 트리라고 부름

 

 

최소 비용 신장 트리

- 최소의 비용으로 모든 정점들을 탐색할 수 있는 트리

- 최소 비용 신장 트리를 만드는 알고리즘은 크루스칼 알고리즘이 있음

 

 

크루스칼 알고리즘

- 가중치를 기준으로 간선을 정렬한 후 최소 비용 신장트리가 될 때 까지 간선을 하나씩 선택 또는 삭제하는 방법

- 크루스칼 알고리즘은 2가지 방식이 존재

- 크루스칼 알고리즘(1)

    -> 간선의 가중치를 오름차순으로 정렬

    -> 오름차순 순서대로 간선을 연결(추가)

    -> 추가할 때 간선이 사이클을 형성하거나 신장 트리가 완성되었다면 추가하지 않음

    -> 7의 간선을 추가할 차례이지만 7을 추가하면 사이클이 형성되므로 추가하지 않음

    -> 8의 간선을 추가하면 최소 비용 신장 트리가 완성되므로 더이상 진행하지 않음

    -> 최소 비용 신장 트리가 완성됐는지 확인하는 방법은 '간선의 수 + 1 = 정점의 수'가 됐다면 완성됐다고 판단

- 크루스칼 알고리즘(2)

    -> 간선의 가중치를 내림차순으로 정렬

    -> 내림차순 순서대로 간선을 삭제

    -> 삭제할 때 정점이 독립되거나(연결된 간선이 없음) 신장 트리가 완성되었다면 삭제하지 않음

    -> 13부터 9까지 간선을 지우고 8의 간선을 지울 차례이지만 지울 경우 정점 A가 독립적이게 되므로 지우지 않고 넘어감

    -> 7을 지울경우 최소 비용 신장 트리가 완성('간선의 수 + 1 = 정점의 수')