[알고리즘 스터디 with 케이시] 최소 신장 트리

Tags: 알고리즘
등록일: 2022.08.03
블로그 포스팅 여부: Not started
작성소요시간: 0:30
학습일: 2022.08.03

정의

• 필요한 간선 이외에는 전부 제거한다!
• 신장 트리(Spanning tree) 란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프다.
• 여기서 최소 신장 트리(MST)는 다음과 같은 조건을 만족한다.
  • 최소한의 간선으로 모든 정점이 연결되어야 한다.
  • 모든 신장 트리 중 가중치의 값이 최소여야 한다.
  • Cycle이 발생해서는 안된다.
• 최소 신장 트리를 위한 알고리즘은 대표적으로 두 가지가 있다.
  • 크루스칼(Kruskal)
  • 프림(Prim)

크루스칼 알고리즘

• 그리디 개념을 이용하여 구현할 수 있다.
• 먼저 모든 그래프를 부분 집합으로 분리한다.
• 가장 가중치가 낮은 간선을 선택하고 부분 집합을 연결한다.
• 이 때, Cycle이 발생하지 않도록 주의한다.
  • 공통 최상위 부모를 찾는 것으로 막을 수 있다.
  • Cycle을 판단하기 위한 알고리즘으로 Union-Find 알고리즘을 이용할 수 있다.

Union-Find 알고리즘

• 서로소 집합을 구하기 위한 알고리즘
  • 서로소 집합은 공통 원소가 없는 두 집합을 표현하기 위한 자료구조
• 서로 다른 두 집합을 병합하는 연산 Union 과
  집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산 Find를 나타낸다.
  • 이런 일을 해주는 데이터 셋이라 생각
• 보통 트리 구조로 구성한다.
• 부모를 계속해서 찾아야하기 때문에 편의상 재귀로 구현하는 경우가 많다.

Union

• 유니온 연산은 앞서 말씀드린 것 처럼 두 원소를 하나의 집합으로 합쳐주는 작업을 합니다.
• 이를 위해 일단 각 원소 자기 자신은 자기 사진이 속한 집합이라고 가정합니다.
• 여기서 key는 원소, value는 자신이 속한 집합의 부모 정점이라고 보시면됩니다.

• 첫 번째 사례를 들어보겠습니다 만약 B가 A에 속할 경우 화면과 같이 B의 부모 원소를 바꿔줍니다.
• 이렇게되면 두 원소는 같은 집합이 됩니다.

• D가 B에 속할경우 D의 부모를 B의 부모인 A로 지정합니다.
• 즉 집합의 최상위 원소를 부모로 지정한다는 뜻입니다.
• 이제 D도 한 집합에 소속되었습니다.

• E가 C에 속할 경우 첫 사례와 같습니다. 그대로 E의 부모가 C가 됩니다.

• E가 B에도 속할 경우에는 E의 부모를 그대로 B로 바꿔주는 것이 아닌
• C-E가 속한 집합의 최상위 원소인 C의 부모를 A,B D가 속한 집합의 최상위 원소인 A로 지정*합니다.
• 이런식으로 두 집합을 하나의 집합으로 합쳐줄 수 있습니다.

• 각 원소의 최상위 집합을 보기 때문에 어디 집합에 속하는지 알 수 없다.
• 그래서 Find를 준비했습니다.

Find

• 파인드 연산의 가장 간단한 방법은 부모 원소가 자기 자신일 때까지 올라가는 방법입니다.
• 예를 들어 E가 소속된 집합의 최상위 원소를 찾을 때 C를 거쳐 A를 보면 최상위 원소를 알 수 있습니다.
• 만약 다른 원소와 같은 집합인지 알기 위해선 두 원소의 최상위 원소가 같은지 보면 됩니다.

• 그래서 경로 압축이라는 최적화를 준비했습니다.

경로 압축

• 경로 압축은 간단한 아이디어입니다. 우리가 최종 공통 부모찾을 때 결국 모든 경로를 탐색하게 되는데요.

• 여기서 만약 재귀로 구현했다면 돌아오면서 해당 원소의 부모 값을 최상위 부모로 변경해주면 됩니다.

• 그러면 자연스럽게 경로가 최적화됩니다. 이렇게 최적화되면 거의 상수시간만에 공통 부모를 찾을 수 있게 됩니다.

Kruskal

드디어 크루스칼 알고리즘입니다 ㅠㅠ

• 먼저 크루스칼 알고리즘을 시작하기 전에 데이터를 화면과같이 간선과 서로소 집합으로 구성합니다

• 여기서 우리는 탐욕적으로 탐색을 할것이기 때문에 간선들 가중치를 기준으로 정렬해줍니다.

• 이렇게 구성하고나면 본격적으로 크루스칼 알고리즘이 시작됩니다.
• 먼저 가장 가중치가 낮은 간선을 선택하고 두 정점을 한 집합으로 이어줍니다.
• 그러면 화면과같이 집합이 구성됩니다.

• 다음으로 가중치가 낮은 간선인 A-B 간선을 선택하고 두 정점을 이어줍니다.
• 그럼 A,B,D가 한 집합이 됩니다.

• 이번엔 BC 간선을 선택합니다.
• 마찬가지로 두 집합을 이어줍니다

• 이번에도 아까와 같습니다. BF 간선을 선택하고 두 집합을 합쳐줍니다

• 이번에는 조금 다른데요, AC 간선을 선택하고 두 정점을 합쳐주려하지만 사이클이 발생하는 구조입니다.
• 여기서 두 정점 집합의 최상위 원소가 같다면 이미 같은 집합에 소속되어있다는 뜻이기 때문에 cycle이 발생합니다.
  • 따라서 해당 간선은 패스합니다.

• 이번엔 FG간선을 선택합니다.
• 이번엔 사이클이 발생하지 않기 때문에 합쳐줍니다.

• 이어서 DE 간선을 선택합니다.
• 여기까지오면 모든 정점이 한 집합으로 구성되었다는 것을 알 수 있습니다.

• 그래도 진행을 해보자면 EF 간선은 사이클이 발생하게 됩니다.

• 마찬가지로 CF 간선도 패스합니다

• 이렇게 패스한 간선을 모두 제거하면, 최소 신장 트리를 만들 수 있습니다.
• 크루스칼 알고리즘을 이용해 최소 신장 트리를 만들 수 있습니다.

정리

• 가장 가중치가 낮은 간선부터 선택하는 것 = Greedy
• 각 원소가 같은 집합인지 확인하기 위한 알고리즘 = Union-Find
• 두 정점이 같은 집합에 속한다면 = Cycle

출처

케이시 - 강의 (이선협 마스터)