问题标签 [directed-graph]

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件，它们的执行顺序相互依赖，我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直都在这样做——但我的 google-fu 今天一直很弱。什么是“首选”算法？

我有大约 3500 个防洪设施，我想将它们表示为一个网络来确定流动路径（本质上是一个有向图）。我目前正在使用 SqlServer 和 CTE 递归地检查所有节点及其上游组件，只要上游路径不分叉很多，它就可以工作。但是，由于增加了上游复杂性，一些查询比其他查询花费的时间呈指数增长，即使它们在物理路径上并不远（即两个或三个“下游”段）。在某些情况下，我已经让它在终止查询之前超过十分钟。我使用的是一个简单的两列表格，一列是设施本身，另一列是第一列中列出的设施的上游。

我尝试使用当前工具添加索引以帮助加快速度，但这没有任何区别。而且，对于图中可能的连接，任何节点都可以有多个上游连接，并且可以从多个“下游”节点连接。

数据中肯定有可能存在循环，但我还没有找到验证这一点的好方法（除了 CTE 查询报告最大递归计数命中；这些很容易修复）。

所以，我的问题是，我存储这些信息是否错误？除了 CTE 之外，还有更好的方法来查询上游点吗？

是否有一种有效的算法来检测有向图中的循环？

我有一个有向图，表示需要执行的作业计划，作业是节点，依赖项是边。我需要在该图中检测导致循环依赖的循环错误情况。

锦标赛图和有向完全图是一回事吗？而且，锦标赛图中的所有顶点是否都具有相同数量的边？

我有一个由我的应用程序用户分类的项目列表（下面的蓝色节点）。类别本身可以被分组和分类。

生成的结构可以表示为有向无环图 (DAG)，其中项目是图拓扑底部的汇，顶部类别是源。请注意，虽然某些类别可能定义明确，但很多类别将由用户定义并且可能非常混乱。

例子：

_{（来源：theuprightape.net）}

在该结构上，我想执行以下操作：

• 查找特定节点下的所有项目（汇）（欧洲的所有项目）
• 查找通过所有一组 n 个节点的所有路径（如果有）（所有通过 SMTP 从 example.com 发送的项目）
• 找到位于所有节点集下方的所有节点（交叉点：goyish brown foods）

第一个似乎很简单：从节点开始，沿着所有可能的路径到底部并在那里收集项目。但是，有没有更快的方法？记住我已经通过的节点可能有助于避免不必要的重复，但是还有更多的优化吗？

我该如何处理第二个？第一步似乎是确定集合中每个节点的高度，以确定从哪个（s）开始，然后找到低于该集合其余部分的所有路径。但这是最好的（甚至是好的）方法吗？

维基百科上列出的图遍历算法似乎都与寻找特定节点或两个节点之间最短或最有效的路线有关。我认为两者都不是我想要的，还是我只是看不到这如何适用于我的问题？我还应该在哪里阅读？

我可以轻松地为有向图的节点定义数据类型。

我可以使用 show 函数将图形保存到文件中，然后使用 read 恢复它。但是，show 无法应对循环。有没有一种简单的方法来保存和恢复图表？

我需要在复杂的图形结构中找到一条或多条路径。该图是使用与此类似的东西构建的：

使这变得复杂的是节点可以引用回更早的节点。例如，

A -> C -> E -> A

我需要做的是获取一个堆栈列表，这些堆栈代表通过节点的路径，直到我到达具有特定值的节点。由于可能有一些非常大的路径可用，我们可以尝试最多的节点。

有没有人有办法构建这个（或类似的东西）？我过去做过递归，但出于某种原因，我脑子里全是放屁。我的问题指定了一个 lambda 表达式，但不一定需要使用 lambda。我将不胜感激任何解决方案。

旁注：我从 aku 对这个递归问题的出色回答中提升了课程。虽然下面显示的他优雅的解决方案遍历了树结构，但它似乎没有足够的灵活性来做我需要的事情（例如，关闭圆形路径并跟踪成功的路径）。

编辑：

根据下面评论和答案的输入，我在 CodeProject 中找到了一个很好的解决方案。它使用 A* 路径查找算法。 链接在这里。

如何检查有向图是否是无环的？算法是如何命名的？我会很感激参考。

这里的图表是指类似于这些图像的东西：

理想的解决方案是：

• 仅使用托管代码
• 允许输出到位图图像
• 允许输出到 WPF 元素
• 包括某种交互式表面，用于显示支持缩放、平移和重组节点的图形

我也有兴趣了解可能用作此类工作起点的项目。如果它需要一些发展来实现我想要的，那么我准备好解决它。这个目标中最复杂的部分似乎是在合理的时间范围内获得图形布局。

我想实现一个节点接口，基本上是一个DAG，其中每个节点对其输入连接执行操作，并输出一些东西（你可以连接到另一个节点）

一些示例应用程序：

• 苹果“摇一摇” ——截图
• 铸造厂“核弹” ——截图
• MindNode - 截图
• vvvv -截图
• 石英作曲家-截图

作为第一个目标，我想要一个只有 2 个节点的图形应用程序。一个“数字”，它简单地输出一个固定的数字，一个“加”节点，它接受两个输入并输出两者的总和。

正如人们到目前为止所回答的那样，我对如何在代码中表示数据有一个粗略的想法，例如在 Python 的伪代码中：

我将如何围绕此包装自定义 GUI？像下面这样的东西，但手绘略少！

我从哪里开始？我目前计划用 Objective-C/Cocoa 编写它，尽管我非常愿意接受其他语言的建议。