LoslegenKostenlos loslegen

Kürzester Pfad II

Nachdem du den Code geschrieben hast, um zu prüfen, ob der Zielknoten in den Nachbarn enthalten ist, erweiterst du jetzt dieselbe Funktion um den Code für den Fall, dass der Zielknoten nicht in den Nachbarn enthalten ist.

Den gesamten Code, den du schreiben musst, platzierst du im else-Zweig; also wenn node2 nicht in neighbors ist.

Diese Übung ist Teil des Kurses

Einstieg in die Netzwerkanalyse mit Python

Kurs anzeigen

Anleitung zur Übung

  • Füge mit der Methode .add() den aktuellen Knoten node zur Menge visited_nodes hinzu, um nachzuhalten, welche Knoten bereits besucht wurden.
  • Füge die Nachbarn des aktuellen Knotens node, die noch nicht besucht wurden, zu queue hinzu. Verwende dafür die Methode .extend() von queue zusammen mit einer List Comprehension. Die Methode .extend() hängt alle Elemente einer übergebenen Liste an.
    • Der Ausgabeausdruck und die Iteratorvariable der List Comprehension sind beide n. Das Iterierbare ist der Iterator von neighbors, und die Bedingung lautet, dass n nicht in den besuchten Knoten ist.

Interaktive Übung

Vervollständige den Beispielcode, um diese Übung erfolgreich abzuschließen.

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 ____])
Code bearbeiten und ausführen