DFS로 cycle 판별하기 (유향, 무향 그래프)

1) 유향 그래프(directed)
기존의 dfs 코드에 finished 리스트를 추가한다. 만약, 이미 방문한 노드를 재방문하였을 때, 해당 노드의 dfs 호출이 끝나지 않았다면 사이클이 존재한다고 판단할 수 있다.

V, E = map(int, input().split())

def detect_uni():
    unidirectional = [[] for _ in range(V+1)]
    for _ in range(E):
        a, b = map(int, input().split())
        unidirectional[a].append(b)
    visited_uni = [False] * (V + 1)
    finished_uni = [False] * (V + 1)

    global cycle_uni
    cycle_uni = 0
    # dfs, 단방향, 연결 그래프의 사이클 찾기
    def dfs_unidirectional(v):
        global cycle_uni
        visited_uni[v] = True
        for next in unidirectional[v]:
            if not visited_uni[next]:
                dfs_unidirectional(next)
            elif not finished_uni[next]: 
            ## visited[next] and not finished[next]:
                cycle_uni += 1
        finished_uni[v] = True

    dfs_unidirectional(1)
    print(cycle_uni)

다양한 그래프를 직접 그려보면 이해하기 쉽다.

1. 자식 노드가 한 개 뿐인 직선형 트리
   
2. 기본 트리 형태
   
3. 사이클이 있는 경우
   
4. 사이클이 아니지만 재방문하는 경우
   

2) 무향 그래프

def detect_bi():
    bidirectional = [[] for _ in range(V+1)]
    for _ in range(E):
        a, b = map(int, input().split())
        bidirectional[a].append(b)
        bidirectional[b].append(a)
    visited_bi = [False] * (V + 1)
    
    global cycle_bi
    cycle_bi = False
    
    def dfs_bidirectional(v, parent):
        global cycle_bi
        visited_bi[v] = True
        for next in bidirectional[v]:
            if not visited_bi[next]:
                dfs_bidirectional(next, v) 
            elif parent != next:
                cycle_bi =  True

    dfs_bidirectional(1, -1)
    

detect_bi()
print(cycle_bi)

무향 그래프에서는 parent 개념을 도입한다. parent는 자신이 어떤 노드로부터 왔는지를 기억하는 param이다.

위의 무향 그래프에서, dfs는 1->2->3->4로 진행될 것이다. dfs(4)에서, 4와 연결된 next는 3, 2번 노드이다. 또한 dfs(4)의 parent는 3이다. next = 3의 경우, parent == next이므로 아무 문제가 없지만, next = 2의 경우, next != parent이므로 cycle이 발생했다고 판단할 수 있다.