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

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

Используя знания о поиске соседей, можно перейти к поиску путей в сети. Один из алгоритмов поиска пути между двумя узлами — алгоритм «поиска в ширину» (BFS). В алгоритме BFS вы начинаете с определённого узла и последовательно просматриваете его соседей, затем соседей соседей — и так до тех пор, пока не найдёте целевой узел.

Алгоритмы поиска пути важны тем, что позволяют по-другому оценить значимость узлов — вы увидите это в одном из следующих упражнений.

В этой серии из 3 упражнений вы будете постепенно строить полноценный алгоритм BFS. Задача разбита на 3 части: если выполнить их последовательно, вы получите первую рабочую реализацию алгоритма BFS.

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

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

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

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

  • Создайте функцию path_exists() с тремя параметрами — G, node1 и node2 — которая возвращает информацию о том, существует ли путь между двумя узлами.
  • Инициализируйте очередь узлов для обхода, добавив в неё первый узел — node1. Переменная queue должна быть списком.
  • Выполните итерацию по узлам в queue.
  • Получите соседей текущего узла с помощью метода .neighbors() графа G.
  • Проверьте, содержится ли целевой узел node2 в множестве neighbors. Если да — верните True.

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

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

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

    # Initialize the queue of nodes to visit with the first node: queue
    queue = ____

    # Iterate over the nodes in the queue
    for node in ____:

        # Get neighbors of the node
        neighbors = ____

        # Check to see if the destination node is in the set of neighbors
        if node2 in ____:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return ____
            break
Редактировать и запускать код