Witam.
W wielu książkach szukałem informacji o algorytmie DFS, w większości z nich algorytm ten działał na zasadzie rekurencji, lecz w niektórych spotkałem się z wersją iteracyjna.
Teraz takie moje pytanie, która wersja jest bardziej wydajna, dodam ze implementacja wykorzystująca rekurencje jest o wiele wygodniejsza.
P.S. Czy algorytm DFS jest może zaimplementowany w standardowych algorytmach DFS?
zazwyczaj podejscia iteracyjne sa bardziej wydajne niz rekurencyjne, i zazwyczaj rekurencyjne sa bardziej wygodne w napisaniu i zrozumieniu
Nie jest taki trudny znowu. Dla drzewa:
'przejdź' oznacza samo przejście, 'weź' oznacza przejście do danego wierzchołka i wykonanie na nim operacji, którą DFS ma robić (np. przy wyszukiwaniu będzie to porównanie)
Mnie interesuje przechodzenie grafu, nie drzewa.
Iteracja jest zwykle trochę szybsza od rekursji, ale z drugiej strony w iteracji i tak musisz mieć stos.
Większym problemem jest pamięć. Na stosie odkładają się też takie rzeczy jak adres powrotny, wartości rejestrów, itd. Jeżeli graf jest długą listą, to może skończyć się pamięć. Ponadto w większości systemów operacyjnych programy mają limit pamięci na stos, czyli programowi może się skończyć pamięć mimo, że jest jeszcze wolny RAM.
Moja rada: Jeżeli wiemy, że graf nie przypomina listy, wybierz rekursję. Natomiast wpp. musisz użyć iteracji.
//na poczatku visited == false dla kazdego v
visit(v){
v.visited = true;
do_something(v);
for each n in v.neighbours
if (!n.visted) visit(n);
}
Heap S = new Heap; //jezeli stos zastapimy kolejka, to otrzymamy BFS
S.push(v); // v-dowolny elem z G
while (!S.empty){
v = S.pop();
v.visited = true;
do_something(v);
for each n in v.neighbours
if (!n.visted) S.push(n);
}
Myślę, że wielkosc grafu nie przekroczy kolo 100 000 wierzchołków i jest to graf raczej żadki dajmy na to nie wiecej niż 200 000 krawedzi.
Nie rozumiem stwierdzenia, że graf jest lista, mogłby mi ktoś to wytlumaczyć?
Np. taki graf jest "prawie listą":
0-0-0-0-0-0-0-0-0
Jeżeli ma n wierzchołków i zaczniemy od skrajnego, to maksymalnie na stosie będzie n rekordów aktywacji.
Po głębszym zastanowieniu doszedłem do wniosku, że istnieje dużo więcej grafów, dla których maksymalny rząd rekursji będzie duży,np.
cykl
0-0-0-0
| |
0 0
| |
0-0-0-0
Dla 10^5 może już nie starczyć stosu. Ale to wszystko zależy, gdzie będzie uruchamiany dany program. Jeżeli piszesz program na jakiś konkurs, to dowiedz się, czy jest tam oddzielny limit na stos.(np. na SIO nie ma takiego limitu)
Jeżeli nie wiesz, zastosuj iterację. Nie jest to dużo trudniejsze.
Hmm, jeżeli iteracja jest pewniejsza to juz się przemęcze. :)
Dzięki :P
Chyba jednak niestet iteracja się nie sprawdzi, po zaimplementowaniu zdałem sobie sprawę, że potrzebne sa mi "powroty rekurencji", aby znac kolejnosc odwrotna do przechodzenia grafu.
Zostaje rekurencja?
Wystarczy dodać do każdego wierzchołka jeden wskaźnik-skąd przyszliśmy do tego wierzchołka(dla pierwszego NULL).
Później podążając po tych wskaźnikach możemy prześledzić całą trasę(w odwrotnej kolejności) od początkowego wierzchołka do danego.
Heap S = new Heap; //jezeli stos zastapimy kolejka, to otrzymamy BFS
S.push(v); // v-dowolny elem z G
v.from = NULL;
while (!S.empty){
v = S.pop();
v.visited = true;
do_something(v);
for each n in v.neighbours
if (!n.visted) {
n.from = v;
S.push(n);
}
}
Rozwiązałem to trochę inaczej, nie zdejmuje wierzchołka ze stosu do <ort>pÓÓÓÓki</ort> jego wszyscy potomkowie nie zostali przerobieni, co sądzicie o takim rozwiązaniu?
Optivar napisał(a)
Rozwiązałem to trochę inaczej, nie zdejmuje wierzchołka ze stosu do <ort>pÓÓÓÓki</ort> jego wszyscy potomkowie nie zostali przerobieni, co sądzicie o takim rozwiązaniu?
Yyyy, a jest inna możliwość ? "Potomkowie" rozumiem jako wszyscy sąsiedzi oprócz tego, od którego przyszliśmy.
Ja bym nie używał stosu, ze względu na to, że aby sprawdzić czy robimy cykl (bo wtedy musimy się cofnąć) trzeba przeszukać cały stos czy już wcześniej na aktualnym wierzchołku staliśmy.
Wystarczy oznaczać każdy wierzchołek podczas jego przeszukiwania. Tylko nie oznaczać bool'em (odwiedzono/nie odwiedzono) a wskaźnikiem do poprzedniego wierzchołka tak jak __krzysiek85 napisał. Wtedy nie potrzebny jest stos, i w każdym momencie można odtworzyć drogę.
W momencie, kiedy potrzebujesz drogę w odwrotnym kierunku, wystarczy odłożyć ją na tymczasowy stos (ściągając ze stosu masz odwrotną kolejność co przy wkładaniu). Jeśli często byś potrzebował odtworzyć taką odwrotną drogę to możesz zastosować dwa wskaźniki - skąd przyszedł i gdzie poszedł. Wtedy możesz poruszać się bez problemu w dwie strony. Przy 100 000 wierzchołków po 2 wskaźniki na każdy daje niecałe 800 kB, tak więc żadne obciążenie.
Algorytm dla grafu wyglądałby prawie identycznie jak w drzewie:
Ta sama różnica miedzy "weź" a "przejdź" co ostatnio. Wskaźnik NULL może oznaczać wierzchołek nieodwiedzony, umowny wskaźnik 0xFFFFFFFF może oznaczać wierzchołek początkowy, pozostałe wartości - wskaźnik do poprzednika.
Można wprowadzić optymalizacje np. pamiętać następnika, jeśli często potrzebujesz drogę wstecz.
Jeśli wierzchołki posiadają wielu sąsiadów, można pamiętać nie tyle następnika co jego pozycję w zbiorze sąsiadów.
Wtedy podczas powrotu (3.) szybciej znajdziemy następnego nieoznaczonego sąsiada, bo szukać go będziemy tylko za zapamiętaną pozycją (przed są same oznaczone).
na razie wiemy tylko, że w grafie jest 100 000 wierzchołków. Jeśli zależy ci na wydajności musisz lepiej opisać swój problem, a pomożemy :) Szczególnie interesowało by mnie jak wypada liczba sąsiadów i jak często potrzebujesz drogę wstecz.