0

我以一种非常愚蠢的方式编写了一个环检测程序。任何人都可以帮助改进它吗？以下代码是查找所有 5 元环。我需要一个能够找到 N 成员环的通用函数，其中 N 通常小于 10。谢谢一百万！

在我的问题中，我有大约 2000 分。每个点连接到其他几个点，这些连接点存储在neighbor_list. 并point[i].neighbor_list()返回点 [i] 的邻居列表。下面代码的思路是从一个点开始，遍历它的neighbor list和它的neighbor的neighbor list，以此类推，找到返回原点的routes/cycles/rings。我的代码的中心部分如下，它只找到由 5 个点组成的环。我需要一个通用代码来查找所有 N 成员环。如果有任何不清楚的地方，请发表评论。 

for r0 in range(2000): #ring member 0
    rin.append(r0)
    for r1 in point[r0].neighbor_list():
        rin.append(r1) #ring member 1 
        for r2 in point[r1].neighbor_list():
            if r2 == r0: continue # to avoid the case of a-b-a ...
            else: rin.append(r2)
            for r3 in point[r2].neighbor_list():
                if r3 == r1: continue
                else: rin.append(r3)
                for r4 in point[r3].neighbor_list():
                    if r4 == r2: continue
                    else: rin.append(r4)
                    for r5 in point[r4].neighbor_list():
                        if r5 == r0: 
                            rin.append(r5)
                            rings.append(list(rin)) # find a ring, save it
                            rin.pop()
                        else: continue  
                    rin.pop()
                rin.pop()
            rin.pop()
        rin.pop()
    rin.pop()
4

1 回答 1

1

您试图在无向图中找到大小为 N 的循环。

您可能会找到所有循环，然后选择大小合适的循环。看到这个答案。 在无向图中查找所有循环

于 2013-08-27T16:06:17.013 回答