자료구조 이분그래프1 [자료구조] 이분 그래프(Bipartite Graph)란 ? 이분 그래프의 개념이분 그래프(Bipartite Graph)는 정점을 두 개의 집합으로 나눌 수 있고, 같은 집합에 속한 정점끼리는 간선이 연결되지 않는 그래프입니다. 즉, 모든 간선이 한 집합의 정점에서 다른 집합의 정점으로만 연결됩니다이분 그래프의 특징- 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.- 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 모조건 같은 색으로 칠해진다.- 사이클의 길이가 홀수이면 이분 그래프가 아니다. (예: 3개의 정점으로 이루어진 삼각형(사이클 길이 3)은 이분 그래프가 아니다)- 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.- 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래.. 2025. 5. 8. 이전 1 다음
