Začněte nyníZačněte zdarma

Nejkratší cesta I

Znalosti o hledání sousedů můžeš využít i při hledání cest v síti. Jedním z algoritmů pro hledání cest mezi dvěma uzly je algoritmus „prohledávání do šířky" (BFS, z angl. breadth-first search). BFS algoritmus začíná v konkrétním uzlu a postupně prochází jeho sousedy, pak sousedy sousedů, a tak dále – dokud nenajde cílový uzel.

Algoritmy pro hledání cest jsou důležité, protože nabízejí další způsob, jak hodnotit důležitost uzlů – to uvidíš v pozdějším cvičení.

V této sérii 3 cvičení budeš postupně budovat finální BFS algoritmus. Úloha je rozdělena do 3 částí, jejichž postupným splněním získáš první funkční implementaci BFS algoritmu.

Toto cvičení je součástí kurzu

Úvod do analýzy sítí v Pythonu

Zobrazit kurz

Pokyny k cvičení

  • Vytvoř funkci path_exists() se 3 parametry – G, node1 a node2 – která vrátí, zda mezi dvěma uzly existuje cesta, nebo ne.
  • Inicializuj frontu uzlů k navštívení prvním uzlem node1. Proměnná queue by měla být seznam.
  • Iteruj přes uzly ve frontě queue.
  • Získej sousedy uzlu pomocí metody .neighbors() grafu G.
  • Zkontroluj, zda se cílový uzel node2 nachází v množině neighbors. Pokud ano, vrať True.

Interaktivní cvičení na vyzkoušení si v praxi

Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.

# 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
Upravit a spustit kód