Wydajny sposób na ćwiczenie algorytmów teorii grafów

Question

Właśnie przeczytałem o algorytmie breadth-first search w książce Wprowadzenie do algorytmów i ręcznie symulowałem algorytm na papierze. To, co chciałbym teraz zrobić, to zaimplementować go w kodzie dla dodatkowej praktyki.

Zastanawiam się nad implementacją wszystkich struktur danych od zera (macierze adjacency list, "kolor", "odległość" i "nadrzędne"), ale potem przypomniałem sobie, że istnieją obecnie biblioteki wykresów, takie jak wykres Boost biblioteka i niektóre inne graph APIs w Pythonie. Próbowałem również szukać niektórych problemów związanych z BFS na UVA i Sphere Judge Online, ale nie mogę powiedzieć, które problemy wymagałyby rozwiązania BFS.

Moje pytanie brzmi, co byłoby najbardziej bezbolesny sposób na ćwiczenie tych algorytmów wykresu (nie ogranicza się tylko do BFS, ale również się przydać, kiedy chcą wprowadzić DFS, Dijkstra, Floyd-Warshall, etc). Witryny z problemami praktycznymi są mile widziane.

Answer 1

Osobiście uważam, że najlepszym sposobem na ich zrozumienie byłoby samodzielne wprowadzenie reprezentacji wykresów od zera.

Po pierwsze, pokażą ci rzeczywiste zastrzeżenia dotyczące implementacji, z których dowiesz się, dlaczego dany algorytm może być interesujący/dobry/sprawny/cokolwiek. Z drugiej strony uważam, że zrozumienie wykresów i ich rzeczywistego wykorzystania, w tym jego implikacji (rekurencja, wydajność/skalowalność, aplikacje, alternatywy, ...), jest łatwiejsze dzięki podejściu oddolnemu.

Ale może to tylko ja. Powyższe ma bardzo osobisty gust.

Answer 2

Znalazłem twoje pytanie interesujące, trochę googotowałem i znalazłem JGraphEd.

Nie obejmuje wszystkich algorytmów grafów, ale wygląda na dobre narzędzie do eksperymentów.

Answer 3

Zgadzam się z Balphą. Najlepszym sposobem na poznanie i zrozumienie algorytmów jest wykonanie. Wystarczy wybrać algorytm i go wdrożyć. Kiedy dotrzesz do punktu, w którym utkniesz lub nie masz pewności, spójrz na kilka istniejących przykładów. Będziesz wtedy mógł porównać swoje własne myślenie ze zrozumieniem innych ze stanowiska zrozumienia, zamiast po prostu zaakceptować to, co jest oferowane.

Gdy nauczysz się, czego chcesz, najlepszym sposobem na utrwalenie swojego zrozumienia jest nauczenie go lub opisanie komuś innemu. Możliwe, że niektórzy ludzie będą chcieli cię wysłuchać, a przynajmniej możesz napisać wpis na blogu dla osób, które nie znają algorytmu, który właśnie studiowałeś.

Ale jeśli szukasz „bezbolesny”, to może należy trzymać się z daleka od algorytmów całkowicie ;-)

Answer 4

This site could help you

Tutaj masz opis każdego problemu na acm problemset. Możesz zobaczyć kategorię każdego problemu i wskazówkę, aby go rozwiązać. Wystarczy przejrzeć problemy związane z wykresem. Dobrą radą jest stosowanie tych wskazówek tylko wtedy, gdy sam próbowałeś rozwiązać problem i nie udało mu się.

Answer 5

Wizualizacja niektórych najkrótszych algorytmów ścieżkę na danych rzeczywistych, gdzie zbadać obszar jest wyświetlany na żółto:

• (bidirectional) Dijkstra
• A*