时间戳

首页 > 解决方案 > 是否可以使用邻居数组执行广度优先搜索？

python - 是否可以使用邻居数组执行广度优先搜索？

问题描述

程序的输入是这样的：

1 2
2 3
2 5
5 1
3 4
4 5
4 6

第一个数字代表顶点一，第二个数字代表顶点2。这意味着有一条边连接两个顶点，这意味着它们是邻居。1 [我的问题是，是否可以仅使用邻居列表执行 BFS？或者我需要将数据转换成图表吗？

任何帮助，将不胜感激！

标签： pythonlistgraphnetworkxgraph-theory

解决方案

最简单的方法是构建一个图表，并使用可用的算法。在 NetworkX foe 实例中，您有一组基本算法用于广度优先搜索nx.algorithms.traversal. 所以你可以这样做：

s = '''1 2
2 3
2 5
5 1
3 4
4 5
4 6'''

l = [i.split() for i in s.splitlines()]

然后从边列表构建一个图：

import networkx as nx

G = nx.from_edgelist(l)

并使用上述模块中的可用方法，例如从源头开始在广度优先搜索中迭代边缘：

list(nx.algorithms.traversal.breadth_first_search.bfs_edges(G, '2'))
# [('2', '1'), ('2', '3'), ('2', '5'), ('3', '4'), ('4', '6')]

推荐阅读