이분 그래프

이분 그래프

이분 그래프의 개념

출처 - https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

• 인접한 정점끼리 서로 다른색으로 칠했을때 모든 정점을 두가지 색으로만 칠할 수 있는 그래프
  • 잘 이해가 안간다면 그림을 살펴보자.
• BFS,DFS 모두 이용해서 구현할수 있다.

이분 그래프 코드

bool check(int v) {
    queue<int> que;
    for (int i = 1; i <= v; i++) {
        if (visited[i] != 0) continue; // 이미 결정된 노드는 큐에 넣지 않음
        que.push(i);
        visited[i] = 1;

        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (int j = 0; j < vec[x].size(); j++) {
                int next = vec[x][j];
                if (visited[next] == 0) {
                    que.push(next);
                    visited[next] = visited[x] * -1;
                }
                else if (visited[next] == visited[x]) {
                    return false; // 이분 그래프가 아닐 경우
                }
            }
        }
    }
    
    return true; // 이분 그래프일 경우
}

백준 1707번 문제의 코드 일부이다.

• 우선 for 문을 이용해 모든 정점들을 확인하고, 이미 방문한 정점은 continue를 통해 넘어간다.
• 정점을 방문하면 queue에 push를 하고 visited값을 true로 변경한다.
• 이후 큐가 empty가 될떄까지(해당 시작 노드와 연결된 모든 노드를 방문 할때까지) 해당 노드와 연결된 노드를 방문한다.
• 이때 해당 노드를 방문을 안했다면 -> if (visited[next] == 0) , queue에 push를 하고 visited[next] = visited[x] * -1;
  • visited[next] = visited[x] * -1; 이 코드의 의미는 -1 를 곱해줌으로써 1과 -1이 반복되게 만들어준다.
• 만약 해당 노드를 이미 방문 했는데  visited[next] == visited[x] 일 경우, 이분그래프가 아니라는 의미의 false를 리턴한다.
  • visited[next] == visited[x]의 의미는 상위 노드와 값이 동일할경우를 의미하는데 즉 연결된 노드의 값이(색이) 동일한 경우를 말하고 이는 이분 그래프가 아니라는 뜻이므로 false를 리턴한다.
• 모든 조건문을 이상 없이 통과하면 이분 그래프라는 의미의 true를 리턴한다.

 

정리