[자료구조] 이분 그래프

1. 개념

어떤 그래프에 있는 노드를 두 집합으로 나눴을 때, 같은 집합 내의 노드끼리는 간선으로 연결되어 있지 않고, 다른 집합의 노드끼리는 간선으로 연결되어 있는 그래프. 이분그래프가 되려면 서로 다른 그룹의 노드끼리는 모두 연결이 가능해야한다.

 

2. 이분 그래프 판별

• BFS나 DFS로 탐색하면서 정점을 방문할 때, 그 정점에 특정 색을 칠한다.
• 위에서 방문한 정점과 인접한 정점을 방문할 때는 위에서 칠한 색과 다른 색을 칠한다.

특정 정점을 방문해서 색을 칠한 후 그 정점과 인접한 정점의 색을 보는데 색이 같다는 것이 드러나면 이분 그래프가 아니다.

 

3. 코드

public static void dfs(int nodeIndex){
    visited[nodeIndex] = true;
    for(int n : A[nodeIndex]){
        if(!visited[n]){
            check[n] = (check[nodeIndex]+1) % 2;
            dfs(n);
        }else if(check[nodeIndex] == check[n]){
            isEven = false;
        }
    }
}

• check는 각 노드별 집합을 나타내는 배열이다. 특정 노드를 방문해서 해당 노드와 인접한 다른 노드를 확인할 때, 특정 노드에 인접해 있는 것들은 특정 노드와 다른 집합에 들어가야 한다. 그래서 특정 노드의 check값에 1을 더한후 2로 나눈 나머지로 집합을 정한다. 이러면 집합이 0 아니면 1로 나뉘게 되어서 이분 그래프인지 확인이 가능하다.

public static void bfs(int nodeIndex){
    Queue<Integer> q = new LinkedList<>();
    q.offer(nodeIndex);
    visited[nodeIndex] = true;
    while(!q.isEmpty() && isEven){
        int v = q.poll();
        for(int n : A[v]){
            if(!visited[n]){
                visited[n] = true;
                q.offer(n);
                check[n] = (check[v]+1) % 2;
            }else if(check[n] == check[v]){
                isEven = false;
            }
        }
    }

}

4. 관련 문제

백준 1707