1. 학습
    2. /
  2. 강의
    3. /
  3. Wprowadzenie do analizy sieci w Pythonie
Connected

연습 문제

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.

지침

100 XP
  • 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.