Znaleźć cykle w pewnym grafie

0

Mam graf skierowany, którego każdy wierzchołek posiada maksymalnie jednego rodzica i dowolną ilość dzieci. Podobnie jak w drzewie klas w jakimś języku programowania, w którym klasa może mieć dokładnie jedną klasę bazową. Jednak każdy rodzic (klasa) nie posiada informacji o swoich dzieciach (klasach pochodnych). Tylko dzieci znają swojego rodzica (klasę bazową) i w tym kierunku możliwe jest przeglądanie grafu. Wierzchołków bez rodzica może być wiele (brak wspólnej klasy bazowej, z której się wywodzą wszystkie pozostałe, jednak mogę to zmienić i wprowadzić taką regułę jeśli się przyda). Listę wszystkich wierzchołków trzymam w tablicy (kolejność losowa).

Muszę sprawdzić, czy w grafie NIE MA cykli.
Chodzi o to aby metoda była raczej prosta niż wydajna, ale wydajność też się liczy.
Może da się uniknąć tworzenia pomocniczego drzewa w którym wierzchołki pamiętają dzieci (klasy pochodne) ?
Jakieś pomysły na algorytm ?

//EDIT
Eureka :) oświeciło mnie.

Mój pomysł bazuje na koncepcji, że jeśli taki graf nie posiada cykli jest drzewem. Dla uproszczenia zakładam, że wierzchołki bez rodzica tak na prawdę posiadają jednego wspólnego rodzica (jedeń korzeń). Jeśli przeglądać by takie drzewo w szerz, wierzchołki będą przeglądane w pewnej kolejności. I właśnie tą kolejność chce odzwierciedlić w tablicy w której trzymam wszystkie wierzchołki. Skorzystam z takiej własności tej kolejności, że rodzic jest zawsze przed dzieckiem.

Tablica dzieli się na 2 spójne części: posortowaną z przodu i nieposortowaną za nią (kwestia pamiętania indeksu podziału)
Bąbelkiem ułożę wierzchołki bez rodzica (klasy bez bazy) na początku listy. Oznaczę je jako posortowane.
Teraz rekurencja: dla każdego wierzchołka poprzednio ułożonego bąbelkiem sprawdzę czy nie jest on rodzicem któregoś z wierzchołków części już posortowanej. Jeśli znajdzie się takie dziecko - mamy cykl.
Dalej jeszcze raz dla każdego wierzchołka poprzednio ułożonego bąbelkiem dołożę do części posortowanej dzieci tego wierzchołka.
Zrobię to wywołują kolejnego bąbelka na części nieposortowanej. Dzieci które wyłonił bąbelek oznaczę jako posortowane.

Na pewno moje rozumowanie jest poprawne?

0

wystarczy odpalić dfs'a. jeżeli napotkasz szary wierchołek przy sprawdzaniu wierchołków wychodzących to znaczy, że masz cykl.

jeżeli do jakiegoś wierzchołka nie dotrłeś dfs'em to musisz go przejechać osobno, tzn:

for each węzeł do
if węzeł.kolor = biały then
dfs(węzeł)

jeżeli masz pod ręką jakiegokolwiek studenta po pierwszym roku informatyki to zrobi ci to z zawiązanymi oczami ;)

złożoność liniowa o(v + e), długość kodu kilkadziesiąt linijek

jeżeli masz cykl to obojętne w którą stronę są strzałki (tzn. czy rodzic wkazuje na dziecko czy odwrotnie), bo itak cykle pozostaną bez zmian.

0

Faktycznie. Że ja na to nie wpadlem [wstyd] . Hańba. W dodatku dfs będzie super prosty z racji braku "polimorfizmu".

1 użytkowników online, w tym zalogowanych: 0, gości: 1