無向グラフにBFSを使用したサイクルが含まれているかどうかを確認するPythonプログラム

ツリーのすべてのノードの合計を見つける必要がある場合は、クラスが作成されます。このクラスには、ルートノードの設定、ツリーへの要素の追加、特定の要素の検索、およびツリーの要素の追加を行うためのメソッドが含まれています。合計などを見つけます。これらのメソッドにアクセスして使用するために、クラスのインスタンスを作成できます。

以下は同じのデモンストレーションです-

例

from collections import deque

def add_edge(adj: list, u, v):
   adj[u].append(v)
   adj[v].append(u)

def detect_cycle(adj: list, s, V, visited: list):

   parent = [-1] * V

   q = deque()

   visited[s] = True
   q.append(s)

   while q != []:

      u = q.pop()

      for v in adj[u]:
         if not visited[v]:
            visited[v] = True
            q.append(v)
            parent[v] = u
         elif parent[u] != v:
            return True
   return False

def cycle_disconnected(adj: list, V):

   visited = [False] * V

   for i in range(V):
      if not visited[i] and detect_cycle(adj, i, V, visited):
         return True
   return False

if __name__ == "__main__":
   V = 5
   adj = [[] for i in range(V)]
   add_edge(adj, 0, 1)
   add_edge(adj, 1, 2)
   add_edge(adj, 2, 0)
   add_edge(adj, 2, 3)
   add_edge(adj, 2, 1)

   if cycle_disconnected(adj, V):
      print("There are 5 vertices in the graph")
      print("0-->1")
      print("1-->2")
      print("2-->0")
      print("2-->3")
      print("2-->1")
      print("Is there a cycle ?")
      print("Yes")
   else:
      print("There are 5 vertices in the graph")
      print("0-->1")
      print("1-->2")
      print("2-->0")
      print("2-->3")
      print("2-->1")
      print("Is there a cycle ?")
      print("Yes")
      print("No")

出力

There are 5 vertices in the graph
0-->1
1-->2
2-->0
2-->3
2-->1
Is there a cycle ?
Yes

説明

• 必要なパッケージがインポートされます。

• グラフにノードを追加するのに役立つ「add_edge」という名前の別のメソッドが定義されています。

• グラフのコンポーネントが接続されたときにサイクルが形成されるかどうかを判断するのに役立つ「detect_cycle」という名前のメソッドが定義されています。

• 「cycle_disconnected」という名前の別のメソッドが定義されており、サイクルが接続されているかどうかを判断するのに役立ちます。

• 「add_edge」メソッドを使用して要素がグラフに追加されます。

• コンソールに表示されます。

• 「cycle_disconnected」メソッドが呼び出され、出力がコンソールに表示されます。