C++プログラムでDFSを使用して特定のグラフが2部グラフであるかどうかを確認します

連結グラフがあるとします。グラフが2部グラフであるかどうかを確認する必要があります。セット内のノードが同じ色で着色されるように、2つの色を適用してグラフ彩色が可能な場合。

したがって、入力が次のような場合

その場合、出力はTrueになります

これを解決するには、次の手順に従います-

• 関数insert_edge（）を定義します。これは、エッジ配列adj、u、v、
を取ります。
• adj [u]
の最後にvを挿入します
• 形容詞の最後にuを挿入[v]
• メインの方法から、次の手順を実行します。
• adj [v]の各uについて、do
  • visited [u]がfalseと同じ場合、-
    • visited [u]：=true
    • color [u]：=色の反転[v]
    • is_bipartite_graph（adj、u、visited、color）でない場合は、-
      • falseを返す
  • それ以外の場合、color[u]がcolor[v]と同じである場合、-
    • falseを返す
• trueを返す

例（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);

出力

1