Cześć
Mam za zadanie zaimplementować graf skierowany, wraz z funkcjonalnoscią znalezienia najkrotszej sciezki od danego miejsca do liscia.
Na wejsciu dostaję ilość wierzcholków w grafie, liczbę połączen między nimi i miejsce z którego mam najkrótsza drogą dotrzeć do miejsca, z którego nie da sie isc dalej.
Problem jest graf zawiera cykl (pętli zawierac nie może, więc delikatne uproszczenie) . Jeśli jest cykl, to muszę go wykryć, zapamietać że był, ale jednoczesnie próbować iść do liscia.
Jaki jest najprostszy sposób, aby w przechodzeniu BFS wykryc, że scieżka się zapętla?
0
0
Oznaczaj te wierzchołki w których już byłeś, jak jeszcze raz w nim będziesz gratulacje znalazłeś cykl. To oznaczanie zwie się również kolorowaniem czasem potocznie.
0
Tylko jeszcze małe utrudnienie - każdy wierzchołek mogę odwiedzić w dwóch stanach. Raz kolorując na czarno a raz kolorując na biało, więc cykl będzie dopiero wtedy, gdy przejdę po tym samym wierzchołku w tym samym stanie