问题标签 [directed-acyclic-graphs]

我有一个代表属性列表的 DAG。这些性质使得如果 a>b，则 a 具有到 b 的有向边。它也是可传递的，因此如果 a>b 且 b>c，则 a 具有到 c 的有向边。

但是，从 a 到 c 的有向边是多余的，因为 a 有到 b 的有向边，而 b 有到 c 的有向边。我怎样才能修剪所有这些多余的边缘？我正在考虑使用最小生成树算法，但我不确定在这种情况下应用什么合适的算法

我想我可以从每个节点及其所有出边进行深度优先搜索，并比较它是否可以在不使用某些边的情况下到达某些节点，但这似乎非常低效和缓慢。

算法完成后，输出将是所有节点的线性列表，其顺序与图一致。因此，如果 a 具有到 b、c 和 d 的三个有向边。b 和 c 也都有指向 d 的有向边，输出可以是 abcd 或 acbd。

在我的 webapp 中，我们有很多字段汇总了其他字段，而这些字段汇总了更多字段。我知道这是一个有向无环图。

当页面加载时，我计算所有字段的值。我真正想做的是将我的 DAG 转换为一维列表，其中包含计算字段的有效顺序。

例如：A = B + D, D = B + C, B = C + E 高效计算顺序：E -> C -> B -> D -> A

现在我的算法只是迭代地简单地插入到一个列表中，但我遇到了一些开始中断的情况。我在想，需要做的是将所有依赖关系计算成树结构，然后从那里将其转换为一维形式？是否有一种简单的算法可以将这种树转换为有效的排序？

我有一个 DAG。我有这个操作来在两个节点之间添加一条边。

如果 A 可以从 B 到达，则 B 是 A 的父级。如果 A 可以从 B 到达而无需经过另一个节点，则 B 是 A 的直接父节点。

此图的要求是：

1. 没有循环。
2. 对于任何节点，都有一个直接父节点列表 P[1],P[2],P[3]...对于任何 i 和 j，P[i] 都不是 P[j] 的父节点。

如果添加一条边，则不满足要求 1，则不构造该边。如果添加一条边，则不满足要求 2，则构建边，但将修改直接父项，以满足要求 2。

例如有3个节点

• A、直系父母：无
• B、直系父母：A
• C、直系父母：A

现在，如果我在 B 和 C 之间添加一条边，我们有

• C、直系父母：A、B

但是 A 是 B 的父级，不满足要求 2，因此 A 从 C 的直接父级中删除，我们有

• C、直系父母：B

目前这是我所做的：将边缘从 A 添加到 B（这个 A 成为 B 的父级）

1. 通过 BFS 检查 B 是否是 A 的父级。如果是这样，不要添加边缘。（这确保没有循环）
2. 通过 BFS 检查 A 是否已经是 B 的父级。如果是这样，请不要添加边缘。
3. 找到 A 的父级与 B 的直接父级的交集。这是通过通过 BFS 找到 A 的每个父级来完成的。从 B 的直接父级中删除交集，并将 A 添加为 B 的直接父级。（2 和 3 确保满足要求 2）

这很慢。它在 5k 节点级别发生故障（我正在寻找它来处理任何少于 100k 节点的图），速度变得不可接受，添加节点边缘需要 0.02 秒。

我有一种感觉，第 1 步和第 2 步可以用其他算法一步完成。

我曾想过使用拓扑排序，但它必须横穿整个图，这对于我的第 1 步和第 2 步来说是最坏的情况。添加新节点时，排序将被打乱。所以我每次插入都必须运行拓扑排序，所以它不会产生任何好处。对于第 3 步，必须找到 A 的整个父母集。这个过程相当缓慢，因为平均而言它横穿了图表的相当一部分。

我怎样才能使它更有效率？

我有一个带有 s 和 t 顶点的图，我需要找到它之间的最短路径。该图有很多我想利用的特殊属性：

• 该图是一个 DAG（有向无环图）。
• 我可以在 O(|V|) 时间内创建拓扑排序，比传统的 O(|V + E|) 更快。
• 在拓扑排序中，s 是列表中的第一项，t 是最后一项。

有人告诉我，一旦我对顶点进行了拓扑排序，我就可以比我目前的 Dijkstra 统一成本标准更快地找到最短路径，但我似乎找不到它的算法。

伪代码将不胜感激。

编辑：从 s 到 t 的所有路径都具有相同数量的边。边有权重。我正在寻找成本最低的路径。

给定一个 DAG，其中每个节点都属于一个类别，如何将这个图转换为一个表，每个类别都有一个列？转换不必是可逆的，但应该保留有关图结构的有用信息；并且应该是一种“自然”的转换，从某种意义上说，查看图表和表格的人不应该对任何行感到惊讶。它也应该是紧凑的，即只有几行。

例如，给定一个节点 a1,b1,b2,c1 与边 a1->b1, a1->b2, b1->c1, b2->c1 的图（即菱形图），我希望看到以下内容桌子：

我已经对这个问题想了很多，但是我很难想出一种算法来在某些图表上给出直观的结果。考虑具有边 a1->c1, b1->c1 的图 a1,b1,c1。我想要生成这张表的算法：

但也许它应该产生这个：

我正在寻找对这个问题的创造性想法和见解。如果您认为这会有所帮助，请随意改变以简化或限制问题。

头脑风暴！

编辑：

尽管行的顺序无关紧要，但转换应始终生成相同的行集。

在使用 Excel 等进行排序和过滤时，该表应该表现良好。这意味着不能将多个节点打包到表的单个单元格中 - 每个单元格只有一个节点。

前几天我无法正确地表达自己并得到关闭我的答案，所以这是我的第二个镜头：

我需要创建一个基本的 DAG（有向无环图）应用程序，使用常用词，一个基于节点的应用程序。我不需要用于 nw 的 GUI，只需一个控制台示例即可执行整个树。

这是我到目前为止所拥有的：

节点可以有任意数量的输入和任意数量的输出（我如何处理它们？）

我的问题是：如何构造一个 DAG，其中节点总和的输出是节点根的输入，而输出是节点 Output_screen 的输入？

节点（总和）---> 节点（根）---> 节点（输出屏幕）

我会感谢任何帮助，因为我在上面找不到任何 tut

这是一棵树：

1. 将有一个根。

2. 每个树节点都有零个或多个子节点。

3. 允许两个节点指向同一个子节点。假设节点 A 和节点 B 都有子节点 C。

但是，禁止这样做，

节点 A 是节点 B 的后代，节点 B 是节点 A 的后代。

一种被禁止的情况是

节点 A 有一个子节点 C 和节点 D，

节点 C 和 D 都有一个子节点 E，

节点 E 有一个 A 的子节点。

问题是，如何以最快的方式确定这个圈子？

更新：我意识到这是在有向图中找到任何循环。刚才我设法想出了一个类似于 Tarjan 算法的解决方案。

感谢您的评论。

有人可以简单地向我解释什么是有向无环图吗？我看过维基百科，但它并没有真正让我看到它在编程中的用途。

我正在寻找一种算法来检查给定图是否是另一个给定图的子图。

我几乎没有条件让这个 NP 完全问题更可行..

• 这些图有大约 <20 个顶点。
• 图表是 DAG。
• 所有顶点都是非唯一标记的，并且主图和子图中的对应顶点应该具有相同的标签。我不知道我是否使用了正确的术语（因为我没有上过图论课程......）。它会是这样的：

折线图 A--B 是 A--B--A 的子图，但 A--A 不是 A--B--A 的子图。

任何建议都很好。顺便说一句，这不是作业问题。:D

我试图找到一种空间要求适中的快速算法来解决以下问题。

对于 DAG 的每个顶点，在 DAG 的传递闭包中找到其入度和出度的总和。

鉴于此 DAG：

我期待以下结果：

在我看来，这应该是可能的，而无需实际构建传递闭包。我无法在网上找到任何能准确描述这个问题的东西。我有一些关于如何做到这一点的想法，但我想看看 SO 人群能想出什么。