2元组python列表中的循环检测 [英] Cycle detection in a 2-tuple python list

问题描述

给出2元组(源，目标)中的边列表，是否有任何有效的方法来确定循环是否存在?例如，在下面的示例中，存在一个循环，因为1-> 3-> 6-> 4->1.一个想法是计算列表中每个整数的出现次数(同样，是否有任何有效的方法可以这个?).有什么更好的办法吗?我看到10,000个2元组边缘信息有问题.

Given a list of edges in 2-tuple, (source, destination), is there any efficient way to determine if a cycle exists? Eg, in the example below, a cycle exists because 1 -> 3 -> 6 -> 4 -> 1. One idea is to calculate the number of occurrence of each integer in the list (again, is there any efficient way to do this?). Is there any better way? I am seeing a problem with 10,000 of 2-tuple edge information.

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

推荐答案

我假设您要在由边缘列表表示的无向图中找到一个循环，并且您不希望计算大小的平凡"循环1或2.

I'm assuming you want to find a cycle in the undirected graph represented by your edge list and you don't want to count "trivial" cycles of size 1 or 2.

您仍然可以使用标准的深度优先搜索，但是您需要稍微注意节点的颜色(一个简单的标志来告知您已经访问过的节点是不够的):

You can still use a standard depth-first search, but you need to be a bit careful about the node coloring (a simple flag to signal which nodes you have already visited is not sufficient):

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个级别的后边缘.如果存在一个简单的大小为> = 2的循环，这就是正确的情况.通过存储父指针，您实际上也可以在发现循环时也打印该循环.

This will detect if there is a back edge in the depth-first forest that spans at least 2 levels. This is exactly the case if there is a simple cycle of size >= 2. By storing parent pointers you can actually print the cycle as well if you found it.

对于大型图形，您可能希望使用显式堆栈而不是递归，如维基百科.

For large graphs you might want to use an explicit stack instead of recursion, as illustrated on Wikipedia.

这篇关于2元组python列表中的循环检测的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！