与えられたグラフがPythonで2部グラフであるかどうかをチェックするプログラム

無向グラフが1つあるとすると、グラフが2部グラフであるかどうかを確認する必要があります。グラフのすべてのエッジ{u、v}がAに1つのノードuを持ち、Bに別のノードvを持つように、グラフのノードを2つのセットAとBに分割できる場合、グラフは2部グラフであることがわかります。

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

次に、出力はTrueになり、[0,4]はセットAにあり、[1,2,3]はセットBにあり、すべてのエッジはAからAまたはBからBではなく、AからBまたはBからAになります。 。

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

• 関数dfs（）を定義します。これはソースを取ります

• グラフ[ソース]の頂点ごとに、実行

  • color [vertex]が-1と同じでない場合、

    • color[vertex]がcolor[source]と同じ場合、

      • result [0]：=False

      • 戻る

    • 次のイテレーションに行く

  • color [vertex]：=1 --color [source]

  • dfs（vertex）

• メインの方法から、次のようにします-

• n：=arrのサイズ

• グラフ：=頂点0からn-1の空の隣接リスト

• 0からnの範囲のiの場合、実行

  • arr [i]のjごとに、実行

    • iをグラフに挿入[j]

    • jをグラフに挿入[i]

  • color：=サイズnのリストで、-1で塗りつぶします

  • 結果：=1つの真の値を持つリスト

• 0からnの範囲のiの場合、実行

  • color [i]が-1と同じ場合、

  • dfs（i）

• 結果を返す[0]

理解を深めるために、次の実装を見てみましょう-

例

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      graph = [set() for i in range(n)]
      for i in range(n):
         for j in arr[i]:
            graph[j].add(i)
            graph[i].add(j)
      color = [-1] * n
      result = [True]
      def dfs(source):
      for child in graph[source]:
         if color[child] != -1:
            if color[child] == color[source]:
               result[0] = False
               return
            continue
      color[child] = 1 - color[source]
      dfs(child)
   for i in range(n):
      if color[i] == -1:
      dfs(i)
   return result[0]
ob = Solution()
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
print(ob.solve(graph))

入力

graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]

出力

True