DFS - Przeszukiwanie grafu

Cześć :)

Pisze program na grafie. Chciałbym napisać program który: Użytkownik wprowadza dane czyli ilość wierzchołków i połączenia. Następnie po każdym wierzchołku po kolei sprawdza czy przejdzie graf: tzn idzie w głąb dla każdego połączenia wychodzącego od wierzchołka X i jeżeli skończą się wierzchołki nie cofam się się do wierzchołka, z którego ostatnio przyszedłem czy jakiegokolwiek innego i nie wchodzę z tego miejsca do następnego nieodwiedzonego (jeśli taki jest) tylko po prostu zapisuje informację o niepowodzeniu.

Myślę, że najlepiej do tego użyć DFS-a, ale nie wiem jak w sumie się za to zabrać. Przeszukać wierzchołek dla wszystkich jego połączeń i później przeszukiwać dla każdego z tych połączeń połączenia kolejnego wierzchołka etc? Nie mam w sumie pomysłu.

https://computersciencesource.files.wordpress.com/2010/05/dfs_1.png

Z punktu D tak: DBEAC
z punktu B nie przejdziesz ponieważ gdy pojdziesz w strone D nie mozesz sie wrocic wiec AEC nie przejdziesz i odwrotnie to samo.

Zależy mi na takim algorytmie

1. Rozumiem, że chcesz sprawdzić, czy istnieje ścieżka w grafie przechodząca przez wszystkie jego wierzchołki?
2. Czy możesz odwiedzać wierzchołki kilkukrotnie?
3. Czy możesz przechodzić krawędziami wielokrotnie?
4. Czy są jakieś dodatkowe ograniczenia?

1. Właśnie tak, jest ścieżka, ale nie mogę powtórzyć tej samej drogi więc nie zawsze będzie.
2. Tak
3. Nie
4. Policzyć ilość przeskoków pomiędzy wierzchołkami albo zaliczonych ścieżek bo to samo wyjdzie.

Ok, rozumiem, że dla danego grafu G(V, E), dla każdego wierzchołka v ze zbioru V chcesz powiedzieć, czy istnieje ścieżka zaczynająca się w wierzchołku v, przechodząca przez wszystkie wierzchołki ze zbioru V co najmniej raz (1), przechodząca przez każdą krawędź ze zbioru E co najwyżej raz (2).

Co więcej, chcesz podać długość takiej ścieżki. Takich ścieżek może być wiele, o różnych długościach. Czy chcesz zatem wyznaczyć wszystkie takie ścieżki? Jeżeli tak, możesz zastosować przeszukiwanie w głąb zaznaczając zamiast odwiedzonych wierzchołków krawędzie. Pamiętaj o tym, aby przy nawrotach oznaczać krawędzie z powrotem jako dostępne.

Łatwo zauważyć, że dla grafu pełnego liczba możliwych ścieżek spełniających (1) i (2) jest >= n!.

Przeszukiwanie z nawrotami nazywane jest backtrackingiem (ang.). Niektóre języki natywnie wspierają backtracking pozwalając na łatwą implementację takich algorytmów. Przykładem takiego języka jest Prolog.

@szmq to co opisałeś z tym DFSem jest bez sensu. A problem który chcesz rozwiązać to:
https://en.wikipedia.org/wiki/Eulerian_path
a konkrentniej:
http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf

Shalom napisał(a):

A problem który chcesz rozwiązać to:
https://en.wikipedia.org/wiki/Eulerian_path

Nie. On chce odwiedzić każdy wierzchołek co najmniej raz, odwiedzając każdą krawędź co najwyżej raz. Nie musi nawet odwiedzać wszystkich krawędzi. Co więcej, cykl Eulera nie musi odwiedzać wszystkich wierzchołków grafu.

@merlinnot

Co więcej, cykl Eulera nie musi odwiedzać wszystkich wierzchołków grafu.

Pokaż mi jak odwiedzić wszystkie krawędzie w spójnym grafie, nie odwiedzając przy tym wszystkich wierzchołków. I dare you.
Napisał że chce odwiedzić wszystkie wierzchołki, przechodząc przez niektóre wielokrotnie, ale nie powtarzając krawędzi. Jak dla mnie spokojnie można do tego wykorzystać szukanie ścieżki eulera, ewentualnie można go przerywać kiedy już odwiedziliśmy wszystkie wierzchołki.

Nigdzie nie powiedziałem, że graf jest spójny. Wystarczy, że jest tam wierzchołek izolowany, wtedy może istnieć cykl Eulera nie odwiedzający wszystkich wierzchołków.

Właściwie, to dlaczego cykl Eulera, a nie łańcuch?

Łatwo znaleźć przykład, w którym nie ma cyklu Eulera, a istnieje w nim ścieżka, o którą tu pytamy. Czy możesz udowodnić, że ten algorytm jest poprawny?

@merlinnot

1. To ty zacząłeś o cyklu, ja cały czas mówiłem o ścieżce/łańcuchu
2. Póki autor nie napisze konkretnie jakie są wymagania (np. że ścieżka ma być minimalna?) to wróżymy z fusów. A znając życie to problem jest dużo łatwiejszy.

1. Artykuł, do którego link podałeś (http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf), traktuje o cyklu Eulera (Eulerian Circuit), nie o łańcuchu.

2. Pewnie masz rację, ale starałem się dosyć dokładnie dopytać o wymagania. Wyrażamy na razie większe zainteresowanie tematem, niż sam autor ;)

Nie chce odwiedzić wszystkich wierzchołków co najmniej raz. Chce sprawdzić ścieżkę z każdego wierzchołka. Jeżeli napotka ścieżkę, która już była użyta dla danego wierzchołka to przerywa DFS-a wcześniej i zapisuje do jakiejś zmiennej ilość przeskoków. Może i racja z tą ścieżką Eulera. Obadam dzisiaj

Ale ścieżkę z każdego wierzchołka dokąd? Gdzie ona ma prowadzić? Kiedy uznajemy że ścieżka jest dobra? Może ty chcesz policzyć ile w grafie jest wszystkich możliwych ścieżek bez cykli?

dopiero uczę się algorytmiki. Mógłbym opierać się na tej implementacji? http://www.algorytm.edu.pl/grafy/przeszukiwanie-w-glab.html

@szmq możesz użyć tej implementacji i podbijać sobie licznik

if(!w[w[k].polaczenia[i]].odwiedzony) 
      w_glab(w[k].polaczenia[i]); 
      //tutaj

i zliczysz wtedy te swoje ściezki.

No nie do końca :) Niezależnie od tego jaki wierzchołek to jest tyle samo przeskoków.
Załóżmy że mamy:
https://drive.google.com/file/d/0B_AejuktdjhaOHpVMHEyWGFQUHM/view?usp=sharing

z 1 przejdziemy do 2 albo 3. Zalozmy, ze idziemy do 2, nastepnie 3,4,5,6 i 1 to dlatego przechodzimy przez 3 bo polaczenie 3-1 jeszcze nie bylo uzyte w przeciwienstwie 2-3. Załóżmy teraz, że startujemy z wierzchołka 4 i możemy wybrać 3 albo 5. Zakładamy, że wybieramy 3, następnie pójdziemy do 6, 5 i przerywa ponieważ droga kończy się na połączeniu 4-5. (4-3 była już użyta)