서로소 집합 / 최소 신장 트리

wonjoogu·2021년 3월 18일
0

SSAFY TIL

목록 보기
4/18

서로소 집합(Disjoint-set)

  • 상호배타 집합(겹치지 않는), 교집합x, == 유니온 파인드, 유니크한 식별자를 대표자라고 한다.

  • 서로소 집한 표현 방법 : 연결 리스트, 트리

  • 서로소 집합 연산 : Make-Set(단위 연산), Find-Set(x가 속한 집합을 찾는 것, 자신이 속해있는 집합의 대표자를 리턴한다.), Union(두 구성 요소를 주면 얘네들이 속한 집합을 합쳐주는 것, 내부적으론 find연산이 동반되어있다.)

  • 연결리스트 : 같은 집합의 원소들은 하나의 연결 리스트로 관리, 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 갖는다. 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

  • Make-Set(a)~Make-Set(f) : 전처리 연산 느낌, 단위 집합, 크기가 1인 집합 따라서 교집합이 있을 수 없음

  • 연산의 효율을 높이는 방법
    :Rank를 이용한 Union
    :Path compression

최소 신장 트리(MST)

  • 그래프에서 최소 비용 문제
    : 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
    : 두 정점 사이의 최소 비용 경로 찾기

  • 신장 트리
    : n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리

  • KRUSKAL 알고리즘
    : 간선을 하나씩 선택해서 MST를 찾는 알고리즘

PRIM 알고리즘

  • 대표적인 그리디 알고리즘 중 하나
  • 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

***** 꿀팁 ******
간적쿠 : 간선이 적으면 크루스칼 (행렬이 아닌 리스트로 많이 푼다 Priority Queue), PQ + UnionSet = Kruskal
간만프 : 간선이 많으면 프림( V - 1 )

profile
SSAFY 5th

0개의 댓글