TY_IT💻

이분그래프 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프 이분 그래프인지 확인하는 방법 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용 → 서로 인접한 정점이 같은 색이면 이분 그래프 X 1. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다. 2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다. 3. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다. 4. BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다. ※ 이..

복습 그래프: 노드와 노드 사이에 연결된 간선 정보를 가지고 있는 자료구조 서로 다른 개체가 연결되어 있다 --> 가장 먼저 그래프 알고리즘 떠올려야함. [그래프와 트리 자료구조 비교] 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노트 X 루트 노드 존재 노드 간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 그래프의 구현 방법 1. 인접 행렬(Adjacency Matrix): 2차원 배열 사용 2. 인접 리스트(Adjacency List): 리스트 사용 노드의 개수가 V, 간선의 개수가 E인 경우 인접 행렬과 인접리스트 구현 비교 인접행렬 이용 인접리스트 이용 간선 정보 저장 O(V^2)..