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.

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.

.css-6su6fj{-webkit-flex-shrink:0;-ms-flex-negative:0;flex-shrink:0;}cvičení

Pokyny

cvičení