ПочатиПочніть безкоштовно

Найкоротший шлях I

Ви можете використати знання про пошук сусідів, щоб спробувати знаходити шляхи в мережі. Один із алгоритмів пошуку шляху між двома вузлами — це алгоритм «breadth-first search» (BFS), або пошук у ширину. У BFS ви стартуєте з певного вузла та ітеративно переглядаєте його сусідів і сусідів сусідів, доки не знайдете цільовий вузол.

Алгоритми пошуку шляху важливі, адже вони надають ще один спосіб оцінювати важливість вузлів; ви побачите це в одній із наступних вправ.

У цьому наборі з 3 вправ ви крок за кроком підете до підсумкового алгоритму BFS. Завдання поділено на 3 частини, і якщо виконати їх послідовно, ви отримаєте першу робочу реалізацію алгоритму BFS.

Ця вправа є частиною курсу

Вступ до аналізу мереж у Python

Переглянути курс

Інструкції до вправи

  • Створіть функцію path_exists(), яка має 3 параметри — 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
Редагувати та запускати код