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

Odpowiedz Nowy wątek
2011-10-21 16:12
4glory
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?

Pozostało 580 znaków

2011-10-21 23:06
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.

Pozostało 580 znaków

2011-10-21 23:36
0

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


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
Ale i tak otrzymasz drzewo ;p - lukas_gab 2011-10-21 23:44

Pozostało 580 znaków

2011-10-21 23:48
4glory
0

k dzieki wielkie

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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