데이터 구조 와 알고리즘 의 병합 집합(교차 집합 하지 않 음)

인식 하고 수집 하 다. ( )에 대해 서 는 많이 들 어 본 적 이 없 거나 잘 모 르 는 사람 이 많다.실제로 집합 을 조사 하 는 것 은 매우 효율 적 인 데이터 구조 이다.간단 함 을 실현 하 는 것 은 모든 요소 통 이기 때문에 일 을 처리 하 는 효율 을 높 일 수 있다.
정 해진 의미 에 대해 백과 에서 이렇게 정의 한 것 은:
그리고 집합 을 찾 습 니 다.N 개의 요소 가 있 는 집합 응용 문제 에서 우 리 는 보통 시작 할 때 모든 요소 가 하나의 단일 요소 의 집합 을 구성 한 다음 에 일정한 순서에 따라 같은 그룹 에 속 하 는 요소 가 있 는 집합 을 합 칩 니 다.그 사이 에 하나의 요소 가 어느 집합 에 있 는 지 반복 적 으로 찾 아야 합 니 다.복잡 하지 않 은 것 처럼 보이 지만 데이터 의 양 이 매우 많다 는 것 이 특징 이다.정상 적 인 데이터 구조 로 묘사 하면 공간 적 으로 너무 커서 컴퓨터 가 감당 할 수 없다.공간 적 으로 겨우 통과 하 더 라 도 운행 시간 이 복잡 해 경기 에 규정된 운행 시간(1~3 초)내 에 시험 문제 에 필요 한 결 과 를 계산 할 수 없고 집합 을 찾 아 설명 할 수 밖 에 없다.
그리고 집합 은 일종 으로 교차 하지 않 는 집합(Disjoint Sets)의 합병 과 조회 문 제 를 처리 하 는 데 사용 된다.항상 사용 중 에 숲 으로 표시 한다.
그리고 기본 사상 을 초기 화하 고 하나의 숲 은 모두 독립 적 이다.보통 배열 로 모든 값 을-1 로 표시 합 니 다. join (a,b)조작.a,b 두 개 를 합병 합 니 다.여기 있 는 a 를 주의 하 세 요.a,b 합병 이 아니 라 a,b 의 집합 합병 입 니 다.이것 은 일부 상황 을 파생 시 켰 다.a,b 가 독립 적 인(다른 합병 과 없 음)이 라면 a 는 b(또는 b 는 a),즉data[a]=b를 가리킨다.또한 이 집합 이 몇 개 인지 표시 하기 위해 원래-1의 b 는 다시-1 즉data[b]=-2.b 를 아버지 로 하 는 노드 는|-2|개 임 을 나타 낸다.

a,b
만약 에 집합(아버지 가 있 을 수도 있 고 자신 이 뿌리 일 수도 있다)이 있다 면 우 리 는 당연히 a,b(a,b 가 이미 다른 사람 을 가리 키 고 있 기 때문이다.)그러면 우 리 는 a,b 의 조상 을 조작 할 수 밖 에 없다.a,b 의 조상 은 가리 키 지 않 았 기 때문이다.그러면 그들 은 우선 마이너스 하 나 를 다른 위 에 올 려 야 한다.그리고 이 수 치 는 가리 키 는 것 으로 바 뀌 어야 합 니 다.

상술 한 것 에 대해 당신 은 의문 이 있 을 수 있 습 니 다.
어떻게 a,b 가 집합 하고 있 는 지 확인 합 니까?집합 여 부 를 확인 하려 면 만 확인 해 야 합 니 다.뿌리의 수치 만 마이너스 이 고,다른 것 은 양수 가 가리 키 는 요 소 를 표시 하기 때문이다.그 러 니까 !a,b 합병,도대체 a 의 조상 이 b 의 조상 에 합병 되 었 습 니까?아니면 b 의 조상 이 a 에 합병 되 었 습 니까?이곳 에 서 는 두 가지 상황 이 발생 할 수 있 는데,이 선택 도 매우 중요 하 다.나무의 높이+1 의 화 는 전체 요소 조회 의 효율 이 떨어진다 는 것 을 알 아야 합 니 다!
그래서 우 리 는 보통 소수 가 큰 나 무 를 가리 키 거나 낮은 나 무 는 높 은 나 무 를 가리 키 는데 이것 은 조회 효율 을 증가 시 킬 수 있 습 니 다!

물론 높이 와 수량의 선택 에 있어 서 는 당신 스스로 선택 하고 고려 해 야 합 니 다.
다른 경로 압축?
매번 조회 할 때마다 아래 에서 위로.우리 가 재 귀 를 호출 할 때 경 로 를 압축 할 수 있다.왜냐하면 우 리 는 하나의 요 소 를 찾 는 데 조상 까지 만 필요 하기 때문에 그 가 조상 에 게 가 까 울 때 .그리고 경 로 를 압축 하 는 대가 가 크 지 않 습 니 다!

코드 구현
그리고 집합 을 찾 는 것 이 비교적 간단 합 니 다.코드 를 직접 붙 입 니 다!

package         ;

import java.util.Scanner;
public class DisjointSet {
	static int tree[]=new int[100000];//   500  
	public DisjointSet() 	{set(this.tree);}
	public DisjointSet(int tree[]) 
	{
		this.tree=tree;
		set(this.tree);
	}
	public void set(int a[])//       -1      ，      -1     ，  ，-1       -（-1） 
	{
		int l=a.length;
		for(int i=0;i<l;i++)
		{
			a[i]=-1;
		}
	}
	public int search(int a)//        
	{
		if(tree[a]>0)//      
		{
			return tree[a]=search(tree[a]);//    
		}
		else
			return a;
	}
	public int value(int a)//  a      （  ）
	{
		if(tree[a]>0)
		{
			return value(tree[a]);
		}
		else
			return -tree[a];
	}
	public void union(int a,int b)//   a，b      
	{
		int a1=search(a);//a 
		int b1=search(b);//b 
		if(a1==b1) {System.out.println(a+" "+b+"       ");}
		else {
		if(tree[a1]<tree[b1])//     ，        ，    value  
		{
			tree[a1]+=tree[b1];//            
			tree[b1]=a1;  //b   a   ，    a；
		}
		else
		{
			tree[b1]+=tree[a1];//            
			tree[a1]=b1;  //b   a   ，    a；
		}
		}
	}
	public static void main(String[] args)
	{		
		DisjointSet d=new DisjointSet();
		d.union(1,2);
		d.union(3,4);
		d.union(5,6);
		d.union(1,6);
		
		d.union(22,24);
		d.union(3,26);
		d.union(36,24);
		System.out.println(d.search(6));	// 
		System.out.println(d.value(6));  //  
		System.out.println(d.search(22));	// 
		System.out.println(d.value(22));  //  
	}
}

package         ;import java.util.Scanner;public class DisjointSet {static int tree[]=new int[100000];//   500  public DisjointSet() {set(this.tree);}public DisjointSet(int tree[]) {this.tree=tree;set(this.tree);}public void set(int a[])//       -1      ，      -1     ，  ，-1       -（-1） {int l=a.length;for(int i=0;i<l;i++){a[i]=-1;}}public int search(int a)//        {if(tree[a]>0)//      {return tree[a]=search(tree[a]);//    }elsereturn a;}public int value(int a)//  a      （  ）{if(tree[a]>0){return value(tree[a]);}elsereturn -tree[a];}public void union(int a,int b)//   a，b      {int a1=search(a);//a int b1=search(b);//b if(a1==b1) {System.out.println(a+" "+b+"       ");}else {if(tree[a1]<tree[b1])//     ，        ，    value  {tree[a1]+=tree[b1];//            tree[b1]=a1; //b   a   ，    a；}else{tree[b1]+=tree[a1];//            tree[a1]=b1; //b   a   ，    a；}}}public static void main(String[] args){DisjointSet d=new DisjointSet();d.union(1,2);d.union(3,4);d.union(5,6);d.union(1,6);d.union(22,24);d.union(3,26);d.union(36,24);System.out.println(d.search(6));// System.out.println(d.value(6)); //  System.out.println(d.search(22));// System.out.println(d.value(22)); //  }}

결어 와 검색 집합 은 간단 하지만 효율 적 인 데이터 구조 에 속한다.집합 중 에 자주 만난다.채택 하고 조사 하지 않 으 면 전통 적 인 폭력 효율 이 너무 낮 아 받 아들 여지 지 않 는 다.또 중 하 나 를 소개 하고 조사 할 수 있 는 기회 가 있다미로 놀이.
총결산
위 에서 말 한 것 은 소 편 이 여러분 에 게 소개 한 데이터 구조 와 알고리즘 을 합 쳐 집합(교차 하지 않 고 집합)을 찾 는 것 입 니 다.여러분 에 게 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 저 에 게 메 시 지 를 남 겨 주세요.소 편 은 제때에 답 해 드 리 겠 습 니 다.여기 서도 저희 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!
만약 당신 이 본문 이 당신 에 게 도움 이 된다 고 생각한다 면,전 재 를 환영 합 니 다.번 거 로 우 시 겠 지만 출처 를 밝 혀 주 십시오.감사합니다!