问题标签 [cyclic-graph]

我正在寻找有向循环图的密度。

根据维基百科，

对于无向简单图，图密度定义为：

2 * |E| / (|V| * (|V| - 1))

对于有向简单图，图密度定义为：

|电子| / (|V| * (|V| - 1))

但然后我继续阅读简单图的定义：

“与多重图相反，简单图是一个无向图，其中不允许有多个边和循环。”

我很困惑，因为另一篇文章提到了“有向”和“无向”简单图。现在简单的图只能是无向的？它还指出简单图不能有循环，所以我不确定我是否能够在我的循环图上使用这些公式中的任何一个。

我继续阅读多图，但没有提到计算它们的密度。
对于具有循环的图，密度不是人们会关心的吗？

第一篇文章说：

“最大密度为 1（对于完整图）”

看起来完整图是multigraphs的一个特殊版本，所以我认为计算密度应该是有意义的。

我用什么公式？

我的问题的答案可能很明显，而且我在纸上知道这个明显的答案。我的意思是，当涉及到一些示例时，我理解为什么我们不允许使用循环来运行最低公共祖先算法，但是我在理解为解决 DAG 中的 LCA 而编写的论文时遇到了问题。所以解决方案的哪一部分阻止我们在循环图上使用它..

我愿意知道并且很感激被告知：

• 您能解释一下 DAG 中 LCA 问题的一种解决方案，而无需太多公式吗？
• 你能确定哪个步骤有循环问题吗？为什么？

在我的问题中，找到它们的 LCA 的节点对不在一个循环内，所以我认为可能有一种方法可以解决这个问题。

提前致谢

正在从事编码练习，我对如何实施解决方案有些困惑。

根据 JavaDoc，我必须实现这个 EmployeeManager 接口。假设员工数据在与其他请求不同的线程中到达。请注意，getSalary() 以恒定时间 O(n) 执行。执行时间不得随员工或部门的数量而变化。

问题）：

1. 这是什么类型的问题？

2. 我应该将 Employee 和 Department 类创建为 POJO，里面会有什么？他们是否必须实现 runnable 才能实现线程安全？

3. 这需要什么类型的数据结构？

我对我的数据结构和 CS 的东西真的很生疏，所以非常感谢任何反馈。

注意：没有负成本。

我正在考虑在使用 Dijkstra 的路由中实现掉头。Dijkstra 会推荐 ABCBD 路线而不是 ABD 路线吗？第一次遇到B时，B在访问邻居后被标记为已访问，因此永远不会考虑从BCB循环

在那种情况下，Dijkstra 从不推荐结果中的循环？

我正在尝试在 Rust 中实现循环链​​接数据结构。我Node的 s 定义为：

我正在尝试构建一个像这样的最小结构（额外的括号以获得更好的生命周期可见性）：

这可行，但现在我不知道如何将占位符替换link2为“关闭循环”的引用。我试过这个，但它不起作用，因为我不能分配给link1，这是借用了上面的行，并且因为link2它仍然被引用时会超出范围link1：

我可以尝试通过使用Rcs 来避免这些生命周期问题，但这听起来会破坏 Rust 的 0-runtime-cost 生命周期管理的目的。

另一种将所有节点放入 aVec并仅直接引用该节点的尝试也不起作用：

因为我不能改变任何节点而不可变地借用它们，但它们都已经被不可变地借用了。

有没有办法在没有运行时开销的情况下使用具有循环链接的这种结构，例如像我尝试过的纯引用？我对额外的内存成本很好，比如支持Vec所有节点的所有权。

我一直在尝试解决 Prolog 中的寻路问题。谓词在哪里

edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(d,e).
edge(d,f).
edge(f,g).

edge(X,Y) :- edge(X,Z), edge(Z,Y).
然后是我编译并运行查询时 的规则| ?- edge(a,X)。它显示 Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ) 然后我搜索了解决方案，发现在我们的规则中包含atom(x).,atom(y).可以解决堆栈溢出问题。即新规则是

edge(X,Y) :- atom(X), atom(Y), edge(X,,Z), edge(Z,Y).是的，它确实解决了堆栈溢出问题。但是，我想知道这个 (atom/1) 谓词究竟是如何解决我的问题的？它对我们的变量有什么作用X,Y来解决 StackOverflow 问题？我是 Prolog 的新手，任何帮助将不胜感激，谢谢。:)

我试图通过以下循环有向图找到所有路径。我希望能够包括通过循环一次的路径，但不包括无限循环通过一条路径的可能性。

我找到了所有简单的路径，但是，还有另外三个不重复循环的路径，但是能够通过一个循环一次。我希望能够使用 Python 找到这些？？

我在下面包含了迄今为止开发的代码。

给定：未加权无向图（循环）G(V,E)，每个顶点都有两个给定的值（比如 A 和 B），并且没有两个相邻顶点具有相同的 A 值。
找到具有最大 B 值总和的简单路径，具有以下约束：
1）该路径包含相同 A 值的顶点，或者它最多可以有两个不同的 A 值（这些值必须是交替的，因为没有两个相邻的顶点可以具有相同的 A 值）

图

在图中。最长的简单路径从顶点 2 开始，到 5 结束，所有顶点最多有 2 个不同的值 1 和 2，它们在路径中以交替方式 1、2、1、2、1 输出并输出 B 值总和。
请记住：如果 B 的值 6 为 13，则顶点 6 可能是答案，因为解决方案路径的总和仅为 12。

它给出了错误的答案。不。顶点数 <=1000000

我正在用 Java 制作一个小游戏来练习编程，并遇到了这个我似乎无法自己解决的小问题。

在这个游戏中，我想建立一个可以买卖物品的虚拟商店。

大多数物品只能通过按照我所谓的“食谱”从其他物品中创建出来才能在游戏中获得。配方基本上只是创建新项目所需的一组项目。一个项目可以有多个配方。配方的结果可以是新数量的多个实例。我将像这样 [item, item, ..., item]（结果数量）表示食谱。

所以有基础物品，不能创造，必须通过其他方式获得，有创造物品，只能通过其配方之一获得。

我想尝试模拟供求关系，我想出了这个属性，我称之为“交易金额”，每个项目都初始化为 0。交易金额表示正在出售或购买的商品数量。如果我卖出 X 数量的物品，它的交易量增加 X，如果我购买 Y 数量的物品，它的交易量减少 Y。

现在我需要确定我的物品的价格。

所有基础项目都被分配了一个统一的值。然后将价值和交易金额插入到函数 f(v, t) 中，该函数会输出价格。这个价格总是 >= 0。这个函数的一个属性是，如果交易量 t 为 0，那么结果价格等于输入值 v。所以如果一个玩家购买了一定数量的物品，那么交易量就会变为下降 x，价格接近 0。如果另一个玩家出售相同数量的相同物品，交易量回到 0，价格跳回原始值。

现在所有基础项目都有一个值，我需要计算所有创建项目的值，以便能够使用 f 计算它们的价格。我希望它们的价值基于创建它们所需的最便宜的配方。所以我必须解析所有食谱，将每个食谱中使用的所有项目的价格相加，并确定一个食谱的最低价格。那就是所创建项目的价值。

我可以在一个图中对这个设置进行建模，其中顶点表示可以在商店中交易的商品，并且有向边将一个商品连接到另一个可以从源商品创建的商品。所以我有一个有向边（'source -> destination'），其中源是目标食谱之一中的成分。因此，从这个前提出发，我创建了一个包含 600 个左右顶点的随机有向图。每次游戏加载时，此图表都会有所不同，并且生成器应特别允许图表内的循环。

这是一个例子：

项目 A 和 B 是基础项目，其值分别为 10 和 2。它们的交易金额最初为 0，因此它们的价格等于它们的值 10 和 2。

项目 C 是具有两个配方 R1 = A、A、B 和 R2 = B、B、B 的已创建项目。现在我确定 R1 的价格为 22，R2 的价格为 6，这是最低配方价格。因此项目 C 的值为 6（最初交易量为 0，因此价格也是 6）。

在这种情况下，图表看起来像 (A) --> (C) <-- (B)

到目前为止，一切都完美无缺。

现在，当价格-价值依赖关系是循环的时，我遇到的问题就出现了。

以下是我需要帮助的 3 类案例：

(1) - 0 顶点循环

简单地说，物品 A 有一个固定的价格，物品 B 可以从配方 [A, B] 中创建。如果 B 的价格发生变化，则 B 创建的所有项目都必须重新计算。在这种情况下，B 是由 A 和 B 组成的，所以我也必须重新计算 B 的价格。这再次触发了 B 的重新计算等等……我知道前提很奇怪，但把它想象成重新粉刷一扇门（B）。它由相同的门 (B) 加上油漆 (A) 制成。我称其为 0 顶点循环，因为在遍历循环时，您通过 0 个顶点返回到您开始的位置。

(2) - 1 个顶点循环

如果我们从第一个示例中获取相同的项目 A 和 B，并添加具有配方 R1=A、B 和 R2=D、D、D 的项目 C 和具有配方 R3=C 的项目 D。所以C可以“分解”成3个D，3个D可以组合成一个C但既然 C 也可以由 D 制成，并且假设 R2 变得比 R1 便宜，那么我也必须降低 C 的价格，从而再次触发 D 的价格降低等等。这将一直持续到价值收敛到某个地方，具体取决于所涉及配方的成分。我称它为 1 个顶点循环，因为在遍历循环时，您只通过一个顶点。

(3) - n个顶点循环

这是一般情况，我想如果我解决了这个问题，上面的两个具体情况也将得到解决。如果商品 A 由 B 组成，B 由 C 组成，C 由 D 组成，以此类推，直到由 A 组成的商品 Z，那么改变一个的价格将触发下一个的价格变化，这将触发价格下等等等等。这条链实际上可以任意长。**

我正在寻找一种可以解决我的问题的算法。我希望能够计算初始交易金额为 0 的所有物品的所有价值和价格。当玩家买卖物品时，价格变化应该通过图表传播。我考虑过修改 Dijkstra 算法、A*、Bellman-Ford 算法和 Floyd-Warshall 算法，但都无法得到令人满意的结果。

有人可以指出我正确的方向吗？

我有一个如下对象：

我必须找到循环实体的映射而不将其转换为图形。

类似的输出将如下所示：

我尝试了以下操作：

有没有其他方法可以提高性能。我认为以迭代方式使用 JSON.stringify 和 try catch 块可能也是一种方法。但我不确定它的性能会更高/更低。