Mamy dany graf skierowany i chcemy wyznaczyć ile minimalnie trzeba wskazać wierzchołków, z których można dojść do wszystkich innych, np:
Odpowiedzi są zaznaczone niebieskim kółkiem, w pierwszym przypadku można zaznaczyć którykolwiek i będzie dobrze.
Jakieś pomysły ?</image>
Sprawdzasz spójność grafu. Gdy z pierwszym przeszukaniem w głąb (lub w szerz) nie przejdziesz wszystkiego sprawdzasz dalej, i zwiększasz liczbę wierzchołków (i ew. dodajesz wierzchołek do jakieś listy). Tak ja to widze.
No to źle widzisz, bo np. najprostszy kontrprzykład to
4->1->2->3
BFS od jedynki znajdzie 1,2,3 i potem następny bfs od 4 znajdzie 4 i odpowiedź to będzie 2 ? Czy coś innego miałeś na myśli ?
To byłoby dobre dla grafu nieskierowanego...
Hm, ja bym najpierw wyszukał silnie spójne składowe. Następnie tworzymy graf w ten sposób, że każdą silnie spójną składową reprezentujemy przez tylko jeden wierzchołek (w sensie rozwiązania tego zadania, wierzchołki silnie spójnej składowej są nierozróżnialne).
W ten spobób otrzymaliśmy DAG (dowód niewprost: gdyby był jakiś cykl, to musiałby się znaleźć w jakiejś nietrywialnej silnie spójnej składowej).
Teraz problem na pewno jest prostszy... Posortowałbym te wierzchołki topologicznie i dodawał kolejno do listy wynikowej, usuwając z grafu wszystkie wierzchołki, do których da się dostać z aktualnego. I tak aż do usunięcia wszystkich.
Ja probował bym:
-podzielic graf na składowe;
-i dla kazdej składowej policzyc ilosc wierzcholkow o stopniu wejsciowym = 0;
dla przykładu 4 ->1->2->3
mamy jedna składowa .. i tylko jeden wierzchołek ma stopien wejsciowy = 0 ( wierchołek o nr 4)
zauwazmy co dzieje sie gdy jest cykl
1->2->3->1 ...wtedy zadnen wiercholek nie ma wejsciowego zero .. wiec kazdy z wiercholkow tej składowej moze byc Naszym punktem ;)
Cały algorytm:
-podzielenie grafu na skladowe(BFS || DFS) // składowych szukamy na grafie nieskierowanym
-dla kazdej składowej liczymy ilosc wierzcholkow o stopniu = 0 jezeli takie są to są to własnie Nasze punkty jezeli takich nie ma to swiadczy o tym ze składowa jest cyklem wiec wystarczy 1 dowolny wierchołek z cyklu
Może sie myle ;)
dziad, ty się na pewno mylisz, bo mam już mam kontrprzykład na twoje rozwiązanie ;p
natomiast rozwiązanie Pawła200x.5 to jedyne, które mi się zaczyna podobać ;D
pokaz ten kontrprzykład .. natomiast rozwiazanie Pawla<brawo>
Coś w ten deseń, twój algorytm da jeden zamiast 3 !!
Temat można uznać za zakończony, bo lepszego, poprawnego i krótszego rozwiązania niż Pawła to chyba nie ma...
A tak w ogóle to może ktoś ma jakiś fajny, prosty i najlepiej darmowy (albo cracka od razu :)) programik do rysowania takich grafów jak wyżej ?? bo paint to się średnio do tego nadaje...
Dia?
Algorytm dziada jest ok. I da 3 a nie 1 jak piszesz.
generator napisał(a)
Algorytm dziada jest ok. I da 3 a nie 1 jak piszesz.
Da 1:
Jedna składowa spójności (zgodnie z komentarzem, że składowe sprawdzamy na grafie nieskierowanym).
Nie ma wierzchołka z zerem wejść -> są cykle -> można wybrać dowolny wierzchołek.