Python: обнаружение цикла с использованием next и iter в убывающем наборе - PullRequest
Новая
       18

Python: обнаружение цикла с использованием next и iter в убывающем наборе

0 голосов
/ 31 мая 2018

Я следил за видео Тушара Роя об обнаружении циклов в ориентированных графах.Я понимаю использование белых, серых и черных наборов для обнаружения цикла, но главное, что я не понимаю, это то, как при проверке длины набора white, next(iter(white)) будет знать, куда идти дальшетак как установленный размер изменился.В документации сказано, что iter дает вам объект итератора, а next извлекает следующий элемент.Является ли главное, что итератор оценивается каждый раз по-разному?

Вы можете найти код здесь или здесь . 

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)

1 Ответ

0 голосов
/ 31 мая 2018

next(iter(white)) просто возвращает элемент из набора white.Набор не упорядочен, поэтому нет гарантии, какой элемент выбран.Вы правы, полагая, что итератор оценивается для каждой итерации цикла.

Тот факт, что набор изменяется по мере прохождения цикла, запрещает использование цикла for.

...