서로소 집합의 Union 연산을 통한 Cycle 판별에 대한 궁금증.

이와 같이 5개의 간선으로 연결된, 5개의 노드가 있다.

 

노드 번호	1	2	3	4	5
부모 노드	1	2	3	4	5

 

Union 연산을 이용해 사이클 ( Cycle ) 여부를 알아보고자 한다.

 

 

Union(1,2)

노드 번호	1	2	3	4	5
부모 노드	1*	1*	3	4	5

 

Union(2,3)

노드 번호	1	2	3	4	5
부모 노드	1	1*	1*	4	5

 

Union(3,5)

노드 번호	1	2	3	4	5
부모 노드	1	1	1*	4	1*

 

 

Union(4,5)

노드 번호	1	2	3	4	5
부모 노드	1	1	1	1*	1*

 

Union(1,4)

노드 번호	1	2	3	4	5
부모 노드	1*	1	1	1*	1

루트 노드가 같아, Cycle이 있음을 알 수 있다.

 

 

여기서, 궁금증이 생기는데,

지금은 Union 연산이 사실 의미를 갖는지 모르겠다.

우선, 간선을 중복하지 않고 따라가니 처음 노드와 최종 노드가 같아 사이클임이 보이는데,

매번 Union연산을 할 때마다, 연산한 두 노드의 루트 노드가 같은 상황이다.

다만, 마지막 간선인 (1,4)에서는 연산전에 두 노드의 루트 노드가 같아 정확하게 사이클임이 직관적으로 보이지만 사이클 판별을 위한 Union연산의 시작 간선을 다르게 한다면

( 노드 번호는 임의로 설정한 것이기 때문에 시작점에 제약이 있다면 안된다. )

 

초기

노드 번호	1	2	3	4	5
부모 노드	1	2	3	4	5

 

Union(3,5)

노드 번호	1	2	3	4	5
부모 노드	1	2	3*	4	3*

 

Union(4,5)

노드 번호	1	2	3	4	5
부모 노드	1	2	3	3*	3*

 

Union(1,4)

노드 번호	1	2	3	4	5
부모 노드	1*	2	3	1*	3

 

Union(1,2)

노드 번호	1	2	3	4	5
부모 노드	1*	1*	3	1	3

 

Union(2,3)

노드 번호	1	2	3	4	5
부모 노드	1	1*	1*	1	3

 

마지막 연산이 종료된 후에, 2번 노드와 3번 노드의 루트노드가 같게되고

이러함으로 사이클을 판별할 수 있다.

 

그렇다면,

 

이 역시도 Union(1,2)를 하게되면 1번 노드와 2번 노드의 루트노드는 같게되고

사이클이 형성되는 것으로 보여지는데,

이는 “무방향 그래프는 무조건 사이클이 형성된다.” 라고 할 수 있는 게 아닌가 궁금하다.

 

참고한 자료들의 설명이 부족한건지 무언가 잘못생각한것에 꽂혀있는지 모르겠다.