이분 그래프 : 모든 정점을 두 가지 색으로 칠하되, 모든 간선이 두 가지 색의 정점을 포함하도록 색칠할 수 있는 그래프
이분 그래프 판별:
1. 그래프를 BFS or DFS로 탐색하며, 색을 이웃과 다른 색으로 계속 칠한다.
2. 자신과 인접한 정점의 색이 자신과 같으면 이분 그래프가 아니다.
-연결 그래프일 경우, 정점 하나를 시작으로 탐색을 한 번만 마친 후, 판별할 수 있지만
비연결 그래프일 경우, 모든 정점을 탐색해 판별해야한다.
'컴퓨터 사이언스 > 자료구조와 알고리즘' 카테고리의 다른 글
| [Greedy] 최소 신장 트리(Minimum Spanning Tree) (0) | 2021.04.29 |
|---|---|
| [정렬] 거품 정렬, 선택 정렬, 삽입 정렬 (0) | 2021.04.29 |
| [트리] 전위(Preorder), 중위(Inorder), 후위(Postorder) (0) | 2021.04.17 |
| [정렬] Quick Sort Algorithm depend on Pivot Selecting (0) | 2021.04.12 |
