グラフでBFSを使用してノードから到達可能なすべてのノードを検索するPythonプログラム

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

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

例

from collections import deque

def add_edge(v, w):

   global visited_node, adj
   adj[v].append(w)
   adj[w].append(v)

def BFS_operation(component_num, src):

   global visited_node, adj
   queue = deque()

   queue.append(src)

   visited_node[src] = 1
   reachableNodes = []

   while (len(queue) > 0):

      u = queue.popleft()
      reachableNodes.append(u)
      for itr in adj[u]:
         if (visited_node[itr] == 0):

            visited_node[itr] = 1
            queue.append(itr)

   return reachableNodes

def displayReachableNodes(m):

   for i in m:
      print(i, end = " ")
   print()

def findReachableNodes(my_list, n):

   global V, adj, visited_node

   a = []

   component_num = 0

   for i in range(n):
      u = my_list[i]

      if (visited_node[u] == 0):
         component_num += 1

      a = BFS_operation(component_num, u)

   print("The reachable nodes from ", u, " are")
   displayReachableNodes(a)

V = 7
adj = [[] for i in range(V + 1)]
visited_node = [0 for i in range(V + 1)]
add_edge(1, 2)
add_edge(2, 3)
add_edge(3, 4)
add_edge(3, 1)
add_edge(5, 6)
add_edge(5, 7)

my_list = [ 2, 4, 5, 7 ]

arr_len = len(my_list)
findReachableNodes(my_list, arr_len)

出力

The reachable nodes from 2 are
2 1 3 4
The reachable nodes from 4 are
2 1 3 4
The reachable nodes from 5 are
5 6 7
The reachable nodes from 7 are
5 6 7

説明

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

• ツリーに要素を追加するのに役立つ「add_edge」という名前のメソッドが定義されています。

• 「BFS_operation」メソッドは、幅優先探索アプローチを使用してツリーをトラバースするのに役立ちます。

• 「displayReachableNodes」という名前のメソッドが定義されています。これは、特定のノードから到達できるノードを表示するのに役立ちます。

• 「findReachableNodes」という名前のメソッドが定義されており、ノードを反復処理し、要素に対して「BFS_operation」を実行します。

• 「add_edge」メソッドは、グラフにノードを追加します。

• リストが定義され、コンソールに表示されます。

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