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

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

已邀请:

4 个回复

授巨

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)

晤默报

假设我们有一个函数verticesWithin(d,x)，它找到顶点x的距离ѭ2within内的所有顶点。解决此类问题（暴露缓存/内存化机会）的一种好的策略是提出一个问题：该问题的子问题如何相互关联？在这种情况下，如果d >= 1是范围内所有i的vertices(d-1,y[i])的并集，则我们可以看到verticesWithin(d,x)，其中y=verticesWithin(1,x)。如果是d == 0，则仅是{x}。（我假设一个顶点与自己的距离为0。）在实践中，您将要查看案例ѭ11the的邻接列表，而不是使用该关系，以避免无限循环。您还希望避免将x本身视为y的成员而带来的冗余。同样，如果将verticesWithin(d,x)的返回类型从简单列表或集合更改为表示距x的距离增加的d集的列表，则 verticesWithin(d,x) = init(verticesWithin(d+1,x)) 其中init是产生列表中除最后一个元素以外的所有元素的函数。显然，如果按字面意思将其转录为代码，那么这将是一个非终止的递归关系，因此您必须对如何实现它有所了解。有了子问题之间的这些关系，我们现在可以缓存verticesWithin的结果，并使用这些缓存的结果来避免执行多余的遍历（尽管是以执行一些集合操作为代价的-我不完全确定这是一次胜利）。我将把它作为练习来填充实现细节。

勘掸府迫路

您已经提到了计算A^d的选项，但这远远超出了您的需要（正如您已经提到的那样）。但是，有一种使用这种想法的便宜得多的方法。假设您有一个零和一的（列）向量v，代表一组顶点。现在向量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的步长进行访问。

犁攀富

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

要回复问题请先登录或注册

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

4 个回复

发起人

algorithm

graph

path

shortest

问题状态

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

与内容相关的链接

4 个回复

发起人

algorithm

graph

path

shortest

问题状态