对于图中的每个顶点，找到距离 d 内的所有顶点

Question

在我的特定情况下，该图表示为邻接列表，并且是无向且稀疏的，n 可以是数百万，d 是 3。计算 A^d （其中 A 是邻接矩阵）并挑选出非零条目有效，但我想要一些不涉及矩阵乘法的东西。对每个顶点进行广度优先搜索也是一种选择，但速度很慢。

Answer 1

def find_d(graph, start, st, d=0):

    if d == 0:
        st.add(start)
    else:
        st.add(start)
        for edge in graph[start]:
            find_d(graph, edge, st, d-1)

    return st

graph = { 1 : [2, 3],
      2 : [1, 4, 5, 6],
      3 : [1, 4],
      4 : [2, 3, 5],
      5 : [2, 4, 6],
      6 : [2, 5]
    }

print find_d(graph, 1, set(), 2)

Answer 2

假设我们有一个函数 verticesWithin(d,x)，它可以查找顶点 x 距离 d 内的所有顶点。

对于这样的问题，为了暴露缓存/记忆化机会，一个好的策略是提出一个问题：这个问题的子问题如何相互关联？

在这种情况下，我们可以看到verticesWithin(d,x) 如果 d >= 1 是所有 vertices(d-1,y[i]) 的并集i 在范围内，其中 y=verticesWithin(1,x)。如果d == 0那么它就是{x}。 （我假设一个顶点被认为与自身的距离为 0。）

在实践中，您需要查看 d == 1 情况的邻接表，而不是使用它关系，以避免无限循环。您还需要避免将 x 本身视为 y 的成员的冗余。

此外，如果 verticesWithin(d,x) 的返回类型从简单列表或集合更改为 d 集合列表，表示与 x 的距离增加，然后

verticesWithin(d,x) = init(verticesWithin(d+1,x))

其中 init 是生成列表所有元素的函数除了最后一个。显然，如果按字面转录成代码，这将是一个非终止递归关系，因此您必须对如何实现它有点聪明。

配备了子问题之间的这些关系，我们现在可以缓存 verticesWithin 的结果，并使用这些缓存的结果来避免执行冗余遍历（尽管以执行一些集合操作为代价 - 我不完全确保这是一场胜利）。我将把它作为练习来填写实现细节。

Answer 3

您已经提到了计算 A^d 的选项，但这比您需要的要多得多（正如您已经说过的那样）。

然而，有一种更便宜的方法可以使用这个想法。假设您有一个由 0 和 1 组成的（列）向量 v，表示一组顶点。现在，向量 w := A v 在每个节点上都有一个 1，从起始节点只需一步即可到达该向量。迭代时，u := A w 对于从起始节点只需两步即可到达的每个节点都有一个 1，等等。

对于 d=3，您可以执行以下操作以下（MATLAB 伪代码）：

v = j'th unit vector
w = v
for i = (1:d)
   v = A*v
   w = w + v
end

向量 w 现在对于每个节点都有一个正条目，可以从最多 d< 中的第 j 个节点进行访问/代码> 步骤。

Answer 4

在这种情况下，从给定顶点开始的广度优先搜索是最佳解决方案。你会找到距离 d 内的所有顶点，并且你永远不会访问距离 >= d + 2 的任何顶点。

这是递归代码，尽管如果需要的话，可以通过使用队列轻松消除递归。

// Returns a Set
Set<Node> getNodesWithinDist(Node x, int d)
{
  Set<Node> s = new HashSet<Node>();  // our return value
  if (d == 0) {
    s.add(x);
  } else {
    for (Node y: adjList(x)) {
       s.addAll(getNodesWithinDist(y,d-1);
    }
  }
  return s;
}