问题标签 [graph-traversal]

我目前正在尝试找出一种有效的方法来查找有向图中两个节点（例如和）之间的某个路径上的所有节点。XY

我的第一个想法是从 X 运行 BFS，从 Y 运行 BFS，并获取访问节点的交集。请注意，我不需要枚举 X 和 Y 之间的所有路径，只需找到位于从 X 到 Y 的路径上的所有节点。

我的问题是，有没有更优化的方法来做到这一点？

我有一个场景的边缘图，想提取最能区分天空和地形的边缘。这似乎被很好地描述为一个图遍历问题。但是，流行的搜索算法（例如 A*）依赖于使用起点和终点（分别不同于第一列和最后一列）。是否有不需要这些参数的图形搜索算法？我还想最大化提取边缘的一些全局特征，例如平滑度。注意：速度是一个重要问题，这需要实时完成。

我有一个表，它表示在边缘列表表示中没有循环依赖关系的图形数据结构，如下所示：

是否可以进行 SQL 查询，以便对于特定的 vertex v，直接和间接地检索V由所有连接顶点组成的顶点集？

例如retrieve_all_connected_vertices(3)将返回 set (4, 5, 7)。

我正在研究的方法是那些使用 MySQL 支持的纯 SQL 语句（存储过程等没有选择），或者与某种伪编程语言结合使用的方法。我不是在寻找特定于语言的实现，尽管我将使用 Scala 来实现这个特定目的。

我知道我们基本上可以递归地跟踪链接，直到它到达最后一个顶点，但是，如果可以使用某种优化来减少内存使用或算法复杂性，我会很高兴。

I am using Neo4j embedded database on a Play/Scala app. I leaned towards the embedded version because I want to use the Neo4j's Traversal Framework so I can easily create JSON trees using a breadth-first traversal. The problem with embedding the database is that when my Play application hot-reloads, it restarts the application, whereby my app shuts down the server (otherwise I get a db file lock error). This is causing 20s browser reloads between edits. This is especially annoying when editing Play's Twirl html files.

Am I screwed? Should I hide the calls to the embedded db behind a service? Is it worth it to do this just for developement? AFAIK, Neo4j's RESTful service doesn't allow breadth-first traversals. I'm open to suggestions. Thanks.

假设您有一个标准图，每个节点和每条边都有附加值。您希望在最短的时间内从图表上的一个节点转到另一个节点。到目前为止，您遍历此图所花费的时间将被称为 T。如果边的值为 V，则遍历该边会将 V 添加到您花费的时间 (T += V)。如果一个节点的值为 N，遍历该节点将迫使您等待，直到您花费的时间可以被 N 整除 (T += (N - T % N) % N)。

你可以把它想象成街道和红绿灯。在街道上行驶需要一定的时间才能到达另一端。开车穿过红绿灯需要等待它变绿的时间。

例如，假设您有这个图表：

乍一看，顶部路径看起来更快，因为它具有更短的边缘和更短的延迟。然而，事实证明底部路线更快。让我们先计算底部：

然后是顶部：

如您所见，底部要短得多。在这样的小规模下，计算起来更容易，但在城市规模下，您需要使用某种遍历算法。有谁知道除了蛮力之外是否有任何解决方案？

我想找到到节点成本最低的路线。它为我找到了几条路线，但没有最低成本的路线。

我的类来存储有关节点的信息：

在元组中，我有 int, int - 第一个 int 是结束节点，第二个 int 是到该节点的路由成本

遍历图的类：

在我的示例中，我想找到到节点 6 的成本最低的路线

我有一个二分图（男孩和女孩的笔记），其中节点与加权边相连（女孩-男孩对的兼容性如何），每个节点的容量为 5（每个男孩/女孩可以匹配 5 个相反的人性别）。我需要找到最佳匹配以最大化权重。

这可以表述为加权网络流——每个男人是 5 个单位的源，每个女孩是 5 个单位的汇，每个可能的弧有 1 个单位的容量。该问题可以使用线性规划或图遍历算法（例如 Ford-Fulkerson）来解决。

我目前正在研究使用 Neo4j 的可能解决方案 - 有人知道如何去做吗？（或者我应该只使用线性编程解决方案......）

我需要创建一个谓词isConnected/1，将图形作为参数并确定对之间是否存在无向路径。

假设我有一个边列表（G图在哪里）：

因此，由于 3 和 4 之间没有边，这应该会失败。
我将如何解决这个问题？我是否必须遍历每个边缘并将边缘记录在列表中？还是有更好的方法来做到这一点？

给定两个不相交的等数（大小n）集合（称为0and 1），其值从1to2n我必须找到由特定遍历形成的最后一条边（顶点对）。

遍历算法：

• 从值开始1（这个值在哪个集合中并不重要）
• 将它与来自相反集合的第一个自由值连接（首先相对于实际值，所以如果当前值等于3，那么我将检查4, 5, 6, 7, ..., 2n - 1, 2n, 1, 2）
• 重复第二步

例子：

我能够以2 * (1 + 2 ... + n) = 0(n^2)复杂的方式解决这个问题。但我相信有更好的解决方案。

PyYAML 可以处理常规 python 对象中的循环图。例如：

片段#1。

这段代码成功了，所以很明显在加载序列化对象时有一些机制可以防止无限递归。当我编写自己的 YAML 构造函数时，如何利用它？

例如，sayNode是一个具有瞬态字段foo和的类，以及非瞬态bar字段child。只child应将其放入 yaml 文档中。我希望这样做：

片段#2。

但它失败了：

我明白为什么了。我的构造函数不是为递归而构建的。它需要在完成构造父对象之前返回子对象，并且当子对象和父对象是同一个对象时会失败。

但显然 PyYAML 具有解决此问题的图遍历，因为 Snippet #1 有效。也许有一个传递来构造所有对象，第二个传递来填充它们的字段。我的问题是，我的自定义构造函数如何与这些机制联系起来？

这个问题的答案将是理想的。但是，如果答案是我不能使用自定义构造函数来做到这一点，并且有一个不太理想的替代方案（例如将YAMLObject类混合到我的Node类中），那么这个答案也会受到赞赏。