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

Найкоротший шлях 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 ____])
Редагувати та запускати код