Zacznij terazZacznij za darmo

Najkrótsza ścieżka I

Wiedzę o znajdowaniu sąsiadów możesz wykorzystać do wyszukiwania ścieżek w sieci. Jednym z algorytmów znajdowania ścieżki między dwoma węzłami jest algorytm przeszukiwania wszerz (BFS, ang. breadth-first search). Algorytm BFS rozpoczyna działanie od wskazanego węzła i iteracyjnie przeszukuje jego sąsiadów oraz sąsiadów sąsiadów, aż do odnalezienia węzła docelowego.

Algorytmy wyznaczania ścieżek są ważne, ponieważ umożliwiają ocenę istotności węzłów w inny sposób – więcej na ten temat znajdziesz w kolejnym ćwiczeniu.

W tym zestawie 3 ćwiczeń będziesz stopniowo budować finalny algorytm BFS. Problem został podzielony na 3 części, których wykonanie po kolei doprowadzi cię do pierwszej implementacji algorytmu BFS.

To ćwiczenie jest częścią kursu

Wprowadzenie do analizy sieci w Pythonie

Zobacz kurs

Instrukcje do ćwiczenia

  • Utwórz funkcję o nazwie path_exists() przyjmującą 3 parametry – G, node1 i node2 – która zwraca informację o tym, czy między dwoma węzłami istnieje ścieżka.
  • Zainicjalizuj kolejkę węzłów do odwiedzenia, wstawiając do niej pierwszy węzeł, node1. Zmienna queue powinna być listą.
  • Iteruj po węzłach w queue.
  • Pobierz sąsiadów węzła, korzystając z metody .neighbors() grafu G.
  • Sprawdź, czy węzeł docelowy node2 znajduje się w zbiorze neighbors. Jeśli tak, zwróć True.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

# 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
Edytuj i uruchom kod