제2 1 장 교차 집합 하지 않 는 데이터 구조 개인 노트 에 사용 된다.

제2 1 장 교차 하지 않 고 집합 하 는 데이터 구조 에 사용 된다.
21.1 교차 하지 않 고 집합 하 는 작업
하나의 대상 으로 하나의 집합 요 소 를 표시 하고 x 를 설정 하여 하나의 대상 을 표시 하 며 다음 과 같은 세 가지 조작 을 지원 하 기 를 바 랍 니 다.

MAKE - SET (x): 새로운 집합 을 만 듭 니 다. 유일한 구성원 (따라서 대표) 은 x 입 니 다.각 집합 은 서로 교차 하지 않 기 때문에 x 는 다른 어떤 집합 에 나타 나 지 않 을 것 이다.

UNION (x, y): x 와 y 를 포함 하 는 두 개의 동적 집합 (Sx, Sy 로 표시) 을 하나의 새로운 집합 으로 합 친다. 즉, 이 두 집합의 집합 이다.

FIND - SET (x): 바늘 을 되 돌려 줍 니 다. 이 바늘 은 x 를 포함 하 는 (유일한) 집합 대 표를 가리 키 고 있 습 니 다.

교차 하지 않 는 집합 데이터 구조의 많은 응용 중 하 나 는 무 방향 그림 의 연결 분량 을 확정 하 는 것 이다.아래 의사 코드 에서 그림 G 의 정점 집합 은 G. V 로 표시 하고 변 집합 은 G. E 로 표시 합 니 다.

CONNECTED-COMPONENTS(G){
    for each vextex v in G.V
        MAKE-SET(v)
    for each edge(u,v) in G.E
        if FIND-SET(u) != FIND-SET(v)
            UNION(u,v)
}

SAME-COMPONENT(u,v){
    if FIND-SET(u) == FIND-SET(v)
        return TRUE
    else
        return FALSE
}

21.2 교차 하지 않 고 집합 하 는 링크 표시
모든 집합 은 자신의 링크 로 표시 한다.모든 집합 대상 은 head 속성 과 tail 속성 을 포함 하고 head 속성 은 표 의 첫 번 째 대상 을 가리 키 며 tail 속성 은 표 의 마지막 대상 을 가리킨다.링크 의 모든 대상 은 집합 구성원, 링크 의 다음 대상 을 가리 키 는 지침 과 집합 대상 으로 돌아 가 는 지침 을 포함한다.
21.3 교차 하지 않 고 숲 을 모인다.

MAKE-SET(v){
    x.p = x
    x.rank = 0
}

UNION(u,v){
    LINK(FIND-SET(u),== FIND-SET(v))
}

LINK(x,y){
    if x.rank > y.rank
        y.p = x
    else
        x.p = y
        if x.rank == y.rank
            y.rank++
}

FIND-SET(x){
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p
}