LoslegenKostenlos loslegen

Kürzester Weg I

Du kannst dein Wissen über das Finden von Nachbarn nutzen, um Pfade in einem Netzwerk zu finden. Ein Algorithmus zur Pfadsuche zwischen zwei Knoten ist die „Breadth-First Search“ (BFS), also die Breitensuche. Bei BFS startest du von einem bestimmten Knoten und suchst iterativ dessen Nachbarn sowie die Nachbarn der Nachbarn, bis du den Zielknoten findest.

Pfadsuch-Algorithmen sind wichtig, weil sie eine weitere Möglichkeit bieten, die Bedeutung von Knoten zu bewerten – das siehst du in einer späteren Übung.

In diesem Satz von 3 Übungen arbeitest du dich Schritt für Schritt bis zum finalen BFS-Algorithmus vor. Das Problem wurde in 3 Teile aufgeteilt. Wenn du sie nacheinander löst, erhältst du eine erste Implementierung des BFS-Algorithmus.

Diese Übung ist Teil des Kurses

Einstieg in die Netzwerkanalyse mit Python

Kurs anzeigen

Anleitung zur Übung

  • Erstelle eine Funktion namens path_exists() mit 3 Parametern – G, node1 und node2 – die zurückgibt, ob ein Pfad zwischen den beiden Knoten existiert oder nicht.
  • Initialisiere die Warteschlange der zu besuchenden Knoten mit dem ersten Knoten node1. queue sollte eine Liste sein.
  • Iteriere über die Knoten in queue.
  • Ermittle die Nachbarn des Knotens mit der Methode .neighbors() des Graphen G.
  • Prüfe, ob der Zielknoten node2 in der Menge der neighbors enthalten ist. Falls ja, gib True zurück.

Interaktive Übung

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

# 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
Code bearbeiten und ausführen