Python: 在递减集合中使用 next 和 iter 检测循环

Question

我正在关注 Tushar Roy 的 video 关于检测有向图中的循环。我了解使用白色、灰色和黑色集来检测循环，但我不明白的主要是当我们检查 white 集的长度时，next(iter(white)) 会如何知道由于设置大小已更改，下一步要去哪里。文档说 iter 给你一个迭代器对象， next 会检索下一个项目。重点是迭代器每次求值都不一样吗？

您可以找到代码 here or here。

def has_cycle(graph):
    white = set()
    gray = set()
    black = set()

    for vertex in graph.all_vertex.values():
        white.add(vertex)

    while len(white) > 0:
        current = next(iter(white))       
        if dfs(current, white, gray, black) == True:
            return True

    return False        

def dfs(current, white, gray, black):
    move_vertex(current, white, gray)
    for neighbor in current.adjacent_vertices:
        if neighbor in black:
            continue
        if neighbor in gray:
            return True
        if dfs(neighbor, white, gray, black) == True:
            return True

    move_vertex(current, gray, black)
    return False

def move_vertex(vertex, source_set, destination_set):
    source_set.remove(vertex)
    destination_set.add(vertex)

Answer 1

next(iter(white)) 只是 returns 集合 white 的一个元素。集合未排序，因此无法保证选择了哪个元素。您认为迭代器是针对循环的每次迭代进行评估的，这是正确的。

集合随着循环的进行而变化的事实禁止使用 for 循环。

Python: 在递减集合中使用 next 和 iter 检测循环

Python: Detect cycle using next and iter in a diminishing set

python

iterator

depth-first-search

next