Zacznij terazZacznij za darmo

Najkrótsza ścieżka II

Masz już kod sprawdzający, czy węzeł docelowy jest obecny w sąsiadach (neighbors). Teraz rozszerzysz tę samą funkcję o kod obsługujący przypadek, gdy węzeł docelowy nie jest obecny w sąsiadach.

Cały kod, który trzeba napisać, znajduje się w gałęzi else — czyli w sytuacji, gdy node2 nie należy do neighbors.

To ćwiczenie jest częścią kursu

Wprowadzenie do analizy sieci w Pythonie

Zobacz kurs

Instrukcje do ćwiczenia

  • Korzystając z metody .add(), dodaj bieżący węzeł node do zbioru visited_nodes, aby śledzić już odwiedzone węzły.
  • Dodaj do queue tych sąsiadów bieżącego węzła node, którzy nie zostali jeszcze odwiedzeni. W tym celu użyj metody .extend() obiektu queue wraz z wyrażeniem listowym. Metoda .extend() dołącza wszystkie elementy podanej listy.
    • Wyrażenie wyjściowe i zmienna iteratora wyrażenia listowego to oba n. Iterowalnym obiektem jest iterator neighbors, a warunek sprawdza, czy n nie należy do odwiedzonych węzłów.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

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 ____])
Edytuj i uruchom kod