0041 데이터 구조 통합
그리고 조사 집 은 아이 가 아버 지 를 가리 키 는 특수 한 나무 이다.
연결 문제 와 경로 문 제 를 해결 하 는 데 사용:
네트워크 의 노드 연결 상 태 를 판단 합 니 다.
모든 요 소 를 하나의 노드 로 보고 a 와 b 를 하나의 집합 으로 합 칠 때 a 가 있 는 뿌리 노드 가 b 가 있 는 뿌리 노드 를 가리 키 기만 하면 된다. 두 요소 가 하나의 집합 에 있 는 지 확인 하려 면 각자 의 뿌리 노드 만 찾 아야 한다. 만약 에 두 노드 가 같은 뿌리 노드 라면 같은 집합 에 있다 는 것 을 설명 한다. 이렇게 하면 조회 가 비교적 빠르다.합병 도 빠르다.
그리고 집합 인터페이스 디자인 은 다음 과 같다.
package unionFind;
public interface UF {
int getSize();
boolean isConnected(int p, int q);
void unionElements(int p, int q);
}quik find 다음 실현:
package unionFind;
// Union-Find
public class UnionFind1 implements UF {
private int[] id; // Union-Find
public UnionFind1(int size) {
id = new int[size];
// , id[i] ,
for (int i = 0; i < size; i++)
id[i] = i;
}
@Override
public int getSize(){
return id.length;
}
// p
// O(1)
private int find(int p) {
if(p < 0 || p >= id.length)
throw new IllegalArgumentException("p is out of bound.");
return id[p];
}
// p q
// O(1)
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// p q
// O(n)
@Override
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// ,
for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
}
}quik union 은 다음 과 같이 실현 합 니 다.
package unionFind;
// Union-Find
public class UnionFind2 implements UF {
// Union-Find,
// parent[i]
private int[] parent;
//
public UnionFind2(int size){
parent = new int[size];
// , parent[i] ,
for( int i = 0 ; i < size ; i ++ )
parent[i] = i;
}
@Override
public int getSize(){
return parent.length;
}
// , p
// O(h) , h
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// ,
// : parent[p] == p
while(p != parent[p])
p = parent[p];
return p;
}
// p q
// O(h) , h
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent[pRoot] = qRoot;
}
}size 의 최적화: 높이 가 작은 나무의 뿌리 노드 가 높이 가 비교적 높 은 나무의 뿌리 노드 를 가리 키 도록 한다. 이렇게 하면 형 성 된 나무의 높이 가 너무 높 지 않 고 특정한 노드 의 뿌리 노드 를 찾 을 때 효율 도 비교적 빠르다. 만약 에 높이 판단 하지 않 으 면 최 악의 상황 은 단일 체인 표 가 형 성 될 수 있다.
package unionFind;
// Union-Find
public class UnionFind3 implements UF{
private int[] parent; // parent[i]
private int[] sz; // sz[i] i
//
public UnionFind3(int size){
parent = new int[size];
sz = new int[size];
// , parent[i] ,
for(int i = 0 ; i < size ; i ++){
parent[i] = i;
sz[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
// , p
// O(h) , h
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// ,
// : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// p q
// O(h) , h
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
//
//
if(sz[pRoot] < sz[qRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{ // sz[qRoot] <= sz[pRoot]
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}rank 기반 최적화: 깊이 가 낮은 나무 가 깊이 가 높 은 나무 로 합 쳐 집 니 다.
package unionFind;
// Union-Find
public class UnionFind4 implements UF {
private int[] rank; // rank[i] i
private int[] parent; // parent[i] i
//
public UnionFind4(int size){
rank = new int[size];
parent = new int[size];
// , parent[i] ,
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
// , p
// O(h) , h
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// ,
// : parent[p] == p
while(p != parent[p])
p = parent[p];
return p;
}
// p q
// O(h) , h
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// rank
// rank rank
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot;
else if(rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // , rank
}
}
}경로 압축 최적화: parent [p] = parent [parent [p], 다음 그림 의 노드 4 에서 루트 노드 를 찾 을 때 다음 그림 의 그림 1 에서 그림 2 의 모양 으로 변 합 니 다.그리고 노드 4 와 노드 3 을 다시 찾 으 면 다음 그림 의 그림 2 에서 그림 3 의 관계 로 변 한다.이렇게 하면 나무의 높이 를 편리 하 게 낮 출 수 있다.
나무의 높이 를 바 꿀 때 rank 값 을 바 꾸 지 않 는 것 이 합 리 적 입 니까?합 리 적 인 것 입 니 다. rank 은 실제 적 으로 나무의 높이 를 대표 하지 않 기 때문에 진정한 해석 은 순위 입 니 다. 즉, 위의 나무의 순위 (rank) 가 아래 나무의 순위 보다 크 고 이런 규칙 은 계속 존재 합 니 다.
package unionFind;
// Union-Find
public class UnionFind5 implements UF {
// rank[i] i
// , rank , rank ,
// rank height depth ,
private int[] rank;
private int[] parent; // parent[i] i
//
public UnionFind5(int size){
rank = new int[size];
parent = new int[size];
// , parent[i] ,
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
// , p
// O(h) , h
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
// p q
// O(h) , h
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// rank
// rank rank
if( rank[pRoot] < rank[qRoot] )
parent[pRoot] = qRoot;
else if( rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // , rank
}
}
}재 귀적 호출: 이 노드 가 루트 노드 로 가 는 경로 의 모든 노드 가 루트 노드 를 가리 키 도록 합 니 다.그 중에서 find 방법 중의 while 순환 을 재 귀 알고리즘 으로 바 꾸 었 습 니 다.
if(p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
테스트 를 통 해 재 귀 방식 을 사용 하 는 효율 은 이전 판 의 효율 보다 더 느리다.
package unionFind;
// Union-Find
public class UnionFind6 implements UF {
// rank[i] i
// , rank , rank ,
// rank height depth ,
private int[] rank;
private int[] parent; // parent[i] i
//
public UnionFind6(int size){
rank = new int[size];
parent = new int[size];
// , parent[i] ,
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
// , p
// O(h) , h
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// path compression 2,
if(p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
// p q
// O(h) , h
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// p q
// O(h) , h
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// rank
// rank rank
if( rank[pRoot] < rank[qRoot] )
parent[pRoot] = qRoot;
else if( rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // , rank
}
}
}나무의 4 가지 변종: 더미, 선분 나무, trie, 그리고 집합
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
