在我的具体情况下,图表表示为邻接列表,并且是无向和稀疏的,n可以是数百万,d是3.计算A^d(其中A是邻接矩阵)并挑选出非零的条目,但我希望不涉及矩阵乘法的东西。在每个顶点上进行广度优先搜索也是一种选择,但速度很慢。对于图中的每个顶点,找出距离内的所有顶点d
回答
假设我们有一个函数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
的结果,并使用这些缓存的结果来避免执行冗余遍历(尽管需要执行一些设置操作的代价 - 我不完全确定这是一场胜利)。我将把它作为练习来填写实现细节。
您已经提到计算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
节点访问该节点。
我不明白这比矩阵乘法更便宜(时间方面),因为此过程必须是对于一个单独的起始顶点,广度优先搜索是一个更好的选择,也不需要你的向量'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;
}
这是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)
- 1. 在顶点x的较小或相等距离d内找到顶点数
- 2. 图 - 找到从所有其他顶点可到达的顶点
- 3. 考虑图G.顶点8距顶点的距离是多少?7
- 4. 查找哪些点位于每个点的给定距离内
- 5. 算法根据距离源的距离对图中的顶点进行排序
- 6. 使用igraph查找连接到顶点的所有顶点?
- 7. Gremlin-Traversing查找与特定顶点无关的所有顶点
- 8. U-SQL顶点图不会显示每个顶点的ROW_COUNT
- 9. 在图中找到一组顶点,使每个顶点可以到达其他k个顶点
- 10. 统计图中的所有顶点
- 11. 在有向图中找出一个循环中的所有顶点
- 12. 从顶部获取点击div距离
- 13. 每个顶点的概率
- 14. OrientDB:查找所有没有给定类的直接邻居顶点的顶点
- 15. 从多个顶点的最大距离内提取子图的高效算法
- 16. 如何使用顶点的测地距离来平滑骨骼顶点权重?
- 17. 查找两个顶点(节点)之间的所有路径
- 18. 如何找到最大度数的图中的所有顶点?
- 19. 的igraph:为每个顶点中心性措施CSV文件,为每个顶点
- 20. 在另一个点的距离内查找所有点的算法
- 21. 有向图中的顶点,使得存在从这个顶点到另一个顶点的路径
- 22. 删除顶点和顶点本身的所有边
- 23. 在时间O(| E | + | V |)中查找从有向图的顶点可到达的所有顶点
- 24. 使用每个顶点
- 25. 有向图中从一个顶点到另一个顶点的最短路径
- 26. 查找图中的代表顶点
- 27. 查找属于简单循环一部分的所有顶点
- 28. 我如何在ThreeJS中每个顶点和每个顶点照明发光?
- 29. 如何在有向图中找到最小的一组顶点,以便可以达到所有其他顶点
- 30. Neo4j中所有顶点的索引
在图表执导? – 2011-04-16 08:50:13
阅读第一句 – 2011-04-16 10:20:35
由于图表表示为邻接表,因此深度优先搜索(最多d = 3)应该可以工作,您不需要在每个顶点上工作,而只需要顶点可访问 – Wei 2011-04-16 14:14:55