设G(V,E)
为无向无权图r
为V
的子集。现在,节点root
被添加到G
,并且在root
和r
的所有节点之间添加边。现在,对于V-r
的每个节点,我想使用BFS查找最近的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
节点在这个问题中的作用。我认为,解决这个问题最简单的方法是,从所有V-r
节点调用bfs
。每次,当您能够到达属于r
的节点时,都会返回它。因为它是属于r
的第一个可到达节点。以下是此过程的示例:因为
erdos_renyi
是一个随机图,所以它可以在不同的运行中给出不同的结果。以下是一个示例输出:您甚至可以进一步优化此解决方案。首先,为
V-r
节点创建一个列表,该列表将存储从r
节点到达该节点的最短距离。使用一些较大的(即无限)值初始化此列表。现在,不必为每个V-r
节点调用bfs
,您可以从所有r
节点调用bfs,并在可能的情况下更新距离列表。通过这个过程,如果len(r) << len(V-r)
,您对bfs
的调用将更少。我希望这能解决你的问题相关问题 更多 >
编程相关推荐