반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- priority queue
- 강한 연결 요소
- 플로이드 위셜
- prim
- numpy
- python
- Strongly Sonnected Coponent
- algorithm
- 유니온 파인드
- graph
- tree
- 벨만 포드
- 최장 공통 부분 수열
- 우선순위 큐
- 최소 스패닝 트리
- 트리
- 우선 순위 큐
- 크루스칼
- 다이나믹 프로그래밍
- 최소 신장 트리
- minimum spanning tree
- traceback
- 최단 경로
- Longest Common Subsequence
- 그래프
- 알고리즘
- 넘파이
- LCS
- 최단 거리
- 파이썬
Archives
- Today
- Total
목록union find (1)
codinging

Union Find 유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다. 집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다. union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다. 설명 6개의 노드로 union find 의 예시를 들어보겠다. 부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다. 1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다. 먼저 위의 예시는 잘못된 예시이다. 만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다. 모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노..
Algorithm
2023. 5. 6. 17:16