python-3.x - 使用 Networkx 在 Python 中查找 1 跳、2 跳、...、k 跳邻居

Question

我正在尝试使用 nx 在图中找到一些特定节点(比方说 l 节点)的 1 跳、2 跳，如果需要，k 跳邻居。 single_source_dijkstra_path_length.

1. 每个步骤的时间复杂度是多少(1-hop，2-hop，...)，以及
2. 有没有更快的算法？

Answer 1

如果你正在查看未加权的图，你可以使用广度优先搜索，小 k 的时间复杂度应该是平均 O(<k>^k) , 其中<k>是所考虑图的平均度数。

如果您想在加权图中计算多个距离，您应该使用 multi_source_dijkstra_path_length .我不确定这个算法有哪个运行时，但与 Dijkstra 的多次运行相比，它可能是一个改进，它有 O(|V|log(|V|)+|E|) (取决于实现)。

如果您想在加权图中使用最大距离阈值，它可能取决于边上的权重分布以及最小或平均边权重，这会影响计算达到阈值所需的节点数。