在二元组Python列表中检测循环

Question

给定一组边的信息，每条边用一个二元组表示，格式是（起点，终点），有没有什么高效的方法来判断是否存在循环？比如下面这个例子，存在一个循环，因为 1 指向 3，3 指向 6，6 指向 4，然后又回到 1。一个想法是统计每个整数在列表中出现的次数（不过，这样做有没有更高效的方法呢？）。有没有更好的办法？我现在遇到的问题是有 10,000 条二元组的边信息。

a = [(1,3), (4,6), (3,6), (1,4)]

Answer 1

我猜你是想在用边列表表示的无向图中找出一个循环，而且你不想计算“简单”的循环，比如大小为1或2的循环。

你可以使用一种叫做深度优先搜索的标准方法，但在处理节点颜色时需要小心一点（仅仅用一个简单的标记来表示你已经访问过的节点是不够的）：

from collections import defaultdict

edges = [(1,3), (4,6), (3,6), (1,4)]
adj = defaultdict(set)
for x, y in edges:
    adj[x].add(y)
    adj[y].add(x)

col = defaultdict(int)
def dfs(x, parent=None):
    if col[x] == 1: return True
    if col[x] == 2: return False
    col[x] = 1
    res = False
    for y in adj[x]:
        if y == parent: continue
        if dfs(y, x): res = True
    col[x] = 2
    return res

for x in adj:
    if dfs(x):
        print "There's a cycle reachable from %d!" % x

这样做可以检测到在深度优先搜索的过程中是否存在一个“回边”，这个回边至少跨越了两个层级。如果存在一个大小大于等于2的简单循环，正好就是这种情况。通过存储父节点的指针，如果找到了循环，你实际上还可以打印出这个循环。

对于较大的图，你可能想用一个显式的栈来代替递归，就像维基百科上展示的那样。