Graph : 사이클 검출하기

그래프에서 사이클이 존재하는지 여부는 dfs 를 사용해서 직관적으로 찾을 수 있다.

 

일반적인 그래프의 코드를 살펴보도록 하자

static void dfs(int v) {
    visit[v] = true;
    for(int u : adj[v]) {
        if(visit[u]) continue;
        dfs(u);
    }
}

v 라는 정점을 기준으로 dfs 를 수행한다고 했을 때 dfs(v) 가 끝나기 전에 v 를 재방문하는 일이 생기면 사이클이 존재함을 알 수 있다.

 

아래의 코드는 dfs 를 이용한 사이클 존재 여부를 확인하는 코드이다.

 

static boolean cycle = false;

static boolean[] visit = new boolean[n+1];
static boolean[] finished = new boolean[n+1];

static void dfs(int v) {
    visit[v] = true;
    
    for(int u : adj[v]) {
        if(!visit[u]) dfs(u);
        else if(!finished[u]) cycle = true;
    }
    finished[v] = true;
}

finished 라는 배열을 통해서 해당 정점에서의 dfs 탐색이 끝났는지 여부를 저장한다. 이 때 이미 방문한 정점의 dfs 탐색이 끝나지 않았는데 해당 정점을 재방문하는 경우 사이클이 존재함을 확인할 수 있다.