[알고리즘] 이분그래프란? (특징, 탐색방법) (feat. BFS,DFS)

🙋🏻‍♀️ 이분그래프

위 사진처럼 그래프가 '두개의 색'으로 표현되는 것을 이분그래프라고 한다. 빨간정점과 검은정점 두 그룹으로 나뉘었는데, 같은 그룹끼리는 인접하지 않아야한다. 즉, 그래프의 모든 정점이 두 그룹으로 나뉘어지고 서로 다른 그룹의 정점만이 간선으로 연결된 그래프를 말한다.

 

👻 이분그래프의 특징

• 이분 그래프인지 확인하기 위해서는 BFS와 DFS 탐색 방법을 이용할 수 있다. DFS와 BFS를 통해서 그래프를 탐색하게 되면, 같은 depth에 있는 정점은 같은 색을 갖게 되는 것이다.
• 연결 요소의 개수를 구하는 방법과 유사하다.
• 모든 정점을 방문해서 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.

 

🧑🏻‍💻 이분그래프인지 확인해보는 방법

⚠️ 주의사항: 서로 인접한 정점이 같은색으로 칠해지면 이분그래프가 아니다
⚠️ 주의사항: 연결그래프, 비연결그래프 모두 고려해야한다. 비연결인 경우, 모든 정점에 대해서 확인작업이 필요하다. 

1. 그래프 탐색 알고리즘을 적용해서 (DFS, BFS) 그래프를 탐색할 때마다 다른 두 색을 칠한다.
2. 방문한 노드를 기준으로, 그 노드와 인접한 노드는 다른색으로 칠해준다.
3. 이렇게 생성된 그래프에서 탐색을 진행할 때 인접한 노드의 색이 현재 노드와 동일한 색상이게 되면, 이분그래프가 아니게 된다. BFS인 경우, 노드를 방문하다가 만약 같은 레벨에서의 노드를 다른색으로 칠해야하면 이는 이분 그래프가 아니게 된다.
4. 최종적으로 모든 노드를 방문했는데 이러한 경우가 없다면, 이분그래프이다.

 

💻 이분그래프인지 아닌지 확인하는 대표 예시 - 가장 유명한 백준 1707 문제

https://didu-story.tistory.com/272

[백준] (Swift) 1707번 - 이분그래프 (DFS로 풀기!)