问题标签 [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.
algorithm - 遍历具有多个未知权重边的图的最快方法
给定一个无向正加权图G , G的一些边具有未知权重。例如,
其中边缘(B,C)的权重未知。
从A穿越到B花费你7。我们可以通过从B遍历到C来推导出未知的权重e = weight(B,C) ,反之亦然,并花费你e,最终成为一个已知的权重。从A走到C通过B总共花费你e+7。
我的问题是,当给定一个起点时,我们能以多快的速度获得所有未知的重量?也就是说,以尽可能小的成本从起点(例如A )遍历所有未知的权重边。
未知权重的个数为1的情况很简单。您可以先找出从起点到所需边的顶点的最短路径,然后遍历未知权重边。但是,当未知权重边的数量大于 1 时,我不知道如何解决。
谁能弄清楚如何做到这一点?
graph - 我可以在无向图中遍历每个节点恰好一次的最大节点数是多少?
所以我有一个无向无权图。它包含循环。我想找到访问最多节点而不重复访问任何节点的路径。由于这是一个图遍历,你可以在任何你喜欢的节点开始和结束。
背景研究: 我看过旅行商问题(TSP);这个问题是不同的,不允许你从你开始的地方完成并且没有重量。我查看了其他几种算法,但没有发现适合这个问题的算法。
Graph Size:图中有100个节点;有 10 个断开连接的节点。
optimization - 在分支定界算法的早期确定无希望的分支
我必须设计一个分支定界算法,每次都解决笛卡尔平面上图形的最优路径。我已经得到提示,在运行时早期识别无望的分支将复合成一个运行“快一百倍”的程序。我的想法是假设连接到开始/结束节点的最短边将是巡回赛中的第一条或最后一条边,但薄菱形图证明并非如此。有没有人对如何消除这些无望的分支或谈论这个的参考有想法?
基本上,有没有比仅按字典顺序更好地分支到解决方案子集的更好方法,例如。第一个分支包含和排除边缘 ab,第二个分支包含和排除分支 ac
c++ - 显示深度优先搜索图遍历 C++
我正在遍历我设置为一个类的图,使用向量来存储顶点和边。我在图表上使用深度优先搜索来显示路径,但我想以某种方式让我的代码在通过它们时按顺序显示顶点,格式如下:
其中“u”和“v”都是起始顶点(我希望它在同一个顶点开始和结束),“i”值是它沿途经过的顶点。
这是我目前拥有的 DFS 功能,我已经对其进行了简化,以便可以将其用作一般参考。我可以在这里修改什么以使其显示我想要的内容吗?(当前未设置为显示任何内容)。
graph - Neo4j - 为图遍历添加逻辑
简而言之,我的问题是——我是否可以修改 Neo4j 使用的遍历逻辑——在可达性计算期间,如何控制哪些边被遍历,哪些不被遍历。
详细描述:
我正在考虑从我们当前的数据库迁移到 neo4j,我想知道 neo4j 是否适合以下任务:
我们有大约 1000 万个简单节点的大图——它们的属性只有一个 id。
我们也有 3 种边缘 - “标准”、“打开”和“关闭”。"opening" 和 "closeing" 也有一个 "color" 属性,所以它们是匹配的。每个“开放”边都有一个匹配的“关闭”边“。例如,有一个颜色为“3”的开放边缘,所以也有一个颜色相同的关闭边缘。
我们需要解决两个节点之间的可达性问题,其中遍历规则相当简单:您可以随意通过标准边,也可以根据需要通过开放边,同时保持访问的“开放”边的顺序堆栈但是(这是棘手的部分)当你来到一个有几个“关闭”边缘的交叉点时,你必须穿过与遇到的最后一个“打开”边缘匹配的关闭边缘,然后从堆。
例如:
a -[标准]->B-[打开颜色:3]->C-[标准]->D-[关闭颜色:3]->E
还有
D-[关闭颜色:4]->F
请注意,D 有两个“闭合”边缘,颜色不同。根据上面定义的规则,A 可以访问 E,因为颜色堆栈的顶部有 [3]。
然而,A 无法到达 F。
可以为这样的图遍历逻辑配置 neo4j 吗?谢谢!!
java - Neo4j 遍历 API 限制?
对于给定的一组公司节点,我们正在尝试使用 Traversal API 仅检索提供产品节点列表中包含的所有产品的公司节点。之前使用 Cypher 的尝试效果不佳。在这个例子中:
如果所有 3 家公司都包含在公司列表查询中,并且产品 A 和 C 在查询的产品列表中,我们希望只返回公司 2 和 3,因为它们提供产品 A 和 C。这是我们的查询:
如果我们使用 ,Evaluator.includeWhereEndNodeIs(productNodes)
我们将返回列表中提供任何产品的productNodes
所有公司(以上示例中的所有 3 家公司)。如果我们使用Evaluators.includeIfContainsAll(productNodes)
评估器,如果产品节点列表中有多个产品,我们将不会返回任何公司节点。
任何建议表示赞赏。
path-finding - 完整图上的最小成本周期
我有一个带有无向加权边的完整图,需要通过图节点的子集找到最低成本循环。与Traveling Salesman不同,任何节点都可以被访问不止一次,而不是所有节点都需要访问,我的意思是路径应该具有最小的遍历边权重之和。
例如,这是一个邻接矩阵形式的图:
其中每条边的权重用于每个元素。开始和结束于a
并包括的周期[b,d]
看起来像
是否有一个最佳算法,或者一个非常好的启发式算法?
sequence - 使用连续移位的可能 4 位组合
我试图找出使用 4 位和连续移位的可能组合的数量。我有一组 4 个光传感器读取带有白色和黑色标记的纸条。我想弄清楚它的位置。
我需要知道不重复的唯一可能性的最大数量,我尝试手动计算但无法超过 14。如果可能的话,我想达到 16。
这是我的顺序:
顺便说一句,我失踪0101
了1010
algorithm - 在二维网格中查找路径并返回所有匹配的节点
假设我有一个行*列网格,网格上的每个节点都有一个整数(状态)值。
如果值
state[row][0] == state[row][NUMBER_OF_COLUMNS -1]
我想检查是否存在仅由这两点相同状态组成的“路径”..
通过路径,我的意思是左侧、右侧、底部或顶部的状态与原始状态相同。
我不确定它是否重要,但可以说状态是二进制的(# 或 -)所以如果我正在检查状态 ==“-”的路径,如果状态到 N,我们可以继续路径, E,S,W 也是 == "-"
结束行必须等于开始行。
成功案例:
或者
或者
失败的例子:
或者
或者
会失败。
我该怎么做呢?我在 Objective C 中编写代码,但帮助我理解这些步骤的伪代码就足够了。
除了检查路径是否存在 BOOL 之外,我还想返回路径中所有网格坐标的数组。
这很容易实现还是我有点过头了?
java - 如何用各自的属性替换节点 ID?
我正在使用Neo4j
图形数据库,并使用 Java 从中提取路径。我有如下路径:
我想用它们的属性替换路径中的节点 ID。前任。对于具有属性的节点 id 3 "name=ABC"
,输出应该像"[(ABC)--[KNOWS,5]....]"
How it can be done?