이분 그래프1 이분 그래프 (Bipartite graph) 이분 그래프 (Bipartite graph) 1. 그래프란? 정점(vertice, node)과 간선(edge)으로 이루어진 자료구조를 그래프이라 한다. 트리도 그래프의 한 종류에 해당하지만, 그래프는 보다 더 유연한 방식으로 데이터 간의 관계를 표현할 수 있다. 2. 이분 그래프(Bipartite graph)란? 이분 그래프는 인접한 정점에 다른 색을 칠할 때, 모든 정점에 대해 2가지 색만으로 칠할 수 있는 그래프이다. 3. 이분 그래프 탐색 방법 1단계. 그래프를 DFS나 BFS로 탐색한다. 2단계. 색을 이웃과 다른 색으로 설정한다. 3단계. 자신과 인접한 정점의 색이 같을 경우, 이분 그래프가 될 수 없다. - 24.03.18 LAB meeting - 랩 미팅 중 생소했던 개념을 정리한 글입니다. 2024. 3. 19. 이전 1 다음