[그래프] 사이클 검출

그래프에서 사이클이란 간단하다. 쉽게 말해서 자기 자신으로 돌아올 수 있는지를 찾는 것.

 

방법에는 union-find와 dfs의 백엣지 검출이 있다.

 

이때 정점 n개, 간선 n-1개인 그래프는 트리이기에 정점 n개, 간선 n개인 그래프가 되어야 하나의 사이클이 존재한다.

 

트리에서는 visited 배열 없이도 DFS 탐색의 적용이 가능하다.

직전 노드가 어디인지만 표시해주면 된다.

 

사이클 검출 방식

사이클에서 그래프를 찾기 위해 n-1개의 간선을 탐색 한 후,

다시 vistied한 정점을 발견한다면 그 정점에 의해 사이클이 형성된다.

 

사이클에 포함된 정점들이 어떻게 되어 있는 건지 알려면 정점이 어디서 부터 온 것인지를 저장해놓으면 된다.

 

따라서 dfs로도 사이클을 검출할 수 있다.

 

def has_cycle(graph, node, visited, stack):
    visited[node] = True
    stack[node] = True

    # 현재 노드의 모든 이웃에 대해 반복()
    for neighbor in graph[node]:
        # 이웃을 아직 방문하지 않았다면 재귀 호출
        if not visited[neighbor]:
            if has_cycle(graph, neighbor, visited, stack):
                return True
        # 다음 노드에 방문을 했었고(위 조건), 스택에 존재한다면 순환 발견
        elif stack[neighbor]:
            return True

    # 현재 노드에서 빠져나오기 전에 스택에서 제거
    stack[node] = False
    return False

 

위 코드를 사용할 때는 반드시 graph, node, stack의 형태가 set의 형태여야 한다.

graph = {i: [] for i in range(1, n + 1)}
visited = {i: False for i in range(1, n + 1)}
stack = {i: False for i in range(1, n + 1)}

 

한가지 더 주의하자면, 현재 노드에서 빠져나오기 전에 스택에서 제거해야 사이클이 없을 때 오류가 생기지 않는다.

또한 무한 루프를 방지한다.

 

예시로, 1->2, 1->3, 2->3인 그래프가 있다면, stack[node] = False가 없다면 다음 출력이 나온다.

{1: True, 2: False, 3: False}
Entering node: 1
현재 가려는 이웃: 2
  방문하지 않은 시점: 2
{1: True, 2: True, 3: False}
Entering node: 2
현재 가려는 이웃: 3
  방문하지 않은 시점: 3
{1: True, 2: True, 3: True}
Entering node: 3
{1: True, 2: True, 3: True} 아래 스택
Leaving node: 3
{1: True, 2: True, 3: True} 아래 스택
Leaving node: 2
현재 가려는 이웃: 3
  Cycle found, returning True
YES

 

한번의 노드를 마친 뒤에, 다음 노드에서 stack이 계속 True로 되어 있다.

그래서 방문했다고 판단하여 YES로 나오지만, 사실은 NO가 맞다.

{1: True, 2: False, 3: False}
Entering node: 1
현재 가려는 이웃: 2
  방문하지 않은 시점: 2
{1: True, 2: True, 3: False}
Entering node: 2
현재 가려는 이웃: 3
  방문하지 않은 시점: 3
{1: True, 2: True, 3: True}
Entering node: 3
{1: True, 2: True, 3: False} 아래 스택
Leaving node: 3
{1: True, 2: False, 3: False} 아래 스택
Leaving node: 2
현재 가려는 이웃: 3
{1: False, 2: False, 3: False} 아래 스택
Leaving node: 1
NO

 

아래 예시처럼, 순환이 발생하지 않았을 때 전부 다시 백트래킹하며 False로 만들어주고 함수를 나와야, True를 반환하지 않고 오류를 방지할 수 있다.