wykrywanie cykli wykresów - proste wyjaśnienie

czy ktoś mógłby pomóc mi zrozumieć, jak znaleźć cykle na wykresach w kategoriach laika?

Czytałem inne pytania, takie jak To, a także niektóre strony wikipedii, ale wydają się one dość szybko schodzić na matematyczny żargon.

Mam model wykresu w Javie, modelowanie węzłów oraz krawędzie „wejściowe” i „wyjściowe” - i model zna węzły połączone tylko w jednym kierunku, co pozwala mi znaleźć węzły liścia jako punkt początkowy, mój plan był aby przejść z powrotem do wykresu z każdego z tych węzłów liści, dla każdego „przejścia”, zachowując listę wszystkich innych węzłów, które znalazłem na mojej trasie. Jeśli w dowolnym momencie zobaczę coś na liście, będę wiedział, że znalazłem cykl na wykresie. To jednak wydaje się trochę uproszczone.

Jestem pewien, że jest to rozwiązany problem, byłoby miło, gdyby można go było wyjaśnić w prosty sposób.

-as

Najprostszym sposobem, w jaki mogę wyjaśnić świecenie cykli graficznych, jest coś takiego:

• Po pierwsze, zakładam, że znasz podstawy tego, czym jest wykres oraz jakie są węzły i krawędzie. W tym przykładzie założono, że masz wykres, na którym wszystkie krawędzie są tylko jednokierunkowe.
• Utwórz wykres i wybierz jeden węzeł jako punkt początkowy.
• Utwórz jakiś obiekt kontenerowy (najlepiej działałaby lista lub skrót). Nazwij to „Odwiedzono”.
• Utwórz drugi obiekt kontenera (tutaj byłaby idealna kolejka) i nazwij go „Otwórz”.
• Dodaj węzeł początkowy do listy Otwórz.
• Powtarzaj, gdy lista Otwórz nie jest pusta:
  • Usuń pierwszy element z Otwórz i nazwij go Bieżącym
  • Jeśli w Odwiedzone istnieje prąd, masz cykl.
  • Jeśli nie, dodaj Bieżący do Odwiedzonych, a następnie dodaj wszystkie węzły, do których Bieżący może dotrzeć ze swoich krawędzi wychodzących do Otwartych.
• Jeśli Open kończy się pustym i nie wykryto żadnych cykli, oznacza to, że nie masz żadnych cykli. (Przynajmniej nie w dostępnym zestawie pochodzącym od punktu początkowego, który niekoniecznie jest całością twojego wykresu, jeśli masz wyspy na swoim wykresie.)

Zasadniczo najpierw przeprowadzasz szerokie wyszukiwanie na wykresie i śledzisz, które węzły odwiedziłeś za pomocą mapy skrótów.

W dowolnym momencie, jeśli natrafisz na węzeł, który był już odwiedzany (obecny w haszapie), wtedy wiesz, że na wykresie jest cykl.