> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/algorithm-quiz/bipartite.md).

# bipartite(이분그래프) 확인하기

어떤 그래프 내에서 인접한 두 정점이 서로 다른 2개의 부류에 소속되어 있을 때 그 그래프를 이분그래프(bipartite)라고 한다. 인접한 두 정점은 같은 부류에 포함되어 있으면 안된다. 아래의 그래프에서 정점들을 빨간색과 초록색 2가지로 분류했을 때, 각 정점은 자신과 인접한 정점과 다른 색을 가지고 있으므로 이분그래프라고 할 수 있다.

![](/files/-Ly9v0DR4WTS4Xe7wzP9)

아래의 그래프도 이분그래프에 속한다.

![](/files/-Ly9vzzh4Sb7I5DNZN09)

어떤 그래프가 이분그래프인지 아닌지 판별하려면, 어떤 정점 `v`의 부류와 `v`와 인접한 정점의 부류가 같은지 확인하면 된다. 위 예시의 경우, 정점 `v`의 색깔과 `v`와 인접한 정점의 색깔이 같은지 여부를 확인하면 되는 것이다.

어떤 그래프가 이분그래프인지 아닌지 확인하는 함수 `bipartite()`를 구현하면 아래와 같다.

```python
def bipartite(n, adjacent_list, start, end):
    color = [-1 for _ in range(n)]
    queue = list()
    queue.append(start)
    color[start] = BLACK

    while queue:
        v = queue.pop(0)
        for adj_v in adjacent_list[v]:
            if color[adj_v] == -1:
                color[adj_v] = WHITE if color[v] == BLACK else BLACK
                queue.append(adj_v)
            else:
                if color[adj_v] == color[v]:
                    return 0

    return 1
```

`queue`를 확인하는 `while`문은 정점의 갯수만큼 실행되며, 각 정점에 의해 `while`문이 1번 실행되었을 때 `for`문은 그 정점이 가진 간선의 갯수만큼 실행되므로 시간복잡도는 `O(|V| + |E|)`이다.

이미지 출처

* <https://www.geeksforgeeks.org/bipartite-graph/>
* [위키백과 - 이분그래프](https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84)