算法如果周期存在拓扑排序(Algorithm for topological sorting if

一些编程语言（如哈斯克尔）允许模块之间循环依赖。由于编译器需要知道在编译一个模块导入的所有模块的所有定义，它通常如果某些模块导入对方互相做一些额外的工作，或任何其他类型的循环发生。在这种情况下，编译器可能不能够尽可能多的优化代码作为不具有进口周期，因为进口功能可能尚未被分析的模块。通常只有一个周期的模块必须被编译这种方式，作为二进制对象没有依赖条件。让我们把这样的模块回路断路器

特别是如果进口周期是交错有趣的是知道，如何编译数百模块组成的大项目时，最小化回路断路器的数量。

是否有给定一组依赖条件的输出需要被编译成环式破碎机成功编译程序模块的最小数量的算法？

例

我试图澄清我的意思在这个例子。

考虑与四个模块项目A ， B ， C和D 。这是这些模块间的依赖关系的列表，条目X y装置y取决于x ：

A C
A D
B A
C B
D B

同样的关系可视化作为一个ASCII图：

D ---> B
^    / ^
|   /  |
|  /   |
| L    |
A ---> C

有两个循环在这种依赖性的曲线图： ADB和ACB 。为了打破这些周期一个可以例如编译模块C和D为环的断路器。显然，这是不是最好的方法。编译A作为循环断路器是完全足以打破这两个循环，你需要编译少了一个模块作为循环断路器。

Answer 1:

这是被称为NP困难（和APX-硬）的问题最小反馈顶点集。一个近似算法由于DEMETRESCU和Finocchi（PDF，组合算法在向图（2003年）“反馈问题）的工作原理以及在实践中时，有没有简单的长周期，因为我希望为您的应用。

Answer 2:

这里是如何做到这一点在Python：

from collections import defaultdict

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    for h, t in dependency_pairs:
        num_heads[t] += 1
        tails[h].append(t)

    ordered = [h for h in tails if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.iteritems() if heads]
    return ordered, cyclic

def is_toposorted(ordered, dependency_pairs):
    '''Return True if all dependencies have been honored.
       Raise KeyError for missing tasks.
    '''
    rank = {t: i for i, t in enumerate(ordered)}
    return all(rank[h] < rank[t] for h, t in dependency_pairs)

print topological_sort('aa'.split())
ordered, cyclic = topological_sort('ah bg cf ch di ed fb fg hd he ib'.split())
print ordered, cyclic
print is_toposorted(ordered, 'ah bg cf ch di ed fb fg hd he ib'.split())
print topological_sort('ah bg cf ch di ed fb fg hd he ib ba xx'.split())

运行时是线性正比于边缘（依赖对）的数目。

该算法是围绕一个查找表举办名为num_heads，保持计数的前辈（进入箭头）的数量。在ah bg cf ch di ed fb fg hd he ib例如，计数是：

node  number of incoming edges
----  ------------------------
 a       0
 b       2
 c       0
 d       2
 e       1
 f       1  
 g       2
 h       2
 i       1

该算法通过前无古人“visting”节点。例如，节点a和c没有传入的边缘，所以它们首先被访问。

访问意味着该节点是输出和来自图中移除。当一个节点被访问，我们遍历其继承人和减一的来电数量。

例如，在访问节点a ，我们去它的后继h一（以便于减少它的到来计数h 2成为h 1 。

同样地，来访节点时c ，我们遍历其后继f和h ，由一个递减其计数（以使得f 1变f 0和h 1变成h 0 ）。

节点f和h不再有入边，所以我们重复它们输出，直到所有的节点都被访问从图中移除它们的过程。在该示例中，访问顺序（拓扑排序是）：