python - 如何在 Python 中检查容器类型对象的循环引用

Question

我想实现一个程序来检查容器类型的对象中是否存在循环引用。幸运的是，我在 pymotw 中找到了一个短节目。

我把源码贴在这里了，不过好像不对，正如文章底部的评论所说。

能否根据源码实现正确的版本？

import gc
import pprint
import Queue

class Graph(object):
    def __init__(self, name):
        self.name = name
        self.next = None
    def set_next(self, next):
        print 'Linking nodes %s.next = %s' % (self, next)
        self.next = next
    def __repr__(self):
        return '%s(%s)' % (self.__class__.__name__, self.name)

# Construct a graph cycle
one = Graph('one')
two = Graph('two')
three = Graph('three')
one.set_next(two)
two.set_next(three)
three.set_next(one)

print

seen = set()
to_process = Queue.Queue()

# Start with an empty object chain and Graph three.
to_process.put( ([], three) )

# Look for cycles, building the object chain for each object we find
# in the queue so we can print the full cycle when we're done.
while not to_process.empty():
    chain, next = to_process.get()
    chain = chain[:]
    chain.append(next)
    print 'Examining:', repr(next)
    seen.add(id(next))
    for r in gc.get_referents(next):
        if isinstance(r, basestring) or isinstance(r, type):
            # Ignore strings and classes
            pass
        elif id(r) in seen:
            print
            print 'Found a cycle to %s:' % r
            for i, link in enumerate(chain):
                print '  %d: ' % i,
                pprint.pprint(link)
        else:
            to_process.put( (chain, r) )

Answer 1

算法是这样的:

   func cycleSearch(adjacentNodes, node, visited):  
       if (visited[node]):  
           if (node == start):  
               "found a path"  
           return;  
       visited[node]=YES;  
       for child in adjacentNodes[node]:  
           call cycleSearch(adjacentNodes,child,visited)
       visited[node]=NO;

您的代码实现了 Queu，因此您必须修改它以适应 Queu 模式。但无论如何，该算法都是正确的:

1. 如果我已经访问过该节点并且它与第一个节点相同，那么我找到了一条路径，如果它与第一个节点不同我继续(返回)因为我可能有一个循环。<
2. 我将当前节点设置为visited = YES
3. 对于我所在节点的每个相邻节点，我递归调用此函数以及子节点的相邻节点、子节点和起始节点。
4. 然后我设置 visited = NO。因为如果我到达终点节点没有邻接(所以终点)因此它不是我正在寻找的当前循环的一部分并且我回溯所以就好像我没有去过那里一样。