[Algorithm] 무방향그래프에서 싸이클 찾기

 

 

 

 

 

 

싸이클(Cylce)은 '순환'을 의미한다. 

 

일반적으로 싸이클은 좋지 못한 현상이다.  자칫 무한 루프에 빠질 수 있고 순환을 이루는 개체간의 종속성이 올라간다. 간선을 의존관계라고 생각해보자. A는 C에 의존하고 C는 B에 의존하고 B는 A에 의존한다. 종속성이 커질수록 결합도가 올라가 유지보수가 어려워진다. 

 

그러므로 그래프가 싸이클이 있는지 여부를 판단하는 알고리즘이 필요하다. 

 

1) 무방향그래프에서 사이클 찾기 ( Union-Find 알고리즘 )

2) 방향그래프에서 사이클 찾기 ( DFS 탐색 알고리즘 )

 

간선에 방향이 없으면 무방향그래프, 있으면 방향그래프이다.  이번 포스팅에서는 무방향그래프에서 싸이클을 찾아보겠다.

 

 

Union-Find 알고리즘 사용하기

 

[Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 )

Union-Find 알고리즘에 대한 자세한 내용은 위 글을 참고 바란다.

 

 

 

 

 

노드	A	B	C	D
부모	A	B	C	D

 

 

처음에는 각 노드의 부모는 자신이다.  여기서 간선을 하나씩 추가해보자.( 알파벳 순서대로 부모가 된다. )

 

 

1) [ A-B ] 간선 추가

 

 

 

 

A의 부모는 A이다.

B의 부모는 B이다.

 

A-B 간선을 추가해도 싸이클은 생성되지 않는다.

B의 부모는 알파벳 순서에 따라 A가 된다.

 

노드	A	B	C	D
부모	A	A	C	D

 

 

2) [ A-C ] 간선추가

 

 

 

 

 

A의 부모는 A이고

C의 부모는 C이다.

 

A-C 간선이 추가되어도 싸이클은 생성되지 않는다. 

C의 부모는 알파벳 순서에 따라 A가 된다.

 

노드	A	B	C	D
부모	A	A	A	D

 

 

3) [ B-C ] 간선 추가

 

 

B의 부모는 A이다.

C의 부모는 A이다. 

 

B-C 간선이 추가되면 부모가 동일하므로 싸이클이 형성된다.

 

 

이와같이, 부모가 동일한 두 노드 사이에 간선이 추가되면 싸이클이 발생함을 알 수 있다.

Union-Find 알고리즘을 사용하면 싸이클을 판별할 수 있다.

 

이 과정을 코드로 구현해보자.

 

 

코드 구현( python )

 

# 부모찾기 (FIND)
def find_root(parent,x):
  if parent[x] != x :
    parent[x] = find_root(parent,parent[x])
  return parent[x]

# 부모합치기 (UNION)
def union_graph(parent,a,b) :

  a_root = find_root(parent,a)
  b_root = find_root(parent,b)

  if a_root > b_root : parent[a_root] = b_root
  else : parent[b_root] = a_root


n,e = map(int,input().split()) # 노드의 개수 : n , 간선의 개수 : e
parent = [0]*(n+1) # 부모 테이블

#부모테이블 자기자신으로 초기화
for i in range(1,n+1) :
  parent[i] = i 

cycle = False #싸이클 플래그

#간선 입력받기
for _ in range(e) :
  a,b = map(int,input().split())

  if find_root(parent,a) == find_root(parent,b) : # 두 노드의 부모가 동일한데 간선이 추가되면 싸이클이다.
    cycle = True # 싸이클 True
    break # 반복종료

  else : union_graph(parent,a,b) #싸이클이 아닌경우 부모합치기

#출력
if cycle : print("싸이클이 발생했습니다.")
else : print("싸이클이 없습니다.")

 

- 입력

3 3
1 2
1 3
2 3

 

- 출력

싸이클이 발생했습니다.

 

 

---

 

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서