별의 공부 블로그 🧑🏻‍💻

🗒️ disjoint-set (2)

728x90
  1. 2021.06.26 [C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합

    디스조인트-셋(Disjoint-Set) 디스조인트-셋(Disjoint-Set) 또는 유니언-파인드(Union-Find) 자료구조 다음과 같이 불림. 서로소 집합 자료구조 상호 배타적 집합 자료구조 트리 형태로 구성된 포레스트(Forest) 각각의 원소는 숫자 ID 에 의해 표현됨. 랭크(Rank) 와 부모에 의한 포인터를 가짐. 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성됨. 각각의 원소는 하나의 트리를 나타냄. 공통의 원소를 갖지 않는 원소 집합을 표현하기 위해 사용됨. 지원 연산 make-set(x) x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가함. 새로 추가한 원소의 랭크 : 0 원소의 부모 포인터는 자기 자신을 가리키도록 설정함. 그림 설명 원 안에 적힌 숫자 : 원소 ID 괄호 ..

  2. 2021.06.26 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm)

    크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 최소 신장 트리(Minimum Spanning Tree) 정점(Vertex) 의 집합 V와 가중치를 갖는 에지(Edge) 의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소 인 트리 T 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 1956년에 발표됨. 알고리즘 ① 그래프 G의 모든 에지를 최소 힙 H에 추가함. ② H로부터 에지 e를 하나 꺼냄. e : 모든 에지 중에서 가장 가중치가 작은 에지 ③ e이 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있음...

728x90

티스토리툴바