python - 如何使用 BFS 找到最近的节点?
问题描述
让G(V,E)
是一个无向无权图并且r
是 的一个子集V
。现在节点root
被添加到并且在所有节点G
之间添加边。现在对于我想找到使用 BFS 的最近节点的每个节点。请帮忙。我已经尝试了以下代码。root
r
V-r
r
import networkx as nx
import matplotlib.pyplot as plt
def bfs(g, node):
dist = 0
visited = [node]
queue = [(node, dist)]
tr = {}
while queue:
s, dist = queue.pop(0)
tr[s] = []
for nbr in list(g.adj[s]):
if nbr not in visited:
visited.append(nbr)
tr[s].append(nbr, dist+1)
queue.append((nbr, dist+1))
return tr
G=nx.erdos_renyi_graph(50,0.1)
r=[5,8,36,43,21]
G.add_node('root')
for i in r:
G.add_edge(i,'root')
t = bfs(G, 'root')
print(t)
解决方案
我不明白root
这个问题中节点的目的。我认为,解决此问题的最简单方法是bfs
从所有V-r
节点调用。每次,当您能够到达属于 的节点时r
,您将其返回。因为它是属于 的第一个可达节点r
。这是此过程的示例:
import networkx as nx
import matplotlib.pyplot as plt
def bfs(g, node, r):
dist = 0
visited = [node]
queue = [(node, dist)]
#tr = {}
while queue:
s, dist = queue.pop(0)
#tr[s] = []
for nbr in list(g.adj[s]):
if nbr not in visited:
if nbr in r:
return (nbr, dist+1)
visited.append(nbr)
#tr[s].append((nbr, dist+1))
queue.append((nbr, dist+1))
#return tr
return (NaN, NaN)
G=nx.erdos_renyi_graph(50,0.1)
r=[5,8,36,43,21]
G.add_node('root')
for i in r:
G.add_edge(i,'root')
for n in list(G.nodes):
if n not in r:
t, d = bfs(G, n, r)
print("Node {}'s nearest node in r: {} with distance: {}".format(n, t, d))
由于erdos_renyi
是随机图,因此它可以在不同的运行中给出不同的结果。这是一个示例输出:
Node 0's nearest node in r: 5 with distance: 2
Node 1's nearest node in r: 8 with distance: 1
Node 2's nearest node in r: 43 with distance: 2
Node 3's nearest node in r: 36 with distance: 2
Node 4's nearest node in r: 36 with distance: 2
Node 6's nearest node in r: 5 with distance: 2
Node 7's nearest node in r: 36 with distance: 2
Node 9's nearest node in r: 36 with distance: 1
Node 10's nearest node in r: 36 with distance: 2
Node 11's nearest node in r: 8 with distance: 2
Node 12's nearest node in r: 8 with distance: 3
Node 13's nearest node in r: 8 with distance: 2
Node 14's nearest node in r: 8 with distance: 2
Node 15's nearest node in r: 36 with distance: 3
Node 16's nearest node in r: 36 with distance: 3
Node 17's nearest node in r: 8 with distance: 1
Node 18's nearest node in r: 8 with distance: 1
Node 19's nearest node in r: 8 with distance: 1
Node 20's nearest node in r: 21 with distance: 1
Node 22's nearest node in r: 36 with distance: 2
Node 23's nearest node in r: 21 with distance: 2
Node 24's nearest node in r: 21 with distance: 1
Node 25's nearest node in r: 5 with distance: 1
Node 26's nearest node in r: 5 with distance: 1
Node 27's nearest node in r: 36 with distance: 3
Node 28's nearest node in r: 36 with distance: 2
Node 29's nearest node in r: 5 with distance: 1
Node 30's nearest node in r: 21 with distance: 1
Node 31's nearest node in r: 43 with distance: 1
Node 32's nearest node in r: 36 with distance: 3
Node 33's nearest node in r: 5 with distance: 2
Node 34's nearest node in r: 8 with distance: 2
Node 35's nearest node in r: 36 with distance: 2
Node 37's nearest node in r: 36 with distance: 3
Node 38's nearest node in r: 43 with distance: 1
Node 39's nearest node in r: 8 with distance: 2
Node 40's nearest node in r: 43 with distance: 1
Node 41's nearest node in r: 43 with distance: 2
Node 42's nearest node in r: 8 with distance: 2
Node 44's nearest node in r: 43 with distance: 2
Node 45's nearest node in r: 43 with distance: 2
Node 46's nearest node in r: 5 with distance: 2
Node 47's nearest node in r: 8 with distance: 1
Node 48's nearest node in r: 36 with distance: 1
Node 49's nearest node in r: 5 with distance: 2
Node root's nearest node in r: 5 with distance: 1
您甚至可以进一步优化此解决方案。首先,为节点创建一个列表,该列表V-r
将存储从节点到该节点的最短距离r
。用一些大的(即无限的)值初始化这个列表。现在,您可以从所有节点调用 bfs并在可能的情况下更新距离列表,而不是调用bfs
每个节点。通过这个过程,您将减少对if的调用。我希望这能解决你的问题。V-r
r
bfs
len(r) << len(V-r)
推荐阅读
- python - 使用本机不和谐表情符号而不是自定义不和谐表情符号(python)实现角色反应
- c++ - 为什么我收到很多错误?
- python - 如何在 MacO 上对 python3 应用安全更新
- pandas - 如何在 Webscraping 大数据期间摆脱 ConnectionError?
- python-3.x - 尝试安装 pygame “不支持的轮子”错误
- powershell - Powershell下后台运行docker
- css - React Dev Tool 将组件显示为单个字母
- angular - 如果在 Angular 中单击提交时未选中,则显示单选框的验证错误
- c - 查看十六进制数字的特定位?
- compression - 如何在一个可靠的存档中压缩多个文件,但快速只提取一个?