问题标签 [graph-traversal]

If you have a graph represented as an adjacency list, how can you detect any odd length-ed cycles in python?

Suppose you have a graph given as input:

A is a dictionary where the key is a number and the value is a list of numbers, so there is an edge between the key to all of it's values. V is a dictionary which maps a number to the node instance.

How can you detect if there is an odd length-ed cycle?

From the input above, there actually is one which uses nodes 3, 4, 5.

Basically how can I get the output to be 3 4 5?

Thanks

我正在寻找一个可以对图进行节点级遍历的 JavaScript 库。

我能找到的最相似的东西（帮助解释我想要什么）是ThinkMap，它由visualthesaurus使用。

基本上从单个圆形节点（最好是 a <table>）开始，我想显示有限数量的最近邻居。

单击最近邻居应重新构建以新节点为中心的图形，并查询其 JSON 源以获取新的最近邻居。

是否有任何开源 JavaScript 库或框架具有类似功能的示例？

这是场景：我在 orient-db 中有许多用户顶点。我想检索不是特定用户的朋友的所有用户，其中朋友是优势。我需要 gremlin 命令。任何人都可以帮助我吗？谢谢你。迭戈

我目前有一个存储在列表中的连接列表，其中每个连接都是连接两个点的有向链接，并且没有任何点链接到多个点或链接到多个点。例如：

应该产生：

我尝试使用一种算法来执行此操作，该算法采用输入点和连接列表并递归调用自身以查找下一个点并将其添加到不断增长的有序列表中。但是，当我没有从正确的点开始时（尽管这应该只是反向重复相同算法的问题），而且当有多个未连接的链时，我的算法就会崩溃

编写有效算法来排序这些连接的最佳方法是什么？

我有一个巨大的节点有向图（100M+ 个节点），节点集之间有多个路径实例记录。任何两个节点之间的路径可能会有所不同，但我想找到的是共享多个中间节点的路径，除了主要偏差。

例如，我在节点 A 和节点 H 之间有 10 个路径实例。这 10 个路径实例中有 9 个经过节点 c、d、e、f - 但其中一个实例经过 c、d、z、e、f - 我想找到那个“奇怪”的实例。

有什么想法我什至会开始解决这样的问题吗？可能适合该任务的现有分析框架？

基于评论的详细信息：

• PIR（路径实例记录）是经过的节点列表，每个边具有相关的边遍历时间。
• 目前，原始 PIR 记录采用纯字符串格式 - 显然，我希望根据我最终选择分析它的方式以不同方式存储它。
• 这不是一个解决路径的问题——我永远不需要找到所有可能的路径；我只需要分析采用的路径（每个路径都是 PIR）。
• 需要从 PIR 生成子路径列表。

PIR 的示例类似于：nodeA;300;nodeB;600;nodeC;100;nodeD;100;nodeF

这转化为 A->BC->D->F 的路径；每个顶点的成本/时间是一个数字——例如，从 A->B 出发花费 300，从 B->C 出发花费 600，从 D->F 出发花费 100。每次进行遍历时，每次遍历的成本/时间都会有所不同。因此，例如，在一个 PIR 中，从 A->B 出发可能花费 100，但在下一个 PIR 中，从 A->B 出发可能花费 150。

我有一个图表G = (V,E)，在哪里

• V是的一个子集{0, 1, 2, 3, …}
• E是的一个子集VxV
• 中没有未连接的组件G
• 该图可能包含循环
• 中有一个已知节点v，V就是源；即没有这样u的优势V(u,v)
• 中至少有一个汇/终端节点v；V即没有这样u的优势。终端节点的身份未知 - 它们必须通过遍历发现V(v,u)

我需要做的是计算一组路径P，使得从源节点到任何终端节点的每条可能路径都在P. 现在，如果图包含循环，那么根据这个定义，P becomes an infinite set. This is not what I need. Rather, what I need is forP P` 可能会探索循环。to contain a path that doesn't explore the loop and at least one path that does explore the loop.
I say "at least one path that does explore the loop", as the loop may contain branches internally, in which case, all of those branches will need to be explored as well. Thus, if the loop contains two internal branches, each with a branching factor of 2, then I need a total of four paths in

例如，一个算法在下图上运行：

可以表示为：

应该产生一组路径：

到目前为止，我有以下算法（在 python 中）适用于一些简单的情况：

但在更复杂的情况下它会失败。

我会很感激任何帮助，因为这是一个验证我为硕士论文开发的算法的工具。
先感谢您

我想在有向图中创建一堆“与”、“或”和“非”门。然后从输入中遍历，看看它们的结果是什么。

我认为有一个现成的遍历可以做到这一点，但我没有看到。我不知道这种遍历的名称是什么。

当然，广度优先是行不通的。我需要得到所有的叶子，然后走向根部。换句话说

A = (B & (C & Z))

我需要先解决 C@Z。

我需要将这种类型的东西放在一个图表中并向上遍历。

我还在学习 MapReduce 框架，专门由 Hadoop 实现，我想知道是否可以对其进行修改以执行以下任务：

Map() 函数将发出 (key,value) 对，其键是大小为 2 的数组，例如 int[2]。我希望包含两个共同整数中的任何一个的每一对都映射到同一个减速器。

例如，如果 Map() 发出：([2,3],4),([2,4],5),([6,5],2),([5,7],1),那么 Reduce1 应该接收前两对，Reduce2 接收后两对（前两个共享 2，第二个共享 5）。这可以看作是一个连通分量问题，其中顶点是 int[] 中的整数，而边在同一个 int[] 中的任意两个整数之间共享。

我试图弄清楚如何解决这个问题。它取自为 12 年级学生举办的编程竞赛。任务是让学生“Karli”参加足够的课程以获得 214 个学分。学生在进入考场前不得超过或少于 214 个学分。门在图中表示。用户可以重复一堂课，但他们必须离开那个教室..去另一个教室..然后回来。

我尝试手动执行此操作，并且能够找到一个带有路径的解决方案：

数学-代数-哲学-代数-数学-建模-微积分-建模-考试

我正在尝试开发一种算法，该算法将在给定所需信用数的情况下找到一条路径（即本例为 214）

这是我尝试过并陷入困境的：

将地图表示为一个图，门是两个节点之间的一条双边。但是我不知道什么图遍历算法可以让我解决这个问题？

将图形转换为邻接矩阵会使事情变得更容易吗？

谢谢

这是我存储在 JSON 中的数据结构示例：

我正在寻找任何两个节点之间的最短路径。例如，从echoto的最短路径hotel是：echo-> golf->hotel

如您所见，这些节点是循环的，并且可以无休止地遍历它们。我还应该注意，节点路径都是一种方式。所以使用上面相同的例子，从hotel返回到的最短路径echo是：hotel-> foxtrot->echo

这样的数据结构有名字吗？我知道循环打破了“树”的规则。这会是图遍历吗？