极客教程Python程序：使用BFS在图中查找可到达节点达到从节点
当需要找到树的所有节点的和时，会创建一个类，其中包含设置根节点，向树添加元素，搜索特定元素，添加树的元素以查找总和等方法。可以创建类的实例以访问和使用这些方法。
以下是相同的演示−
更多Python相关文章，请阅读：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’方法添加节点到图中。
-
定义列表并在控制台上显示。
-
调用方法并在控制台上显示输出结果。