ÎncepețiÎncepe gratuit

Cel mai scurt drum I

Poți folosi ceea ce știi despre găsirea vecinilor pentru a căuta drumuri într-o rețea. Un algoritm de găsire a drumurilor între două noduri este algoritmul „breadth-first search" (BFS). Într-un algoritm BFS, pornești de la un anumit nod și cauți iterativ prin vecinii săi, apoi prin vecinii vecinilor, până când găsești nodul destinație.

Algoritmii de găsire a drumurilor sunt importanți deoarece oferă o altă modalitate de a evalua importanța nodurilor – vei vedea asta într-un exercițiu ulterior.

În această serie de 3 exerciții, vei construi treptat implementarea finală a algoritmului BFS. Problema a fost împărțită în 3 părți care, dacă le parcurgi în ordine, te vor conduce la o primă implementare a algoritmului BFS.

Acest exercițiu face parte din cursul

Introducere în analiza rețelelor în Python

Vezi cursul

Instrucțiuni pentru exercițiu

  • Creează o funcție numită path_exists() cu 3 parametri – G, node1 și node2 – care returnează dacă există sau nu un drum între cele două noduri.
  • Inițializează coada de noduri de vizitat cu primul nod, node1. queue ar trebui să fie o listă.
  • Iterează peste nodurile din queue.
  • Obține vecinii nodului folosind metoda .neighbors() a grafului G.
  • Verifică dacă nodul destinație node2 se află în mulțimea neighbors. Dacă da, returnează True.

Exercițiu interactiv practic

Încearcă acest exercițiu completând acest cod de exemplu.

# 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
Editează și rulează codul