问题标签 [graph-algorithm]

在无向和连通图中，每条边都有一种颜色（红色、绿色或蓝色）。
有效路径是每种颜色至少有一条边的路径。
问题是如何找到最短的有效路径或确定不存在。

我尝试使用 BFS，但无法找出解决方案。
关于如何开始的任何想法？

我需要从满足以下属性的所有可能的 DFA 中选择一个确定性有限自动机 (DFA)。必须选择均匀分布的 DFA。

DFA 必须具有以下四个属性：

• DFA 有 N 个节点。
• 每个节点有 2 个传出转换。
• 每个节点都可以从其他每个节点访问。
• DFA 是从所有可能性中以完全一致的随机性选择的。

我不考虑标记节点或转换。如果两个 DFA 具有相同的未标记有向图，则认为它们是相同的。

以下是三种不起作用的算法：

算法#1

1. 从一组称为 A 的 N 个节点开始。
2. 从 A 中选择一个节点并将其放入集合 B。

3. 虽然集合 A 中还有节点

   /li>

4. 对于 B 中的每个节点 n

   /li>

算法#2

1. 从一个有 N 个顶点且没有弧的有向图开始。
2. 生成 N 个顶点的随机排列以生成随机哈密顿循环，并将其添加到图中。
3. 对于每个顶点，向随机选择的顶点添加一个输出弧。

算法#3

1. 从一个有 N 个顶点且没有弧的有向图开始。
2. 生成一个长度介于 N 和 2N 之间的随机有向循环，并将其添加到图中。
3. 对于每个顶点，向随机选择的顶点添加一个输出弧。

我根据算法 #2 创建了算法 #3，但是，我不知道如何选择随机定向循环来创建均匀分布。我什至不知道这是否可能。

任何帮助将不胜感激。

我正在考虑在有向图中找到负权重循环的算法。问题是：我们有一个图 G(V,E)，我们需要找到一个有效的算法来找到一个负权重的循环。我了解此 PDF 文档中的算法

简而言之，该算法通过迭代 |V|-1 次进行松弛来应用 Bellman Ford 算法。然后它检查是否有一个可以更放松的边缘，然后存在负权重循环，我们可以通过父指针追溯它，一切顺利，我们找到一个负权重循环。

但是，我正在考虑另一种算法，即通过跟踪到目前为止您遍历的距离的总和，在图上使用深度优先搜索（DFS），我在开始时将所有节点标记为白色，并在我时将它们设为灰色搜索路径，并在完成时将它们标记为黑色，这样我知道当且仅当我找到一个访问节点并且它是灰色的（在我的路径中）时我才找到一个循环，而不是深度已经完成的黑色-第一次搜索，所以对于我的算法，如果我到达一个已经访问过的灰色节点，我检查它的更新是什么（新的距离），如果它比以前低，我知道我的权重是负的循环并可以追溯。

我的算法错了吗？如果是这样，你能找到一个反例吗？如果不是，你能帮我证明吗？

谢谢你

我有两个平面表示一棵树，例如：

树是：

如您所见，一个状态中可以有多个事件和状态。不要介意名称，它们不相关，它们只是表示元素的类型。

我相信第一个列表是树的深度优先、自下而上的遍历，第二个列表是深度优先、自上而下的遍历。

我需要从两个平面列表中重新创建树，即将每个 State 或 Event 分配给它的父 State（或顶层）。这可能吗？如果是这样，怎么做？

我的代码中基本上发生的是：

我无法更改 Traverse* 功能。

我需要租两间房子。我希望他们尽可能接近。大约有300间房屋可供出租。我希望使用 Google Maps Directions API 来计算任何两个可用房屋之间的步行距离，这样我就可以对列表进行排序并选择两个靠近的。

一切都很好，除了谷歌设定了每天 2,500 个查询的理论限制（实际上这个限制要低得多，每天只有 250 个）。我有 300 ² /2 - 300 = 44,700 个查询要进行，所以显然这个限制对我来说是不够的。

这将是一次性的，关于如何使用 Google Maps API 完成我需要的任何提示？我可以以某种方式运行分发的程序，这样限制只会影响一个实例吗？Google App Engine 会有所帮助吗？

我也欢迎改进算法的建议。如果两栋房子相距很远，而另一栋房子靠近其中一栋，则意味着它不必检查第三栋房子和剩下的房子，因为它们可能很远。我也更关心算法的定性性质，而不是确切的距离，所以也许我可以做出一个简单的近似来减少查询。

谢谢，

我有一个家庭任务：

为了使平面图嵌入的可视化器（或铺设我不知道这个过程的正确词）。

平面图与平面图同构，平面图是在平面上绘制的图，其边不相交。

我需要一个算法来做到这一点，有一篇俄语文章，那里描述了名为“Gamma 算法”的算法，但我想找到更多信息，我什至找不到关于“Gamma 算法”的任何信息（在英文，好像还有别的名字），也没有关于英文的其他算法。

任何人都可以建议算法的名称及其描述的链接吗？

ps 对不起，如果我的英语不好:)

我正在寻找有关 TSP 的相关（2000 年之后）新论文。我找到的所有论文都非常难，需要高水平的数学技能。我正在寻找那些具有简单大学数学知识和良好 Java 和 C 编程知识的人易于阅读的论文（我没有找到任何当前使用这些语言实现 TSP 的论文）。

任何提示将不胜感激。

（编辑）

我想说的是，我正在寻找不需要理解困难公式的论文。例如，一些论文描述了算法或解决方案的哲学。不需要实现该算法，只需描述技术即可。也许使用一些简单的几何......

我找到了一些基于 Lin-Kernighan 方法的论文，看起来还可以……

目标是在具有 300 万个顶点的图中制作许多循环链。

问题是如何在 MySQL 数据库中存储边并保持快速，搜索循环链，使用 Dijkstra 算法可能是？

在你开始向我扔维基百科和博客的链接之前，请听我说完。

我正在尝试找到最佳算法/函数来对...进行依赖排序。每个项目都有其依赖项的列表。

我想要一些基于迭代器的东西，但这不是很重要。

重要的是该算法准确地指出哪些项目是依赖循环的一部分。在这种情况下，我想提供详细的错误信息。

实际上，我正在考虑从“依赖节点”类中对我的项目进行子类化，该类具有完成工作所需的布尔值/函数。欢迎使用酷（但具有描述性）的名称:)

假设我们有一个矩阵M x N，给定两个随机指定的exit和entrance，

entrance找到exit只覆盖矩阵中每个节点一次的路径（上、下、左、右） ？