问题标签 [graph-algorithm]

给定一个无向图 G = (V,E) 和一组节点 P。我需要找到一个包含这些节点的循环（不是最短长度循环）吗？我如何找到这个循环？

考虑下图：

我试图找到一种方法来枚举从源节点到目标节点的所有可能路径。例如，从 A 到 E，我们有以下可能的路径：

请注意，对于 ACDE，实际上有 2 条路径，因为其中一条使用边 F3，另一条使用边 F5。此外，由于 A 和 C 之间存在循环，因此您最终可能会得到无限数量的路径，但出于此目的，我只对在从源到目标的路径上没有重复节点的路径感兴趣。

我写了一个深度优先搜索（DFS）算法，但问题是当你在 2 个节点之间有多个边时（比如上面的边 F3 和 F5）我不知道如何处理它。我的算法只带回路径A C D E和A C E，而不带回其他路径。在 的情况下A B C E，我理解原因，因为它从 A 开始，然后到 C 并构建这些路径，但是当 DFS 回到节点 B 时，它然后尝试去 C，但是 C 已经被访问过所以它停止了。

无论如何，我只是想知道是否有办法做到这一点，或者这可能是 NP 完全的。

如果您想查看我的 DFS，代码如下（抱歉滥用宏，我在竞赛编程中使用这些，所以有点习惯）。

输出：

这是一个很长的镜头，但我想我可以在开始肮脏的工作之前尝试一下。

我有一个项目来构建一个应用程序，该应用程序将为定义的输入站（顶点）和线路（边缘），即一些公共交通的真实地图，将给定的地图模式化为地铁地图。我已经对该问题进行了一些研究，这是一个相当于 3-SAT 问题的 NP 完全问题。关于如何生成这样的地图，我也有一些理论想法，但还不够详细。

我正在寻找的是该问题的任何其他现有解决方案，某种伪代码，（几乎）任何其他编程语言中的一些真实代码等，任何可以减少我花在算法本身上的时间的东西，这将使我有更多的时间来处理应用程序的其他方面。

如果有人看到任何可以帮助我的东西，我会非常感激。

我正在尝试设计一种执行以下操作的算法。

输入：

我有一组映射到一组属性的键（总共 n 个）。属性包含每个属性的权重和属性的值。

输出：

根据一组属性及其各自的权重和值，识别一组合格的键（总共 k 个）。

此外，在选择获胜者的每个周期中都应该修改数据，以便在下一个周期中未被选中的人的机会增加（而获胜的人的机会就好像他们在系统）。

希望手头的问题很清楚。基本上，财产的价值和各自的权重将决定哪些钥匙更有可能获胜（权重越高的价值越高，该钥匙获胜的概率就会增加），我们最终会选择每个人。

任何关于如何做到这一点的意见将不胜感激。

谢谢！- 阿泽姆

我有一些代表流程图的数据。（一堆 Jira 状态及其向其他状态的转换。）

我还有一种粗略的方法来将每个流程图项放置在 OpenOffice Draw 文档中的 A4 页面上。（尽管对此欢迎更好的建议。）

但是，我不希望输出一行框并手动重新排列它们，特别是因为我可能需要多次重新生成流程图。

这似乎是一个常见问题，因此必须有现有的算法/技术可以分析多个项目（以及它们之间的链接）并将它们放在合适的位置上。

关于如何最好地做到这一点的任何建议？

我有一个未加权的连接图。我想找到一个连接的子图，它肯定包含一组特定的节点，并且尽可能少的额外节点。这怎么可能实现？

以防万一，我将使用更精确的语言重申这个问题。令 G(V,E) 是一个未加权、无向、连通图。让 N 是 V 的某个子集。找到 G(V,E) 的最小连通子图 G'(V',E') 以使 N 是 V' 的子集的最佳方法是什么？

近似值很好。

例如 A+B=C C+D=E E+F=G 随着对每个节点的更改，重新计算相关节点。下图是我正在尝试做的一个简单示例。

进一步说明 每个对象的结构都是相同的。输入将是价格，因为每次价格变化都会对下游价格产生连锁反应。所以在上面的例子中，A+B=C 会变成 5+6=11。等等

更改不断发生（可能每秒），因为每个值都发生更改，我需要得到通知（事件触发）。

给定一个无向连通图 G，找到一棵直径最小的生成树。

是否有任何有效的算法可以在具有偶数个顶点的完整加权图中找到具有以下属性的边集。

• 对于满足其他标准的任何集合，该集合具有最小、最大的边权重
• 每个顶点都连接到集合中的一条边

所有权重均为正

d我想不出比蛮力更好的方法，但我不认为它是 NP 难的。

我想更好地了解各种常见的搜索算法是如何相互关联的。有谁知道资源，例如层次图或对此的简明文字描述？

我的意思的一个小例子是：

等等

谢谢！