擅长:python、mysql、java
<p>我们可以从一个给定的“开始节点”执行“闭包”操作,方法是从当前“端点”重复获取“图形边”的并集,直到找不到新的端点。我们最多需要这样做(节点数-1)次,因为这是路径的最大长度。(这样做可以避免在有循环的情况下陷入无限递归;在一般情况下,这样做会浪费迭代,但是可以避免检查是否完成的工作,即在给定的迭代中没有进行任何更改。)</p>
<pre><code>from collections import defaultdict
def transitive_closure(elements):
edges = defaultdict(set)
# map from first element of input tuples to "reachable" second elements
for x, y in elements: edges[x].add(y)
for _ in range(len(elements) - 1):
edges = defaultdict(set, (
(k, v.union(*(edges[i] for i in v)))
for (k, v) in edges.items()
))
return set((k, i) for (k, v) in edges.items() for i in v)
</code></pre>
<p>(实际上我测试过一次;)</p>