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

在我的具体情况下，图表表示为邻接列表，并且是无向和稀疏的，n可以是数百万，d是3.计算A^d（其中A是邻接矩阵）并挑选出非零的条目，但我希望不涉及矩阵乘法的东西。在每个顶点上进行广度优先搜索也是一种选择，但速度很慢。对于图中的每个顶点，找出距离内的所有顶点d

来源

2011-04-16 Robert D

在图表执导？ – 2011-04-16 08:50:13

阅读第一句 – 2011-04-16 10:20:35

由于图表表示为邻接表，因此深度优先搜索（最多d = 3）应该可以工作，您不需要在每个顶点上工作，而只需要顶点可访问 – Wei 2011-04-16 14:14:55

假设我们有一个函数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)返回类型是从简单的列表改变或设置，以代表从x的距离增加d集的列表，然后

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

其中init是函数，产率列表中除最后一个之外的所有元素。显然这是一个非终止递归关系，如果字面转换成代码，所以你必须对你如何实现它有点聪明。

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

来源

2011-04-16 09:12:15

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

然而，使用这个想法有一个更便宜的方法。假设你有一个（列）矢量v零和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现在对于每个节点具有肯定条目，可以从最多d步骤中的j节点访问该节点。

来源

2011-04-19 11:25:41 Martijn

我不明白这比矩阵乘法更便宜（时间方面），因为此过程必须是对于一个单独的起始顶点，广度优先搜索是一个更好的选择，也不需要你的向量'w'。'A^d * v'（反复计算或其他）零元素作为'w' – 2011-04-19 22:48:57

你说得对，我以为你想从一个顶点开始，但是，请不要在这种方法中没有矩阵矩阵产品，只有矩阵向量产品（它比计算）。 – Martijn 2011-04-20 06:16:49

在这种情况下，从给定顶点开始的宽度第一次搜索是最佳解决方案。你会发现距离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-19 11:56:57 Josh

这是1个起始顶点的最佳解决方案，但问题在于为每个顶点执行此操作。 – 2011-04-19 20:14:53

@ Robert D.是的，你是对的。我错过了 - 我的不好！ – Josh 2011-04-19 21:28:58

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-11 18:05:53 cybertextron

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

回答

相关问题