НачатьНачать бесплатно

Кратчайший путь II

Теперь, когда вы написали код для проверки наличия целевого узла среди соседей, пора расширить ту же функцию и добавить код для случая, когда целевой узел не входит в список соседей.

Весь код, который нужно написать, находится в блоке else — то есть в ситуации, когда node2 не содержится в neighbors.

Это упражнение является частью курса

Введение в анализ сетей на Python

Посмотреть курс

Инструкции к упражнению

  • С помощью метода .add() добавьте текущий узел node в множество visited_nodes, чтобы отслеживать уже посещённые узлы.
  • Добавьте в queue соседей текущего узла node, которые ещё не были посещены. Для этого используйте метод .extend() объекта queue вместе с генератором списка. Метод .extend() добавляет все элементы указанного списка.
    • Выражение результата и переменная итератора в генераторе списка — оба равны n. Итерируемый объект — это итератор neighbors, а условие — если n не входит в множество посещённых узлов.

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

def path_exists(G, node1, node2):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()
    queue = [node1]

    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True

        else:
            # Add current node to visited nodes
            ____

            # Add neighbors of current node that have not yet been visited
            queue.extend([____ for ____ in ____ if ____ not in ____])
Редактировать и запускать код