问题标签 [graph-traversal]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
263 浏览

graph - 有效地找到有向图中两个节点之间的某个路径上的所有节点

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

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

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

0 投票
1 回答
88 浏览

algorithm - 无起点的图搜索算法

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

0 投票
1 回答
701 浏览

mysql - 高效遍历关系数据库中存储为表的图

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

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

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

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

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

0 投票
1 回答
89 浏览

scala - Play's Hot Reloading and Neo4j Embedded takes too long

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.

0 投票
1 回答
1393 浏览

algorithm - 交通灯图

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

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

例如,假设您有这个图表:

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

然后是顶部:

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

0 投票
1 回答
212 浏览

c# - 图表 - 找不到到节点的最小路线

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

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

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

遍历图的类:

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

0 投票
1 回答
555 浏览

neo4j - 使用 Neo4J 求解加权网络流

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

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

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

0 投票
2 回答
1569 浏览

prolog - 确定图形是否在序言中连接

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

假设我有一个边列表(G图在哪里):

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

0 投票
1 回答
57 浏览

algorithm - 如何从遍历两个不相交的等数组顶点中找到最后一个连接顶点的egde

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

遍历算法:

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

例子:

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

0 投票
2 回答
2679 浏览

python - 如何在自定义 PyYAML 构造函数中处理递归?

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

片段#1。

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

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

片段#2。

但它失败了:

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

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

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