Example02 / 15
用广度优先搜索（BFS）求最短路径距离
用队列实现 BFS，求从源点 0 到所有节点的距离，并与 NetworkX 的结果对比； 按距离把节点分层输出，可以看到 BFS “一层一层”向外扩散。 最后计算整个网络的直径与平均路径长度（空手道网络是连通的，可直接计算）。 输出：自己的结果与 NetworkX 完全一致；直径为 5，平均路径长度约 2.41。
Output输出图
Output文字输出
与 NetworkX 一致吗？ True 距离 0 的节点: [0] 距离 1 的节点: [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31] 距离 2 的节点: [9, 16, 24, 25, 27, 28, 30, 32, 33] 距离 3 的节点: [14, 15, 18, 20, 22, 23, 26, 29] 直径 = 5 ，平均路径长度 = 2.408
Code代码
# 用队列实现 BFS，求从源点 0 到所有节点的距离，并与 NetworkX 的结果对比；
# 按距离把节点分层输出，可以看到 BFS “一层一层”向外扩散。
# 最后计算整个网络的直径与平均路径长度（空手道网络是连通的，可直接计算）。
# 输出：自己的结果与 NetworkX 完全一致；直径为 5，平均路径长度约 2.41。
import networkx as nx
from collections import deque
G = nx.karate_club_graph()
def bfs_distances(G, source):
dist = {source: 0}
queue = deque([source])
while queue:
v = queue.popleft()
for u in G.neighbors(v):
if u not in dist:
dist[u] = dist[v] + 1
queue.append(u)
return dist
my = bfs_distances(G, 0)
ref = nx.single_source_shortest_path_length(G, 0)
print("与 NetworkX 一致吗？", my == dict(ref))
layers = {}
for node, d in my.items():
layers.setdefault(d, []).append(node)
for d in sorted(layers):
print("距离 %d 的节点: %s" % (d, sorted(layers[d])))
print("直径 =", nx.diameter(G), "，平均路径长度 = %.3f" % nx.average_shortest_path_length(G))
# 作图：节点按到源点 0 的 BFS 距离着色，可见“一层一层”向外扩散
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(6.4, 4.2))
pos = nx.spring_layout(G, seed=4)
nx.draw_networkx_edges(G, pos, ax=ax, edge_color="0.7", alpha=0.4)
nc = nx.draw_networkx_nodes(G, pos, ax=ax, node_color=[my[v] for v in G], cmap=plt.get_cmap("viridis_r", max(my.values()) + 1), vmin=-0.5, vmax=max(my.values()) + 0.5,
node_size=[200 if v == 0 else 90 for v in G], edgecolors="0.3", linewidths=0.5)
fig.colorbar(nc, ax=ax, ticks=range(max(my.values()) + 1), label="BFS distance from node 0")
ax.set_title("BFS layers from node 0 (diameter = %d)" % nx.diameter(G))
ax.axis("off"); plt.tight_layout(); plt.show()Run在浏览器中运行
首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。