Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 방향 그래프(Directed Graph)의 사이클 감지하기

이 글에서는 아래 문제를 해결하는 방법을 단계별로 살펴보겠습니다.

문제 정의

주어진 방향 그래프(Directed Graph)에 사이클(cycle)이 존재하는지 판별해야 합니다. 그래프에 하나라도 사이클이 있다면 True를, 없다면 False를 출력합니다.

접근 방법: DFS와 재귀 스택 활용

방향 그래프에서 사이클을 감지하는 가장 대표적인 방법은 깊이 우선 탐색(DFS)입니다. 핵심 아이디어는 다음과 같습니다.

  • visited 배열로 각 노드의 방문 여부를 추적합니다.
  • recStack(재귀 스택) 배열로 현재 탐색 경로에 포함된 노드를 추적합니다.
  • 탐색 중 어떤 이웃 노드가 이미 방문된 상태이면서 동시에 재귀 스택에 존재한다면, 이는 역방향 간선(back edge)이 존재한다는 뜻이며 곧 사이클이 있다는 의미입니다.

구현 예제

# collections 모듈
from collections import defaultdict

# 그래프 생성을 위한 클래스
class Graph():
    # 생성자
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def isCyclicUtil(self, v, visited, recStack):
        # 현재 노드를 방문 처리하고 재귀 스택에 추가
        visited[v] = True
        recStack[v] = True

        # 이웃 노드 중 방문된 상태이면서 재귀 스택에 있는 노드가 있다면 순환 구조
        for neighbour in self.graph[v]:
            if visited[neighbour] == False:
                if self.isCyclicUtil(neighbour, visited, recStack) == True:
                    return True
            elif recStack[neighbour] == True:
                return True

        # 재귀 호출이 끝나면 현재 노드를 재귀 스택에서 제거
        recStack[v] = False
        return False

    # 그래프가 순환하면 True 반환
    def isCyclic(self):
        visited = [False] * self.V
        recStack = [False] * self.V
        for node in range(self.V):
            if visited[node] == False:
                if self.isCyclicUtil(node, visited, recStack) == True:
                    return True
        return False


g = Graph(4)
g.addEdge(0, 3)
g.addEdge(0, 2)
g.addEdge(3, 2)
g.addEdge(2, 0)
g.addEdge(1, 3)
g.addEdge(2, 1)

if g.isCyclic() == 1:
    print("그래프는 순환 구조입니다")
else:
    print("그래프는 비순환 구조입니다")

실행 결과

그래프는 순환 구조입니다

코드 설명

위 예제에서 그래프는 4개의 정점(0~3)으로 구성되어 있으며, 간선 2 → 0 → 2로 인해 사이클이 형성됩니다. 따라서 프로그램은 "그래프는 순환 구조입니다"를 출력합니다.

모든 변수(visited, recStack)는 지역 범위(local scope) 내에서 선언되며, DFS가 진행됨에 따라 다음과 같이 동작합니다.

  1. isCyclic() 메서드는 모든 정점을 순회하며 아직 방문하지 않은 노드에서 DFS를 시작합니다.
  2. isCyclicUtil()은 현재 노드를 방문 표시하고 재귀 스택에 올린 뒤, 인접한 모든 이웃 노드를 재귀적으로 탐색합니다.
  3. 이웃 노드가 이미 방문된 상태에서 재귀 스택에도 존재하면 사이클이 발견된 것이므로 즉시 True를 반환합니다.
  4. 현재 노드의 탐색이 끝나면 재귀 스택에서 제거하여, 해당 노드가 더 이상 현재 경로에 속하지 않음을 표시합니다.

이 알고리즘의 시간 복잡도는 O(V + E)이며, 공간 복잡도 역시 방문 배열과 재귀 스택 저장에 O(V)입니다.

결론

이번 글에서는 DFS와 재귀 스택을 활용하여 Python으로 방향 그래프의 사이클을 감지하는 방법을 배웠습니다. 이 기법은 작업 스케줄링, 의존성 분석, 컴파일러의 순환 참조 검사 등 다양한 실무 문제에 응용할 수 있습니다.