[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기

[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기

---

 

 

사이클을 찾기 위해서는 DFS를 활용한다. (정점 : v, 간선 : e)

 

- visited[] : 점들의 방문여부가 저장된 배열

- recur[] : v가 지금까지 방문한 점이 저장된 배열

 

for(v 수 만큼) {
   dfs(v, visited, recur)
}

 

DFS 수도코드

boolean dfs(v(a), visited, recur) {
    visited[v(a)] = true
    recur[v(a)] = true
    
    for(v(a)와 연결된 점의 수만큼) {
        b = 연결된 점
        if(!visited[b] && dfs(v(b), visited, recur){ 
        // b가 방문상태 아니고, 다시 b 방문한 점들 확인 후 true면 사이클이므로 true 리턴
            return true;
        }
        else if(recur[v(b)]) { //b가 이미 방문된 상태면 사이클이므로 true 리턴
            return true;
        }
        
        recur[v(a)] = false; // dfs 위해 다시 false로 돌려주기
        return false;
    }
}

 

시간복잡도는 O(V+E)로 효율적인 사이클 탐색이 가능하다.