[Algorithm/Graph] 이분 그래프(bipartite graph) 판별하기

이분 그래프란?

• 정점을 두 개의 집합으로 나눌 수 있는 그래프
• 그래프의 모든 에지는 서로 다른 집합에 속한 정점끼리 연결되어야 한다.
• ex) 학생 목록과 수업 목록을 모델링하는 경우
• ex) 스트리핑 플랫폼에서 영화 목록과 시청자 사이의 관계를 모델링하는 경우
• 최대 매칭 또는 최소 정점 커버 문제와 같은 NP-완전 문제들이 이분 그래프에서는 다항시간으로 풀 수 있다.
  • 따라서 주어진 그래프가 이분 그래프인지 아닌지 판별하는 것은 매우 중요하다

 

이분 그래프의 구현

DFS를 변형하여 만들 수 있다.

1. 1번 정점부터 DFS를 시작한다고 가정한다(1번 정점을 스택에 추가한다)
2. 스택에 방문하지 않은 정점이 남아있다면 스택에서 정점을 하나 꺼내고 이를 현재 정점으로 설정한다
3. 이전 정점에 할당된 색상이 검은색이면 현재 정점에 빨간색을 할당한다. 반대로 이전 정점에 할당된 색상이 빨간색이면 현재 정점에 검은색을 할당한다
4. 현재 정점과 인접한 정점들 중에 아직 방문하지 않은 정점들을 스택에 넣고, 현재 정점을 방문한 것으로 설정한다
5. 모든 정점이 색상이 지정될 때 까지 2~4단계를 반복한다. 알고리즘 종료 시 모든 정점에 색상이 칠해져 있다면 이 그래프는 이분 그래프이다.
6. 만약 탐색을 진행하다가 만나게 된 정점이 이미 방문한 정점이고, 이 정점의 색상이 현재 할당할 색상과 다른 색상이면 알고리즘을 종료하고, 해당 그래프가 이분 그래프가 아니라고 판별한다.

C++ 코드

template <typename T>
auto bipartite_check(const Graph<T>& G)
{
	stack<unsigned> stack;
	set<unsigned> visited;	// 방문한 정점
	stack.push(1);  		// 1번 정점부터 시작

	enum class colors { NONE, BLACK, RED };
	colors current_color { colors::BLACK }; // 다음 정점에 칠할 색상

	vector<colors> vertex_colors(G.vertices(), colors::NONE);

	while (!stack.empty())
	{
		auto current_vertex = stack.top();
		stack.pop();

		// 현재 정점을 이전에 방문하지 않았다면
		if (visited.find(current_vertex) == visited.end())
		{
			visited.insert(current_vertex);
			vertex_colors[current_vertex] = current_color;

			if (current_color == colors::RED)
			{
				cout << current_vertex << "번 정점: 빨간색" << endl;
				current_color = colors::BLACK;
			}
			else
			{
				cout << current_vertex << "번 정점: 검정색" << endl;
				current_color = colors::RED;
			}

			// 인접한 정점 중에서 방문하지 않은 정점이 있다면 스택에 추가
			for (auto e : G.edges(current_vertex))
				if (visited.find(e.dst) == visited.end())
					stack.push(e.dst);
		}
		// 현재 정점이 이미 방문한 정점이고, 
		// 현재 칠할 색상과 같은 색상이 칠해져 있다면 이분 그래프가 아님.
		else if (vertex_colors[current_vertex] != colors::NONE &&
			vertex_colors[current_vertex] != current_color)
			return false;
	}

	// 모든 정점에 색상이 칠해졌으면 이분 그래프가 맞음
	return true;
}