Aan de slagGa gratis aan de slag

Shortest Path II

Nu je de code hebt om te controleren of de doelknoop in de neighbors zit, ga je dezelfde functie uitbreiden met code voor de situatie waarin de doelknoop niet in de neighbors zit.

Alle code die je moet schrijven staat in de else-tak; dus als node2 niet in neighbors zit.

Deze oefening maakt deel uit van de cursus

Introductie tot netwerkanalyse in Python

Cursus bekijken

Oefeninstructies

  • Gebruik de .add()-methode om de huidige knoop node toe te voegen aan de set visited_nodes, zodat je bijhoudt welke knopen al bezocht zijn.
  • Voeg de neighbors van de huidige knoop node die nog niet zijn bezocht toe aan queue. Hiervoor gebruik je de .extend()-methode van queue samen met een list comprehension. De .extend()-methode voegt alle items in een opgegeven lijst toe.
    • De outputexpressie en iteratorvariabele van de list comprehension zijn allebei n. De iterable is de iterator van neighbors, en de voorwaarde is dat n niet in de bezochte knopen zit.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

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