Cycle Detection Algorithm

방향 그래프가 주어졌을 때 종종 이 그래프 내에서 \(Cycle\)의 존재 유무를 확인해야 할 때가 있다. 이 글에서는 방향 그래프 내에서 싸이클의 존재 유무를 알아내는 알고리즘을 소개하려 한다.

기본적인 알고리즘

---

\(Cycle\)의 정의를 한번 생각해 보자. \(Cycle\)이란 정점 \(u\)에서 시작해 어떠한 경로를 지나 다시 \(u\)로 돌아오는 경로가 있다면 이를 \(Cycle\)이라고 한다. 그리고 그래프 내에 이러한 \(Cycle\)이 한개라도 있다면 \(Cycle\)이 존재하는 그래프가 된다. 그렇다면 특정한 시작 정점 \(u\)를 잡고 \(dfs\)를 실행해 다시 시작정점 \(u\)로 돌아오는 경로가 있는지 확인하는 알고리즘을 만든 뒤 모든 정점에 대해 해당 알고리즘을 실행하면 \(Cycle\)의 존재 유무를 알 수 있을 것이다.

// simple algorithm
// here가 이미 visited됐는데 시작정점이라면 cycle이 존재하는 것이다
// 모든 정점에 대해서 확인을 해준다(visited는 매번 새롭게 초기화)
bool findCycleAlgorithm(int start, int here) {
    if (visitied[here]) {
        if (here == start) {
            return true;
        }
        
        return false;
    }
    
    visitied[here] = true;
    
    for (int there : node[here]) {
        if (findCycleAlgorithm(start, there)) {
            return true;
        }
    }
    return false;
}

기본적인 알고리즘의 시간복잡도

---

그렇다면 우리가 작성한 코드의 시간복잡도는 어떻게 될까? 일단 한 정점에 대해서 \(dfs\)를 돌리므로 \(O(V+E)\)의 시간이 소요된다. 하지만 모든 정점에 대해서 \(dfs\)를 실행해야 하므로 최종적으로 \(O(V(V+E))\) 의 시간복잡도를 가지게 된다. 그래프의 크기가 작다면 문제없이 돌아가겠지만 그래프의 크기가 커진다면 기본적인 알고리즘은 \(TL\)을 받게 될 것이다. 그렇다면 우리는 이 기본적인 알고리즘을 개선시킬 수 있을까?

DFS Spanning Tree

---

우리가 \(dfs\)를 실행하면 \(dfs\ spanning\ tree\)가 만들어진다. 이 트리에는 아래와 같은 네 가지 간선의 종류가 존재한다.

 

1. Tree Edge (트리 간선)

• \(dfs\ spanning\ tree\)에 속한 간선

2. Forward Edge (순방향 간선)

• 스패닝 트리의 선조에서 자손으로 연결 되지만 \(Tree\ edge\)가 아닌 간선

3. Back Edge (역방향 간선)

• 스패닝 트리의 자손에서 선조로 연결되는 간선. 역시 \(Tree\ edge\)가 아니다.

4. Cross Edge (교차 간선)

• 위 세가지 경우가 모두 아닌 간선

우리는 \(Cycle\)을 찾아야 하는데 \(dfs\ spanning\ tree\)와 간선의 종류들을 아는것이 도움이 되는 걸까? \(Cycle\)의 존재 유무와 위 간선들간의 관계를 한번 생각을 해 보자. 1, 2, 4번 간선은 \(Cycle\)을 만드는데 도움이 안되는 것은 자명하다. 그렇다는 얘기는 \(Cycle\)의 존재 유무는 Back Edge의 존재 유무와 동치라는 얘기가 된다. 왜 그런지는 \(dfs\)의 정의를 생각해 본다면 쉽게 이해가 될 것이다.

 

자 그럼 남은 문제는 Back Edge를 효율적으로 찾는 문제로 바뀌었다. 이 역시 \(dfs\)의 정의를 잘 생각해 본다면 쉽게 찾을 수 있다. 어떠한 정점 \(u\)에서 \(dfs\)를 시작했다고 가정을 해 보자. \(u\)에서 시작한 \(dfs\)는 \(u\)에서 도달할 수 있는 모든 정점을 방문한 뒤에야 종료가 될 것이다. 그렇다는 얘기는 \(dfs\)를 돌다가 \(dfs\)가 아직 끝나지 않은 정점을 다시 방문하게 된다면 Back Edge가 존재한다는 얘기고 \(Cycle\)이 존재한다는 얘기가 된다.

 

이 알고리즘은 일반적인 \(dfs\)와 같은 시간복잡도인 \(O(V+E)\)로 주어진 방향 그래프 내에서 \(Cycle\)의 존재 유무를 알아낼 수 있다.

Advanced Algorithm

---

// advanced algorithm
// dfs한번에 cycle의 존재 유무를 확인한다
// visited가 -1이라는 얘기는 dfs가 아직 안끝났다는 의미고 1은 dfs가 끝났다는 얘기다
bool findCycleAlgorithm(int here) {
    if (visitied[here]) {
        if (visitied[here] == -1) {
            return true;
        }
        
        return false;
    }
    
    visitied[here] = -1;
    
    for (int there : node[here]) {
        if (findCycleAlgorithm(there)) {
            return true;
        }
    }
    
    visitied[here] = 1;
    
    return false;
}