DFS로 사이클 탐지하는 알고리즘 탐구하기1 -기본 이론-

1. 무향 그래프에서 사이클

 

union find 알고리즘을 이용해서 쉽게 판단할 수 있다

 

https://deepdata.tistory.com/432

union find 알고리즘 활용 - 사이클을 판별하는 방법 -

 

 

간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고,

 

서로 다르다면 union을 수행하면 된다

 

 

2. 유향 그래프에서 사이클

 

한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한다.

 

그러므로 단순하게 생각하면 u에서 출발했는데, u로 돌아오는 경로가 있는지 확인만 하면 된다.

 

이를 모든 정점 u에 대해 수행해보면 현재 그래프에서 사이클이 존재하는지 알 수 있을 것이다.

 

def dfs(start,now):
    
    #이미 방문했던 now를 방문하게 되었을때,
    if visited[now] == 1:
        
        #시작 노드와 동일하다면... 사이클이 존재하는 것
        if start == now:
            
            return True
        
        return False
    
    #start에서 dfs하다가 now를 방문
    visited[now] = 1
    
    for v in graph[now]:
        
        #다음 v 노드로 이동
        if dfs(start,v):
            
            return True
    
    return False

 

 

 

 

 

 

 

 

 

위 그래프를 예시로 해보면 True를 반환한다

 

n = 7

edges = [(4,1),(1,2),(2,3),(3,1),(5,3),(6,5),(7,5)]

graph = [[] for _ in range(n+1)]

for a,b in edges:
    
    graph[a].append(b)

find = False

for i in range(1,n+1):
    
    visited = [0]*(n+1)
    
    if dfs(i,i):
        
        print(True)
        find = True
        break

if find == False:
    
    print(False)

True

 

 

 

그런데 모든 노드 i = 1,2,3,..,n마다 dfs를 수행해야하므로 n이 크면 매우 느리다

 

현재 노드 u에서 DFS를 시작하면 u에서 도달할 수 있는 모든 정점을 방문한 뒤에야 종료된다.

 

따라서 DFS 수행하다가 이전에 방문했던 정점이지만 DFS가 아직 끝나지 않은 정점을 다시 방문하게 된다면, 

 

사이클이 형성되어 있다는 뜻이다.

 

visited값을 0이나 1로 하지말고 0,-1,1로 해둔다면... 0은 아직 방문하지 않았고

 

-1은 방문했는데 dfs를 진행중이고, 1은 dfs가 끝난 상태를 의미한다

 

def dfs(u):
    
    #u에서 dfs가 진행중인데 (visited[u] = -1 or 1)
    #u를 다시 방문하였음
    if visited[u]:
        
        #u에서 dfs가 아직 안끝났는데 u를 다시 방문하였다면
        #사이클이 존재함
        if visited[u] == -1:

            return True
        
        #이미 u에서 dfs가 끝난 상태이면 다른 노드에서 u로 온 것이다
        return False
    
    #u에서 dfs 시작
    visited[u] = -1

    for v in graph[u]:

        if dfs(v): #u와 인접한 경로를 이동하면서 방문
            
            return True #dfs가 True를 반환한 경우, 사이클이 존재한다는 의미
    
    #u에서 dfs가 끝났다는 의미
    visited[u] = 1

    #끝났는데도, 아직 True를 반환하지 못하면 사이클이 없음
    return False

n = 7

edges = [(4,1),(1,2),(2,3),(3,1),(5,3),(6,5),(7,5)]

graph = [[] for _ in range(n+1)]

for a,b in edges:
    
    graph[a].append(b)

visited = [0]*(n+1)

print(dfs(7))

True

 

 

이는 1번의 dfs만으로 사이클을 탐지할 수 있어서 첫번째 제시된 알고리즘보다 빠르다

 

물론 이게 가능할려면 그래프가 연결그래프여야한다.

 

하나의 노드에서 모든 노드에 도달 가능한 그래프여야한다.

 

연결그래프가 아니라면, 모든 정점에서 수행해봐야하므로 두 알고리즘은 시간복잡도가 동일할듯?

 

 

 

 

이런 그래프면 5 > 6 > 7이 사이클인데도 불구하고 dfs(1)하면 False 나온다

 

당연한거긴한데

 

이런 연결그래프가 아니라면, 모든 정점에서 확인해봐야한다는거지