jak sprawdzic czy dotarcie z 1 wezla do drugiego jest mozliwe?

0

Hej,
Znacie jakiś algorytm dzięki któremu mógłbym sprawdzic czy istnieje droga laczaca 2 rozne wezly w grafie w ktorym mogą wystapic petle, cykle?

0

Zrób kolejkę krawędzi. Zacznij wyznaczać MST zaczynając od krawędzi z pierwszym węzłem. Jeżeli skończysz robić MST a w kolejce będzie nadal krawędź z węzłem drugim znaczy to, że graf nie był spójny.

0

Najprościej? Puścić szukanie BFSem od wierzchołka startowego. Przerywasz jak graf sie skończy lub jak trafisz na cel.

0

k dzieki wielkie

1 użytkowników online, w tym zalogowanych: 0, gości: 1