如何在广度优先树中存储节点到根的距离？

Question

设G(V,E)为无向图。我想从 G 存储与根有相应距离的节点创建广度优先树。请帮忙

import networkx as nx

g=nx.erdos_renyi_graph(12,.1)
visited = [] 
queue = []     
tree={}
def bfs(visited, g, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0)
    tree[s]=[]
    for neighbour in list(g.adj[s]):
      if neighbour not in visited:
        visited.append(neighbour)
        tree[s].append(neighbour)
        queue.append(neighbour)

bfs(visited, g, 1)
print(tree)

Answer 1

您可以将每个项目保留为 (node, distance) 并附加 (neighbour, distance+1)

import matplotlib.pyplot as plt
import networkx as nx

# --- functions ---

def bfs(g, node):
    distance = 0
    visited = [node]
    queue = [(node, distance)]

    tree = {}

    while queue:
        s, distance = queue.pop(0)
        tree[s] = []
        for neighbour in list(g.adj[s]):
            if neighbour not in visited:
                visited.append(neighbour)
                tree[s].append((neighbour, distance+1))
                queue.append((neighbour, distance+1))

    return tree
  
# --- main ---

#G = nx.erdos_renyi_graph(12, .1)
G = nx.Graph()
G.add_edges_from(([1,2],[2,3], [2,4], [3, 5], [4,5]))

tree = bfs(G, 1)
print(tree)

nx.draw(G, with_labels=True)
plt.show()

结果（手动重新格式化）：

{
  1: [(2, 1)], 
  2: [(3, 2), (4, 2)], 
  3: [(5, 3)], 
  4: [], 
  5: []
}

对于图表

最终你甚至可以使用 tree[(s, distance)]

def bfs(g, node):
    distance = 0
    visited = [node]
    queue = [(node, distance)]

    tree = {}

    while queue:
        s, distance = queue.pop(0)
        tree[(s, distance)] = []
        for neighbour in list(g.adj[s]):
            if neighbour not in visited:
                visited.append(neighbour)
                tree[(s, distance)].append((neighbour, distance+1))
                queue.append((neighbour, distance+1))

    return tree

结果（手动重新格式化）：

{
  (1, 0): [(2, 1)], 
  (2, 1): [(3, 2), (4, 2)], 
  (3, 2): [(5, 3)], 
  (4, 2): [], 
  (5, 3): []
}

顺便说一句：

我正在考虑使用 json.dumps(tree, indent=2) 自动重新格式化结果，但它无法将 node 转换为 json。

但是pretty printer可以用类似的方式格式化

import pprint
pprint.pprint(tree, indent=2)

结果：

{ (1, 0): [(2, 1)],
  (2, 1): [(3, 2), (4, 2)],
  (3, 2): [(5, 3)],
  (4, 2): [],
  (5, 3): []}

如何在广度优先树中存储节点到根的距离？

How to store distances of nodes from root in breadth-first tree?

python

tree

graph-theory

graph-algorithm