Aan de slagGa gratis aan de slag

Kortste pad I

Je kunt wat je weet over het vinden van buren gebruiken om paden in een netwerk te zoeken. Eén algoritme om paden tussen twee knooppunten te vinden is het "breadth-first search" (BFS)-algoritme. In een BFS-algoritme begin je bij een bepaald knooppunt en doorzoek je iteratief de buren en de buren van die buren totdat je het doelknooppunt vindt.

Padzoekalgoritmen zijn belangrijk omdat ze een extra manier bieden om het belang van knooppunten te beoordelen; je ziet dit in een latere oefening.

In deze reeks van 3 oefeningen bouw je stap voor stap naar het uiteindelijke BFS-algoritme. Het probleem is opgedeeld in 3 delen die je, als je ze achter elkaar afrondt, naar een eerste implementatie van het BFS-algoritme leiden.

Deze oefening maakt deel uit van de cursus

Introductie tot netwerkanalyse in Python

Cursus bekijken

Oefeninstructies

  • Maak een functie path_exists() met 3 parameters — G, node1 en node2 — die teruggeeft of er een pad tussen beide knooppunten bestaat.
  • Initialiseer de wachtrij met knooppunten om te bezoeken met het eerste knooppunt, node1. queue moet een lijst zijn.
  • Itereer over de knooppunten in queue.
  • Haal de buren van het knooppunt op met de .neighbors()-methode van graaf G.
  • Controleer of het doelknooppunt node2 in de set neighbors zit. Als dat zo is, retourneer True.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

# 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 bewerken en uitvoeren