Algorithm // 방향성 그래프에서 사이클 찾기

찾는 방법

DFS로 방향 그래프를 탐색하면서 노드를 세 가지 상태로 색칠한다고 하자.

• 하얀색: 아직 DFS 탐색을 시작하지 않은 노드
• 회색: DFS 탐색을 시작했지만, 아직 그 노드에서 출발하는 모든 경로 탐색이 끝나지 않은 노드
  즉, 현재 DFS 호출 스택에 있는 노드
• 검은색: 그 노드에서 출발하는 모든 경로 탐색이 완전히 끝난 노드

DFS 중 어떤 노드의 다음 노드를 확인했을 때, 그 다음 노드가 회색이라면 사이클이 존재한다.

왜냐하면 회색 노드는 현재 DFS 경로 위에 있는 조상 노드이기 때문이다.
따라서 현재 노드에서 그 회색 노드로 가는 간선이 있다는 것은, 이미 지나온 경로로 다시 돌아갈 수 있다는 뜻이고, 이것은 방향 그래프에서 사이클을 의미한다.

반대로 다음 노드가 검은색이면 이미 그 노드에서 출발하는 모든 경로 탐색이 끝난 상태이므로, 다시 탐색할 필요가 없다.

코드 블록

class CycleChecker:
    def __init__(self, graph: dict):
        self.color = defaultdict(lambda: 'white')
        self.graph = graph
        
    def check_cycle(self, src: int) -> bool:
        self.color[src] = 'gray'
        
        for dst in self.graph[src]:
            if self.color[dst] == 'gray':
                return True

            elif self.color[dst] == 'white':
                if self.check_cycle(dst):
                    return True
                
        self.color[src] = 'black'
        return False

• 그래프의 특정 시작점으로 부터 사이클을 탐지하는 코드

from collections import defaultdict

class CycleChecker:
    def __init__(self, graph: dict):
        self.color = defaultdict(lambda: 'white')
        self.graph = graph

    def check_cycle(self, src: int) -> bool:
        self.color[src] = 'gray'

        for dst in self.graph.get(src, []):
            if self.color[dst] == 'gray':
                return True

            if self.color[dst] == 'white':
                if self.check_cycle(dst):
                    return True

        self.color[src] = 'black'
        return False

    def has_cycle(self) -> bool:
        nodes = set(self.graph.keys())

        for src in self.graph:
            for dst in self.graph[src]:
                nodes.add(dst)

        for node in nodes:
            if self.color[node] == 'white':
                if self.check_cycle(node):
                    return True

        return False

• 그래프 내부 모든 노드로부터 시작해서 사이클을 탐지하는 것
• has_cycle은 사이클 탐지에 참여 했는지 여부를 판별해 포함된적 없는 노드들에 대해 사이클을 탐지한다.