[자료구조] 이분 그래프

이분 그래프란

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

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

위와 같은 형태의 그래프가 형성될 때 이분 그래프(Bipartite Graph) 라고 한다.
참고로 간선이 아예 없고 정점만 있는 경우도 이분 그래프이다!

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

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

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

순환 그래프는 이분 그래프가 될 수 없다.
정점에서 간선이 없는 경우도 이분 그래프의 일원이 될 수 있다.

구현 방법

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

출처

https://hongjw1938.tistory.com/117