[알고리즘] 그래프 사이클

그래프에서 사이클을 판별하는 방법 정리

무방향 그래프 사이클 여부 확인

union-find

union-find 알고리즘을 사용할 수 있다.
초기 상태이다.

1번 간선을 탐색한다.

2번 간선을 탐색한다.

3번 간선을 탐색한다.

4번 간선을 탐색할 때, 1과 4의 parent 배열 값이 같기 때문에, 사이클이 존재한다고 판단할 수 있다.
잘 생각해보면, union-find에서 parent 배열 값이 같다는 것은, 이미 하나의 MST를 이루고 있다는 것인데, 이미 연결된 그래프에 간선을 하나 추가하는 것은 사이클을 만드는 것이다.

DFS

각 정점에서 시작하여 자기 자신으로 돌아오는지 확인한다.

DFS를 이용하여 사이클에 있는 정점 찾기

사이클 내부 정점을 저장할 자료구조를 Queue로 가정.
1. 1 정점에서 시작해서 1 정점으로 돌아오는지 확인한다. 돌아오면 Queue에 add
2. 2 정점에서 시작해서 2 정점으로 돌아오는지 확인한다. 돌아오면 Queue에 add
3. 3 정점에서 시작해서 3 정점으로 돌아오는지 확인한다. 돌아오면 Queue에 add
4. 4 정점에서 시작해서 4 정점으로 돌아오는지 확인한다. 돌아오면 Queue에 add
각 정점으로 돌아오는지 확인할 때 주의할 점은
현재 탐색한 정점 수가 3 이상이어야 한다는 것이다.

public static void dfs(List<List<Integer>> graph, boolean[] check,
                           int curr, int start, int cnt){

        check[curr] = true;

        for(Integer next : graph.get(curr)){
            if(check[next]){        //이미 방문했으면
                if(next == start && cnt >= 3){
                    distance[next] = 0;
                    cycleQueue.add(next);
                    return;
                }
            }
            else{
                dfs(graph, check, next, start, cnt + 1);
            }
        }
    }

코드로 보면 위와 같다.
모든 정점에 대해 DFS 탐색을 마친 후에 Queue에는 1, 2, 4가 들어간 상태가 된다.

더 발전된 알고리즘

나중에.