[알고리즘] 유향 그래프에서 순환(cyclic) 판별

유향 그래프에서 순환(cyclic) 판별

 유향 그래프 내에 back edge가 존재하면, 순환이 존재합니다. dfs와 stack 2개를 활용하여 유향 그래프내에 순환 그래프가 존재하는지 확인할 수 있습니다.

 

작동 원리

 (1) 2개의 stack을 생성합니다.

 (2) traced 스택에 dfs를 수행하면서 탐색한 경로 노드 를 저장합니다.

 (3) visited 스택에 방문한 노드들을 저장합니다. visited 스택은 가지치기가 목적입니다.(소요시간 감소). visited 내에 존재하는 노드는 탐색을 진행하지 않기 때문입니다.

 (4) 탐색을 마친 노드는 traced에서 제거합니다.

 (5) 만약, traced에 존재하는 노드를 또 방문하면 순환이 존재합니다.

 

파이썬 코드

 stack 대신에 set 자료구조를 사용했습니다.

# 추적 경로를 담을 set 생성
traced = set()
# 방문한 노드를 담을 set 생성
visited = set()

def dfs(v):
    # 이미 탐색을 마친 노드이면 dfs 종료
    if v in visited:
        return True
    # 경로에 포함되어 있는 노드이면 순환 그래프
    if v in traced:
        return False
    # 경로에 v 노드 추가
    traced.add(v)
    for w in graph[v]:
        if not dfs(w):
            return False
    # 경로에 v노드 제거
    traced.remove(v)
    # 방문한 노드에 v 추가
    visited.add(v)
    return True

 

관련 문제

9466번: 텀 프로젝트