问题标签 [graph-traversal]

我正在研究图表和遍历技术。但是，我有一个关于邻接列表的问题。正如您在邻接方法中所知道的，您为每个保持相邻顶点的顶点声明一个数组或一个列表。所以我的问题是“添加相邻顶点的顺序是否对深度优先搜索有任何影响”。让我更清楚。考虑到我有这个图表：

并考虑我对其进行了一些更改，例如；

所以我认识到深度优先搜索（例如）搜索顺序在逻辑上会发生变化。但是这种情况会影响搜索的性能还是一样？我希望我对我的问题很清楚，我也会感谢每一个答案。（我使用无向图）

Apache Giraph vs Neo4j：这两个图形处理系统中跨节点的遍历算法是否完全不同？如果我们使用 Giraph 和 Neo4j 对存储在单台机器（非分布式）中的数据进行遍历社交图，哪个会更好，为什么？

我正在寻找有关一项实验的信息，该实验确定了一条消息理论上需要经过多少跳才能到达地球上的每个人（即 80 亿）。因此，如果每个接收者都将消息转发给 X 联系人，则需要 Y 跳才能到达地球人口。我只记得Y非常低，X也不高。

任何人都可以帮助我提供实验名称或更多信息吗？

谢谢

我试图在 python 中遍历这个算法中的一个图。如果我想一一打印图表的所有元素或遍历整个图表，我应该做哪些更改。

任何帮助将不胜感激。谢谢。

我正在尝试使用 Gremlin 进行广度优先枚举，但是我无法找到一种方法来输出枚举期间观察到的所有步骤。我只能打印出最后一次迭代的结果。

我的问题是，给定这样的起始节点，我如何使用 Gremlin 跟踪所有路径（不知道整体深度）并打印出我一路上找到的所有内容？

我尝试过分散方法，循环方法（尽管如果我理解正确，两者似乎都需要事先了解路径的实际长度）

非常感谢！

编辑 3：好的，所以我的代码可以工作，但是如果我使用 16 个节点和 11 以上的搜索深度，我将面临巨大的内存消耗问题。

一个 soemone 检查代码并告诉我如何纠正该内存泄漏？

这是完整的代码：

我有以下问题。我有循环、无向、加权图 G=(V,E)。我需要根据这些规则找到两个给定节点之间的简单路径（没有循环）：

1. 在每个可能路径的边集中找到最小权重值
2. 选择这条路径，它在从找到的路径中选择的最小值中具有最大最小值

例如，我们有如下图表：

我们可以尝试找到从节点 1 到节点 8 的简单路径。有两种可能的路径，如下所示：

1. 1 -> 3 -> 5 -> 8，这条路径上的最小边权重是 2
2. 1 -> 3 -> 5 -> 6 -> 7 -> 8，这条路径上的最小边权重是 283

根据提出的标准，想要的路径是路径号 2，因为它具有比路径号 1 更大的最小值。

一个重要的假设：图中的节点数量非常少：少于 15 个。

我考虑过 Dijkstra 或 Bellman-Ford 算法修改，但挑战是，我们没有局部标准（最小距离） - 我们无法找到最小的边权重，直到我们没有获得整个路径......

我的第二个想法是使用最近邻算法的修改，但它用于解决所谓的旅行商问题，与我的情况相比有点不同。

我的问题如下。解决这个问题是否比使用深度优先算法获得两个给定节点之间的所有直接非循环简单路径，然后选择每个找到的路径的最小权重值的最大值更好？

在这种情况下，我有点担心 DFS 算法的复杂性，尤其是由于图中的递归和可能连接（边）的数量。

谢谢你的任何想法。

我正在处理与图遍历（维特比算法）相关的一些任务每个时间步骤我都有一组紧凑的活动状态，每个状态都完成了一些工作，然后结果通过传出弧传播到每个弧的目标状态等等建立了新的活动状态集。问题是输出弧的数量变化很大，从两个或三个到几千个。所以计算线程的加载效率很低。

我尝试通过共享本地内存队列共享作业

但它运行得非常慢，我的意思是如果没有使用活动集（活动集 = 所有状态）则更慢，尽管活动集占所有状态的 10% 至 15%。登记压力大幅上升，入住率很低，但我认为对此无能为力。

线程之间可能有更有效的工作共享方式吗？考虑一下 3.0 上的 warp-shuffle 操作，但我必须使用 2.x 设备。

这个问题是我之前提出的类似问题的延续：Find path between two nodes in graph, based on given criteria - optimization task。

问题摘要：我需要在图中找到从顶点 A 到顶点 B 的最佳路径，假设路径质量计算为路径上边缘权重的最小值，下一个最佳路径是具有最大最小值的路径。通常它就是所谓的“最宽路径问题”。

以前我需要在非常小的图形（最多 15 个顶点）中解决这个问题，所以我不需要复杂的算法，在好心人的帮助下，我设计了我的工作算法。不幸的是，现在我需要以这种方式重新定义我的必需品，以使我的图可以非常大（甚至 5 万条边）。我知道我需要为我的图找到最大生成树，并在获得的 MST 中获得从开始到停止顶点的简单路径。我决定使用jGraphT库。它实现了Kruskal 最小生成树算法。我可以通过将每个边权重乘以 (-1) 并将 Kruskal 用于最小生成树来获得最大生成树，但库中的算法已设计用于检索 MST 边的哈希集。

我的问题如下： 我已经获得了图的最大生成树作为边的 java HashSet。如何以最有效的方式在这种结构中找到从顶点 A 到顶点 B 的路径，以及什么数据结构对此最有效？你给我推荐什么？

此外，我担心这种情况，我的图并不总是一致的（它可能包含孤立的顶点或孤立的子图），这是 Kruskal 算法正确性的主要条件。有没有办法绕过这个问题？

感谢您提供任何帮助或提示。

我有一个（可能）简单的图遍历问题。我是使用 networkx 作为我的图形数据结构的图形新手。我的图表总是这样：

我需要返回从根节点到给定节点的路径（例如，path(0, 11)应该 return [0, 8, 9, 11]）。

我有一个解决方案，它通过传递一个增长和缩小的列表来跟踪遍历树时路径的样子，最终在找到目标节点时返回：

我从骨子里觉得没有必要传递这个“路径”列表......我应该能够使用调用堆栈跟踪该信息，但我不知道如何......有人可以启发我如何使用堆栈递归地解决这个问题来跟踪路径？