Python程序，用于在图形中使用BFS查找可从节点到达的所有节点

  • Z时代
  • 2024-01-10
  • 分类：综合

当需要查找树的所有节点的总和时，将创建一个类，该类包含设置根节点，向树中添加元素，搜索特定元素以及将树中的元素添加至的方法。找到总和，依此类推。可以创建该类的实例来访问和使用这些方法。

以下是相同的演示-

示例

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("来自的可达节点 ", 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)

输出结果

来自的可达节点 2 are
2 1 3 4
来自的可达节点 4 are
2 1 3 4
来自的可达节点 5 are
5 6 7
来自的可达节点 7 are
5 6 7

解释

  • 所需的软件包已导入。

  • 定义了一个名为“ add_edge”的方法，该方法有助于将元素添加到树中。

  • “ BFS_operation”方法有助于使用广度优先搜索方法遍历树。

  • 定义了一个名为“ displayReachableNodes”的方法，该方法有助于显示可以从特定节点访问的节点。

  • 定义了一个名为“ findReachableNodes”的方法，该方法遍历节点，并对元素执行“ BFS_operation”。

  • 'add_edge'方法将节点添加到图中。

  • 列表已定义并显示在控制台上。

  • 调用该方法，并在控制台上显示输出。

以上是 Python程序，用于在图形中使用BFS查找可从节点到达的所有节点 的全部内容， 来源链接： utcz.com/z/360150.html

回到顶部