[그래프] 이분 그래프(Bipartite Graph)

📌 시간 복잡도

O(V + E)
V → 정점 개수
E → 간선 개수

📌 구현(DFS)

1.
colors(boolean[]) & seen(HashSet) 을 준비한다.
2.
그래프의 모든 노드를 순회한다.
for → graph:key
3.
seen에 해당 노드가 있으면 continue
if → seend contains → continue
4.
Stack을 준비한다.
5.
해당 시작 노드의 색깔을 정한다, stackseen에 넣는다.
colors[node] = 1
stack → add
seen → add
6.
Stack 에서 하나씩 꺼낸다.
while → pop
7.
꺼낸 노드와 연결된 노드를 순회한다.
for → connected node
8.
연결된 노드가 seen에 존재 O → 현재 노드와 같은 색인지 확인해서 실패 여부 확인
if → seen contains
if (curColor == color) → false 실패!
9.
연결된 노드가 seen에 존재 Xstack과 seen에 넣고, 현재 색깔과 반대로 넣는다.
else
stack → add
seen add
color[child] = !curColor

📌 참고 자료

TOP