如何在Python中加入链接以获得循环？

Question

我有一个链接列表,想知道连接的路径/周期.

我的链接看起来像这样:

[[0, 3], [1, 0], [3, 1]]

我希望答案是这样的循环(或任何其他匹配循环):

[0,3,1]

因此,您获取第一个子列表的第一个元素,然后您获取第二个元素,并查找以此元素开头的下一个子列表,然后重新开始.

有一种优雅的方式来实现这一目标吗？我尝试了reduce函数,但是链接必须以链接匹配的方式进行排序.

Answer 1

使用发电机有一种非常优雅的方式:

def cycle(lst, val, stop=None):
    d = dict(lst)
    stop = stop if stop is not None else val
    while True:
        yield val
        val = d.get(val, stop)
        if val == stop: break

首先,它允许自然迭代:

>>> for x in cycle([[0, 3], [1, 0], [3, 1]], 0):
....    print x
....
0
3
1

其次,它允许轻松创建列表:

>>> list(cycle([[0, 3], [1, 0], [3, 1]], 0))
[0, 3, 1]

最终,它允许无限项生成:

>>> generator = cycle([[0, 3], [1, 0], [3, 1]], 0, Ellipsis)
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3
>>> generator.next()
... 1
>>> generator.next()
... 0
>>> generator.next()
... 3

Answer 2

考虑使用networkx包:

import networkx as nx
G = nx.DiGraph() #creates directed graph
G.add_edges_from([[0, 3], [1, 0], [3, 1]])
print nx.simple_cycles(G).pop()[:-1]

输出:

>> [0, 3, 1]