问题标签 [topological-sort]

可能最好用一个小例子来说明。
鉴于关系

正确的输出将是

换句话说，任何给定关系成立的排序都是有效的。

我对最容易实现的解决方案最感兴趣，但速度和时间上最好的 O(n) 也很有趣。

我想使用 aPriorityQueue对图进行拓扑排序。为简洁起见，我想为比较器使用匿名内部类。但是，我需要访问图表g以确定我正在查看的节点的度数。这可能吗？

更正的代码

我有一个具有偏序关系的项目列表，即。e，列表可以被认为是一个偏序集。我想以与此问题相同的方式对该列表进行排序。正如那里正确回答的那样，这称为拓扑排序。

有一个相当简单的已知算法来解决这个问题。我想要一个类似于 LINQ 的实现。

我已经尝试过使用OrderBy扩展方法，但我很确定它无法进行拓扑排序。问题是IComparer<TKey>接口不能表示部分顺序。发生这种情况是因为该Compare方法基本上可以返回 3 种值：zero、negative和positive，分别表示 are-equal、is-less-than和is-greater-then。只有有办法返回are-unrelated ，才有可能找到可行的解决方案。

从我的偏见的角度来看，我正在寻找的答案可能由一个IPartialOrderComparer<T>接口和一个扩展方法组成，如下所示：

这将如何实施？IPartialOrderComparer<T>界面会是什么样子？你会推荐一种不同的方法吗？我很想看到它。也许有更好的方式来表示偏序，我不知道。

我正在将工作场所的基础设施转换为使用 git 而不是 svn。整体迁移进展顺利，但我们有一个我开发的工具来进行 SQL 模式迁移。

为了处理单个模式更改依赖关系，迁移脚本使用颠覆关键字替换将最后更改的修订号放入模式中。使用 git，我们不能使用相同的想法，因为修订历史是非线性的（我们完全打算利用分支功能）。

因此，如何从 git 中获取提交 id 的拓扑排序列表？除此之外，有人对如何处理这个问题有更好的想法吗？

我编写了一个源删除算法来对我们数据库中表之间的一些依赖关系进行排序，结果证明我们有一个循环。为简单起见，假设我们有表 A、B、C 和 D。边是这样的：

如您所见，这里有两个循环。一个在 A 和 B 之间，另一个在他们四个之间。这种类型的排序总是会在最大的循环中窒息吗？还是不一定如此？

我的女朋友在一次采访中被问到这个问题，我非常喜欢它，我想我会分享它......编写一个接收字典（单词数组）的算法。该数组按字典顺序排序，但 abc 顺序可以是任何值。例如，它可以是 z、y、x、..、c、b、a。或者它可能完全搞砸了：d，g，w，y，......它甚至不需要包括所有的abc字母，最后它根本不必是字母。它可以是构成字符串的任何符号。例如，它可以由 5、α、!、@、θ 组成……你明白了。这取决于你的算法来发现字母是什么（简单的部分）。

该算法应返回符号的正确字典顺序。

注意/需要考虑的事项： 1. 对于给定的字典，您是否总能发现所有字母的完整顺序？考虑一个只有 1 个单词的字典，有多个符号... 2. 你不能假设字典没有错误。该算法应确定字典是否包含矛盾并输出存在错误。3. 提示：想一个好的数据结构来表示你发现的符号之间的关系。这应该使问题更容易。

我可能会在明天发布我的解决方案。我绝不声称它是最有效的。我想先看看别人的想法。希望你喜欢这个问题

PS 我认为发布解决方案的最佳格式是使用伪代码，但我将此留给您考虑

我有上面的元组列表，我需要用以下逻辑对其进行排序......每个元组的第二个元素取决于第一个元素，例如（课程，会话）->会话取决于课程等等......

我想要一个基于它们依赖的优先级的排序列表，较少或独立的对象将首先出现，所以输出应该如下所示，

我有一组数据，我需要对其执行拓扑排序，并带有一些假设和约束，我想知道是否有人知道适用于此的现有有效算法。

• 已知数据关系会形成 DAG（因此无需担心循环）。
• 从 A 到 B 的边表明 A 依赖于 B，因此 B 在拓扑排序中必须出现在 A 之前。
• 图不一定是连通的；也就是说，对于任何两个节点 N 和 M，可能无法通过沿边从 N 到 M（即使您忽略边方向）。
• 数据关系是单独链接的。这意味着当存在从 A 指向 B 的边时，只有 A 节点包含有关边存在的信息。

问题可以表述如下：

S给定图G中可能有也可能没有传入边的一组节点，找到子图的拓扑排序，该子图G'由集合中G的任何节点可到达的所有节点组成S（服从边方向）。

这混淆了拓扑排序的常用方法，因为它们要求集合中的节点S没有任何传入边，这在我的情况下是不正确的。病理情况是：

哪里S = {B, C}。一个合适的排序应该是D, B, C，但是如果一个正常的拓扑排序算法之前碰巧考虑B过C，它最终会C, D, B是 ，这是完全错误的。（请注意，A它不会出现在结果排序中，因为它无法从 到达S；它在那里给出了一个示例，其中所有节点都S可能具有传入边）

现在，我不得不想象这是一个长期解决的问题，因为这本质上是程序喜欢apt并且yum在一个安装命令中指定多个包时必须做的事情。但是，当我搜索“依赖解析算法”之类的关键词时，我得到的结果描述了正常的拓扑排序，它不能处理这种特殊情况。

我可以想到几种方法来做到这一点，但没有一种方法看起来特别优雅。我想知道是否有人有一些指向适当算法的指针，最好是可以在数据上一次通过的算法。

有谁知道 Java Jung2 图形库是否提供了在给定起始向量的情况下遍历有向图（有向图）的内置功能？我确实看到有一个BFSDistanceLabeler类可以返回距离图，可以这样做，但是我需要对值进行排序（首先是最高距离）并遍历排序集。

我正在使用 Maven 为 Javascript 创建一个依赖管理工具，所以我正在考虑使用 Jung2 来维护我的依赖图。

我有一个收藏：

对中的第一个项目是某个对象（项目），第二个是第一个所依赖的相同类型对象的集合。我想List<Item>按依赖顺序获得一个，所以没有项目依赖于第一个元素等等（没有循环依赖！）。

输入：

结果：

谢谢你。

解决方案：

拓扑排序（感谢Loïc Février的想法）

和

C#上的示例，Java上的示例 （感谢xcud的优秀示例）