加速网络中的随机最小生成树？

Question

这里有一些代码，它的目标是使用贪婪和随机的边权来构建一个随机生成树。它跑得比我想的慢得多。有什么方法可以加快速度吗？

随机生成权值和最小生成树的抽样都是缓慢的。第一种情况对我来说特别奇怪，因为只有179400条边，np.random.uniform(0,1,179400)执行得很快。

(这里慢的意思是秒的顺序。)

(我很乐意使用networkx以外的其他东西，但这并不可取。)

import numpy as np
import networkx as nx

graph = nx.grid_graph([300, 300])

for edge in graph.edges():
    graph.edges[edge]["weight"] = np.random.uniform(0, 1)

tree = nx.minimum_spanning_tree(graph)

Answer 1

如果在测试中批量生成随机数更快，那么就这样做吧。

rand = np.random.uniform(0, 1, graph.edges.size())
i = 0
for edge in graph.edges():
    graph.edges[edge]["weight"] = rand[i]
    i += 1