그리고 데이터 구조 확인(연결 리스트 처리 사용)

뮤텍스 처리

뮤텍스 세트에서만 작동합니다.

이 경우 교차점은 제외됩니다.

노조를 지원하는 작업은 다음과 같습니다.

제작팀 (x) : 요소 x만 포함하는 집합을 만듭니다.

lookup_set(x) : 요소 x가 있는 집합을 찾습니다.

합집합(x,y) : 요소 x를 포함하는 집합과 요소 y를 포함하는 집합의 합집합을 만듭니다.

컬렉션을 처리하는 방법에는 연결 목록을 사용하는 방법과 트리를 사용하는 방법의 두 가지가 있습니다.

  • 연결된 목록다음을 사용하여 뮤텍스 세트를 처리하는 방법 알아보기
  • 연결된 목록처리 집합을 사용하는 작업의 실행 시간을 분석합니다.

  • 나무다음을 사용하여 뮤텍스 세트를 처리하는 방법 알아보기
  • 나무처리 집합을 사용하는 작업의 실행 시간을 분석합니다.

연결 목록 처리 사용

동일한 컬렉션의 요소는 단일 연결 목록으로 관리됩니다.

연결된 목록의 첫 번째 요소는 집합의 대표 요소입니다.

1) Make-Set 상태(x)

Make-Set(x): 요소 x만 포함하는 집합을 생성합니다.


이때 대표 노드는 자기 자신이 된다.

2) Find-Set(x) 상태

lookup_set(x) : 요소 x가 있는 집합을 찾습니다.


위의 다이어그램에서 컬렉션은 두 부분으로 나눌 수 있습니다.

상위 연결 리스트를 A, 하위 연결 리스트를 B라고 하자.

세트의 각 노드는 첫 번째 노드를 대표 노드로 가리킵니다.

3) 조인트(x,y) 상태

Union(x,y): 요소 x를 포함하는 집합과 요소 y를 포함하는 집합의 합집합을 만듭니다.


이 경우 집합 A는 부분 집합이고 집합 B는 주 집합이라고 가정합니다.

부분 집합 A를 기본 집합 B에 추가하고 집합 A의 각 노드는 노드를 나타내는 포인터를 가리킵니다.

집합 B의 대표 노드로 교체합니다.

NIL을 가리키는 세트 B의 마지막 노드는 세트 A의 헤드 노드입니다.

가리키고 연결하다

노조는 왜 이러는 걸까? 가중 합집합 방법 왜냐하면.

가중치를 고려한다는 것은 연결된 목록의 두 세트를 결합할 때 더 작은 세트가 더 큰 세트 다음에 오는 것을 의미합니다.

그 이유는 조인되는 컬렉션의 대표 요소에 대한 포인터 업데이트 작업을 최소화하기 위함입니다.

4) 수행시간

연결 리스트로 표현되는 배타적 집합에서 가중 합집합을 사용할 때, m개의 Make-Set, Union, Find-Set 중 n개가 Make-Set이면 총 실행 시간은 O(m+nlogn)입니다.