[그래프 알고리즘]사이클 탐지

그래프에서의 사이클

한 노드에서 다른 노드들을 거쳐 처음 노드로 돌아올 수 있으면, 그 그래프에는 사이클이 존재한다고 합니다.

무향 그래프에서의 사이클 존재 여부 확인

1. DFS

DFS로 그래프를 순회하면서, 이미 방문한 노드로 이어지는 엣지가 있을 때,

그 무향그래프는 사이클이 존재합니다.

2. Disjoint Set(Union and Find)

한 엣지가 연결하는 두 노드를 하나의 그룹으로 묶어가는 방식으로도 사이클의 존재 여부를 확인할 수 있습니다.

처음에는 모든 노드들이 서로 다른 그룹에 속한 것으로 가정합니다.

모든 엣지들을 확인하며, 한 엣지가 연결하는 두 노드를 같은 그룹으로 묶습니다.

그러다가 어느 엣지가 연결하는 두 노드가 이미 같은 그룹에 속한 노드들이라면, 이미 이전에 확인한 다른 엣지들을 통해 두 노드가 연결될 수 있음을 의미하므로 사이클이 존재한다는 것을 알 수 있습니다.

이를 구현하기 위해 union and find 알고리즘을 이용합니다.

방향 그래프에서의 사이클 존재 여부 확인

방향 그래프에서는 back edge 의 존재 여부로 사이클이 존재하는지 확인할 수 있습니다.

back edge란 DFS로 그래프를 탐색 하다가, 아직 DFS 재귀 함수가 종료하지 않은 노드로 다시 방문을 하게 될때,

그 엣지를 back edge라고 합니다.

노드 1, 2, 3이 1->2->3 처럼 연결되어 있고, 1번 노드부터 DFS 를 한다고 할 때,

DFS 함수의 호출 순서는 1, 2, 3이고, 종료 순서는 3, 2, 1입니다.

근데 만약 노드 2번에서 DFS 함수가 종료하기 전에 방문 된다면, 이는 2번 노드에 연결된 엣지를 통해 다시 2번으로 올 수 있음을 의미하므로, 사이클이 존재한다고 할 수 있습니다.

DFS로 순회하면서, 노드들의 방문순서와 DFS 함수 종료 여부를 기록합니다.

이미 이전에 방문한 적이 있고, DFS 함수가 종료되지 않은 노드를 다시 방문한다면 사이클이 존재합니다.