C++ 프로그램에서 DFS를 사용하여 주어진 그래프가 Bipartite인지 확인

<시간/>

연결된 그래프가 있다고 가정합니다. 그래프가 이분법인지 여부를 확인해야 합니다. 그래프 채색이 가능한 경우 2가지 색을 적용하여 집합의 노드가 같은 색으로 채색되도록 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 True

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

insert_edge() 함수를 정의하면 가장자리 배열 adj, u, v,
adj[u] 끝에 v 삽입
adj[v] 끝에 u를 삽입
주요 방법에서 다음을 수행합니다.
adj[v]의 각 u에 대해, do
- 방문한[u]가 false와 같으면 -
  - 방문함[u] :=사실
  - color[u] :=색상 반전[v]
  - is_bipartite_graph(adj, u, 방문, 색상)가 아니면 -
    - 거짓 반환
- 그렇지 않으면 color[u]가 color[v]와 같을 때 -
  - 거짓 반환
참을 반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void insert_edge(vector<int> adj[], int u, int v){
   adj[u].push_back(v);
   adj[v].push_back(u);
}
bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
   for (int u : adj[v]) {
      if (visited[u] == false) {
         visited[u] = true;
         color[u] = !color[v];
         if (!is_bipartite_graph(adj, u, visited, color))
            return false;
      }
      else if (color[u] == color[v])
      return false;
   }
   return true;
}
int main() {
   int N = 6;
   vector<int> adj_list[N + 1];
   vector<bool> visited(N + 1);
   vector<int> color(N + 1);
   insert_edge(adj_list, 1, 2);
   insert_edge(adj_list, 2, 3);
   insert_edge(adj_list, 3, 4);
   insert_edge(adj_list, 4, 5);
   insert_edge(adj_list, 5, 6);
   insert_edge(adj_list, 6, 1);
   visited[1] = true;
   color[1] = 0;
   cout << (is_bipartite_graph(adj_list, 1, visited, color));
}

입력

insert_edge(adj_list, 1, 2);
insert_edge(adj_list, 2, 3);
insert_edge(adj_list, 3, 4);
insert_edge(adj_list, 4, 5);
insert_edge(adj_list, 5, 6);
insert_edge(adj_list, 6, 1);