[C로 쓴 자료구조] 동치 관계 (Equivalence Relations)

동치 관계

 

동치 관계를 이용하여 집합 S를 "동치 클래스"로 분할함

ex) 0=4, 3=1, 4=3, 5=6

동치 클래스 : {0, 1, 3, 4}; {5, 6}

 

배열을 통해 paris[n][n] 구조로 구현해보자.

<i, j>가 입력될 경우, pairs[i][j]와 pairs[j][i]를 1로 설정하는 방식으로 구현할 수 있다.

하지만 이경우에 원소의 수에 비해 동치항의 수가 적을 경우 즉 희소 행렬이 될 경우에 메모리의 낭비가 심해진다.

 

n개의 연결 리스트 seq[n] 구조로 구현해보자<i, j>가 입력될 경우 노드 j를 seq[i]가 가리키는 리스트에 추가노드 i를 seq[j]가 가리키는 리스트에 추가하는 방식으로 구현할 수 있다.

 

 

 

일차원 boolean 배열 out[n] : 해당 원소가 출력되었는지 check 하는 배열out[i] = TRUE : 원소 i를 이미 출력함out[i] = FALSE : i가 이미 출력되어 다시 출력할 필요 없음

 

1. 동치항을 입력받아 seq[]를 이용한 리스트 구성2. out[i] = TRUE인 첫 번째 원소 i를 선택하여 seq[i] 리스트를 스캔하면서 리스트의 원소들을 출력3. seq[i]의 원소 중에서 out[] 배열의 값이 TRUE인 원소들의 리스트들을 현재 스캔을 완료한 후 스캔하여야 함4. Stack을 구현하기 위해 해당 노드의 link를 Stack의 다음 원소를 가리키는 포인터로 변경

 

 

 

동치항의 입력이 완료된 후의 리스트

 

#include <stdio.h>
#include <atlalloc.h>
#define MAX_SIZE 24
#define IS_FULL(ptr) (!(ptr))
#define FALSE 0
#define TRUE 1

struct node {
	int data;
	struct node* link;
};

int main(void) {
	short int out[MAX_SIZE];
	struct node* seq[MAX_SIZE], * x, * y, * top;
	int i, j, n;

	printf("Enter the size(<= %d) ", MAX_SIZE);
	scanf_s("%d", &n);

	//seq[] out[] 초기화
	for (i = 0; i < n; i++) {
		out[i] = TRUE;
		seq[i] = NULL;
	}


	//input the equivalnece pairs
	printf("Enter a pair of numbers(-1 -1 to quit):");
	scanf_s("%d %d", &i, &j);
	while (i >= 0) {//-1이 입력되면 종료하도록
		x = (struct node*)malloc(sizeof(struct node));
		x->data = j;
		x->link = seq[i];
		seq[i] = x;
		//j를 리스트i의 앞에 추가함

		x = (struct node*)malloc(sizeof(struct node));
		x->data = i;
		x->link = seq[j];
		seq[j] = x;
		//i를 리스트j의 앞에 추가함


		printf("Enter a pair of numbers (-1 -1 to quit):");
		scanf_s("%d %d", &i, &j);
	}

	for (i = 0; i < n; i++) {
		if (!out[i]) continue; //out은 플래그임
		printf("\n New class: %5d", i);
		out[i] = FALSE;
		x = seq[i]; top = NULL;
		for (;;) {
			while (x) {
				j = x->data;
				if (out[j]) {
					printf("%5d", j); out[j] = FALSE;
					y = x->link; 
					x->link = top; 
					top = x; 
					x = y;
				}
				else x = x->link;
			}
			if (!top)
				break;
			x = seq[top->data]; top = top->link;
		}
	}
}

 

 

간단한 방법

for (x = seq[i]; x != NULL; x -= x->link){
	if (out[x->data] == TRUE)
		push(x->data)
}

 

 

실행결과