이분그래프1 이분 그래프 (Bipartite Graph) 이분 그래프 (Bipartite Graph) 이분그래프는 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 뜻한다. 다시 말해, 그래프의 모든 정점이 두그룹으로 나뉘어져있고 같은 그룹끼리는 인접하지 않은 그래프이다. 이분그래프를 확인하는 방법은 BFS 나 DFS를 이용한다. 1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색을 칠한다. 2. 각 정점을 방문 중, 자신과 인접한 정점의 색이 자신과 같다면 그 그래프는 이분 그래프가 아니다. (발견과 동시에 BFS 종료) 3. 모든 정점을 방문하고 인접한 정점끼리 같은색이 없다면 이분그래프이다. 특징) 모든 정점을 방문하기 때문에 시간 복잡도는 O (V+E) 이다. 아래의 코드는 백준사이트의 이분그래프를 풀면서 BFS.. 2021. 3. 6. 이전 1 다음
