Kom igångKom igång gratis

Kortaste vägen I

Du kan använda det du vet om att hitta grannar för att söka efter vägar i ett nätverk. En algoritm för vägfinnning mellan två noder är "bredden-först-sökning" (BFS). I en BFS-algoritm börjar du från en bestämd nod och söker iterativt igenom dess grannar och grannarnas grannar tills du hittar destinationsnoden.

Vägfinnningsalgoritmer är viktiga eftersom de ger ett annat sätt att bedöma noders betydelse – du kommer att se det i en senare övning.

I den här serien med 3 övningar bygger du steg för steg upp den fullständiga BFS-algoritmen. Problemet är uppdelat i 3 delar som, om du löser dem i ordning, leder dig till en första implementation av BFS-algoritmen.

Den här övningen är en del av kursen

Introduktion till nätverksanalys i Python

Visa kurs

Övningsinstruktioner

  • Skapa en funktion som heter path_exists() med 3 parametrar – G, node1 och node2 – som returnerar om det finns en väg mellan de två noderna eller inte.
  • Initiera kön av noder att besöka med den första noden, node1. queue ska vara en lista.
  • Iterera över noderna i queue.
  • Hämta grannarna till noden med metoden .neighbors() på grafen G.
  • Kontrollera om destinationsnoden node2 finns i mängden neighbors. Om den gör det, returnera True.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

# 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
Redigera och kör kod