问题标签 [graph-traversal]

在 haskell 中表示一棵树非常容易：

但那是因为它不需要命令式“指针”的概念，因为每个节点/叶子都有一个，并且只有一个父级。我想我可以将它表示为 s 列表的列表......为那些没有路径的节点Maybe Int创建一个表......但这看起来真的很丑陋和笨拙。NothingJust n

我想知道是否有一种算法：给定一个完全连接的n节点图（具有不同的权重）......会给我从节点A（起始节点）到所有其他节点的最便宜的循环，然后返回到节点 A？有没有办法改变像 Primm 的算法来完成这个？

谢谢你的帮助

编辑：我忘了提到我正在处理一个无向图，所以每个顶点的入度 = 出度。

我引用人工智能：一种现代方法：

深度优先搜索的属性很大程度上取决于使用的是图搜索还是树搜索版本。避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它最终会扩展每个节点。另一方面，树搜索版本并不完整 [...]。深度优先树搜索可以在不增加内存成本的情况下进行修改，以便根据从根到当前节点的路径上的状态检查新状态；这避免了有限状态空间中的无限循环，但不能避免冗余路径的扩散。

我不明白图形搜索如何完整而树搜索不是，因为树是一个特定的图形。

此外，我不清楚“无限循环”和“冗余路径”之间的区别......

有人可以向我解释一下吗？

附言。对于那些有这本书的人，它是第 86 页（第 3 版）。

我想要一个关于在图形/网络上操作的好的 javascript 库的推荐。我对可视化不感兴趣，只对寻找最短路径和生成树之类的东西感兴趣。

我看过crow，看起来不错，但是是面向对象的。

像 underscore.js 这样的功能模型是我的偏好，但不是必需的。

我正在研究一个深入研究的问题：

有一个连通的无向图。我需要访问所有节点而不多次访问节点。我可以在任意节点开始和结束。

我该怎么办？我应该将算法Floyd-Warshall应用于所有可能的起始节点还是有更好的方法？

谢谢。

我应该如何继续这样做？这是一个家庭作业，我有一个很大的问题。现在，问题是我不能使用库。

我有一个像这样的图表：

使用字典，取自文件。

我正在使用http://www.python.org/doc/essays/graphs/上的算法来查找所有路径，所以那里没有问题。

但是现在我有了从一个点到另一个点的所有路径，我需要对权重求和并得到它的全部成本。

如果你能帮助我，并指导我一些好的方法来接近它，我将不胜感激。

我正在尝试创建一个将执行以下搜索的TraversalDescription ；

• 仅返回具有特定属性的节点（“type”==“PERSON”）
• 返回一定数量的结果（整个图很大，我们只对局部图感兴趣）
• 可以使用任何关系类型

我还没有走得很远，我似乎无法弄清楚如何为节点属性创建评估器；

我有一个类似于下面的无向图，我需要实现一个图遍历算法。 示例：http:
//i.imgur.com/15L6m.png

这个想法是每个顶点是一个城市，每个边缘是一条道路。
边的权重表示遍历指定边所需的时间。
条件是：

1. 每条边都在指定的时间窗口中打开以进行遍历：Time Open1、Time Open2、TimeClose1、Time Close2 - 当前时间必须在这些时间间隔内才能遍历边。
   
2. 只有一些顶点必须被访问。每个顶点必须在指定的时间窗口内至少访问一次：Time Open1、Time Open2、TimeClose1、Time Close2 - 当前时间必须在这些时间间隔内，以便将顶点标记为已访问。
   
3. 起点始终是顶点 0
   

对于我的示例，我有：
必须访问的顶点及其时间窗口（不考虑 -1 的值）：

边在以下时间窗口中打开（不考虑 -1 的值）：

所以基本思想是从顶点 0 开始，在考虑指定时间的情况下找到遍历顶点 1、4 和 5 的最短路径。
此外，例如，如果您完成了 0-1 但不能使用 1-5，则可以执行 0-1-0-1-5。

我现在正在使用的一个可能的解决方案是：
从 0 开始。找到最近的顶点以在最短的时间内标记（我使用修改后的 Dijkstra 算法）。这样做直到我标记了所有需要的顶点。问题是我认为我没有找到所有的可能性，因为正如我所说，你也可以像 0-1-0-1-5 组合一样移动，最后你可能会得到一条更短的
路线.

为了使它更清楚，我必须找到最短路径，以便我从顶点 0 开始，以一个目标顶点结束，同时我已经访问了所有其他目标顶点至少一次，尊重施加在边缘和目标顶点上的条件。
例如：
一个可能的解决方案是 0 - 4 - 3 - 5 - 1 总时间为 60+50+60+50=220
从 0 我也可以直接转到 5 但如条件中所述以标记顶点 5我必须有 170 到 450 之间的累积时间。另外，如果我去 0-4，我不能使用边缘 4-2，因为它在 80 处打开并且我的累积时间是 60。注意我可以使用 0-4-3，因为 4 -3 在 60 处打开，而执行 0-4 所需的时间等于 60。

首先，我将使用最多 20 个顶点和大约 50 条边。

解决方案 1：
0
1 4 5 0 2 5 0 2 3 0 1 3

我所做的是通过访问每个相邻顶点构建类似于树的东西来遍历图形。我在以下情况下停止扩展分支：
1. 我有太多重复项，例如我有 0 1 0 4 0 1 0 - 所以我停止了，因为我有一组重复的 0 值，即 4
2. 我找到一条包含所有要标记的顶点
3. 我发现一条道路比另一条完整的道路花费更长的时间
4. 我无法创建另一个节点，因为边是封闭的

解决方案2：

应用@Boris Strandjev 示例，但我有一些问题：

我必须在其间隔内至少访问节点 1,4 和 5 一次，允许在间隔外访问但不标记。对于一个顶点，我有 {(< id1, id2id3id4>, time)}，其中 id1 是当前顶点的 ide，id2-4 表示 1,4,5 的布尔值，如果在指定的时间间隔内访问，时间 -路径中的当前时间

编辑：

我最终使用了上述两种解决方案的组合。一切似乎都很好。

我有一个要遍历的有向无环加权图。

有效解决方案路径的约束是：

1. 考虑到第二个约束，路径中遍历的所有边的权重之和必须是图中可能的最高值。
2. 在所选路线中必须访问过恰好 N 个顶点（包括开始和结束顶点）。

通常，该图将具有大量顶点和边，因此尝试所有可能性不是一种选择，并且需要相当有效的算法。

为这个问题寻找一些指针或合适的算法。我知道使用 Dijkstra 算法很容易满足第一个条件，但我不确定如何结合第二个条件，甚至不知道从哪里开始寻找。

如果需要任何其他信息，请告诉我。

给定一个无向循环图，我想通过广度优先搜索或深度优先搜索找到所有可能的遍历。给出一个图作为邻接列表：

所以来自根 A 的所有 BFS 路径都是：

对于 DFS：

我将如何以一种有意义的方式在算法上生成这些遍历？我想可以生成字母的所有排列并检查它们的有效性，但这对我来说似乎是最后的手段。

任何帮助，将不胜感激。