자료구조 - 이분 그래프(Bipartite Graph)

 

관련 글

 

그래프 관련 글은 여기를 참조
그래프 탐색 - BFS는 여기를 참조
그래프 탐색 - DFS는 여기를 참조

 

 

1. 이분 그래프

 

이분 그래프는 그래프 형태의 자료구조인데 정점을 2그룹으로 나눌 수 있으되 같은 그룹의 정점끼리는 간선으로 이어지지 않은 경우를 의미한다.

즉 아래의 그림처럼 된 경우가 그러하다.

 

 

위의 그림에서 보다시피 빨간색, 파란색의 정점으로 두 그룹으로 나뉘었다. 그러나 빨간색 끼리는 인접하지 않았고, 파란색 끼리도 인접하지 않았다.

 

위와 같은 형태의 그래프가 형성될 때 이분 그래프(Bipartite Graph) 라고 한다.

참고로 간선이 아예 없고 정점만 있는 경우도 이분 그래프이다!

 

이분 그래프는 현실에서 굉장히 많이 쓰이는 중요한 그래프이다. 주요 예시는 다음과 같다.

학생 - 수업의 관계 : 학생들이 어떤 수업을 듣고 있는지 관계를 나타내는 맵을 그릴 수 있다.
유저 - 선호 영화 관계 : 각 유저가 어떠한 영화를 선호하는지 나타내는 맵을 그릴 수 있다.
구직자 - 선호 회사 관계 : 각 구직자가 어떠한 회사를 선호하는지 나타내는 맵을 그릴 수 있다.

위와 같이, 다양한 관계를 나타내는 맵을 그림으로써, 그 안에서 매칭 알고리즘을 이용하여 특정 내역을 추천하거나 특정 관계를 확인하는 등의 결과를 알아낼 수 있게 된다.

 

 

2. 구현하기

 

이 경우는 DFS, BFS 를  통해서 구현할 수 있다. 해결 방법은 다음과 같다.

아래의 경우는 BFS를 기준으로 생각한다.(DFS도 동일한데 구현 방식만 다를 뿐)

1. 최초 탐색 시작할 정점의 색상을 빨간색으로 칠한다.(숫자 1로 표현)
2. 최초 정점의 인접 정점의 색상을 파란색으로 칠한다.(숫자 -1로 표현)
3. 해당 인접 정점들을 차례로 탐색을 시작하며 자신과 인접한 정점을 빨간색으로 칠한다.(숫자 1로 표현)
4. 이와 같은 방식을 탐색을 지속하며 반복하여 2개의 색상으로 모두 칠한다.
5. 색상을 칠하다가 이웃 정점이 같은 색으로 칠해져 있다면 이분 그래프가 될 수 없다.

 

아래 코드를 보며 어떻게 구현할 수 있는지 이해해보자. 아래에서는 그래프를 인접 리스트가 아닌 인접 행렬로 보기 쉽게 구현을 했다.

 

BFS로 구현하는 방법은 아래 코드를 참조

import java.util.*;
public class Bipartite{
    // 상단의 그림을 인접행렬로 표현함.
    static int graph[][] = {{0, 0, 0, 0, 1, 1, 1, 0},
                            {0, 0, 0, 0, 0, 0, 0, 1},
                            {0, 0, 0, 0, 0, 0, 0, 1},
                            {0, 0, 0, 0, 0, 0, 1, 0},
                            {1, 0, 0, 0, 0, 0, 0, 0},
                            {1, 0, 0, 0, 0, 0, 0, 0},
                            {1, 0, 0, 1, 0, 0, 0, 0},
                            {0, 1, 1, 0, 0, 0, 0, 0}};
    // 정점의 개수 8개
    static int v = 8;
    public static void main(String[] args){
        int start = 0; // 0번 정점에서 탐색 시작
        boolean isBipartite = bfs(start);
        
        System.out.println(isBipartite ? "이분 그래프임!" : "이분 그래프가 아님!");
    }
    
    // BFS를 수행하는 메소드
    private static boolean bfs(int src){
        int color[] = new int[v];
        
        // 시작 정점은 1번 색상으로 칠한다.
        color[src] = 1;
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(src);
        
        while(!q.isEmpty()){
            int curr = q.poll();
            
            // 루프가 있다면 false 반환
            if(graph[curr][curr] == 1) return false;
            
            for(int i=0; i < v; i++){
                // 인접 정점이면서 아직 색상이 정해지지 않았다면
                if(graph[curr][i] == 1 && color[i] == 0){
                    color[i] = color[curr] * -1;
                    q.offer(i);
                // 인접했는데 같은 색상이면.. false 반환
                } else if(graph[curr][i] == 1 && color[i] == color[curr]){
                    return false;
                }
                
                // 기타 인접하지 않았거나 인접했는데 다른 색상이면서 이미 방문 완료된 경우는
                // 넘어간다.
            }
        }
        return true;
    }
}

 

DFS로 구현하는 방법은 아래 코드를 참조

import java.util.*;
public class Bipartite{
    // 상단의 그림을 인접행렬로 표현함.
    static int graph[][] = {{0, 0, 0, 0, 1, 1, 1, 0},
                            {0, 0, 0, 0, 0, 0, 0, 1},
                            {0, 0, 0, 0, 0, 0, 0, 1},
                            {0, 0, 0, 0, 0, 0, 1, 0},
                            {1, 0, 0, 0, 0, 0, 0, 0},
                            {1, 0, 0, 0, 0, 0, 0, 0},
                            {1, 0, 0, 1, 0, 0, 0, 0},
                            {0, 1, 1, 0, 0, 0, 0, 0}};
    // 정점의 개수 8개
    static int v = 8;
    
    // 색상 저장하는 배열
    static int[] color;
    public static void main(String[] args){
        int start = 0; // 0번 정점에서 탐색 시작
        
        color = new int[v];
        boolean isBipartite = dfs(start, 1);
        
        System.out.println(isBipartite ? "이분 그래프임!" : "이분 그래프가 아님!");
    }
    
    // DFS로 탐색하는 메소드
    private static boolean dfs(int src, int c){
        color[src] = c;
        
        // 루프가 있는 경우 이분 그래프가 될 수 없음
        if(graph[src][src] == 1) return false;

        for(int i=0; i < v; i++){
            // 인접하였으며 색상이 같다면 이분 그래프가 아니라고 반환
            if(graph[src][i] == 1 && color[src] == color[i]){
                return false;
                
            // 인접했는데 아직 방문하지 않은 상태라면 dfs로 지속 탐색
            // 현재와 다른 색상으로 칠함
            } else if(graph[src][i] == 1 && color[i] == 0){
                return dfs(i, c*-1);
            }
            
            // 그 외 인접하지 않았거나 인접했는데 다른 색상이면 넘어간다.
        }
        return true;
    }
}

 

읽어 주셔서 감사합니다. 오류가 있으면 댓글 주시면 반영하겠습니다.