4

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

4

4 回答 4

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)
于 2013-10-11T18:05:53.760 回答
0

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

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

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

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

向量w现在对于每个节点都有一个正条目，可以j在最多d步骤中从第 th 节点访问。

于 2011-04-19T11:25:41.417 回答
0

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

解决此类问题的一个好策略是公开缓存/记忆机会，即提出以下问题：该问题的子问题如何相互关联？

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

在实践中，您需要查看 case 的邻接列表d == 1，而不是使用该关系，以避免无限循环。您还需要避免将x自己视为y.

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

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

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

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

于 2011-04-16T09:12:15.943 回答
0

在这种情况下，从给定顶点开始的广度优先搜索是最佳解决方案。您将找到距离 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;
}
于 2011-04-19T11:56:57.097 回答