Grafy nieskierowane - szukanie podgrafów w zbiorze

Witam. Piszę w tym dziale, ponieważ nie mogę sobie poradzić z rozwiązaniem jednego problemu. Napisałem skrypt, który w bazie danych ma współrzędne punktów oraz krawędzie nieskierowane łączące w obie strony te punkty w graf. Cały graf jest przeszukiwany przez DFS z pomocą stosu. Problem polega na tym, że nie umiem wpaść na pomysł jak można znaleźć wszystkie podgrafy zamknięte w tym grafie. Próbowałem już na zasadzie, że jeśli trafi na punkt odwiedzony to wraca po stosie i zapisuje ścieżkę jako zamkniętą do oddzielnej bazy, ale jednak to nie wystarcza. Czasem się zdarza, że po drodze pomija jakieś większe albo mniejsze. Chciałbym też spytać czy przeszukiwanie DFS nadaje się do takiego zadania i w jaki właśnie sposób powinno szukać tych podgrafów zamkniętych, jakie powinny być warunki albo czy ktoś się z czymś podobnym już spotkał. Jeśli za mało podałem informacji to postaram się szczegółowiej opisać. Z góry dziękuję.

Hm... jaki masz cel?
a) szukanie w jednym grafie 'czegoś tam' co nazywasz podgrafem;
b) szukanie w zbiorze danych wszystkich istniejących grafów (czyli wydzielenie ze zbioru danych grafów jakie się w nim znajdują).

Narysowałem prosty przykład i pod nim to co powinno być wynikiem przeszukiwania grafu. Co prawda przykłady, które ja sprawdzam są bardziej skomplikowane niż ten tutaj, bo posiadają więcej punktów i krawędzi, ale mam nadzieje, że widać o czym wcześniej pisałem.

Czyli chodzi o rozdzielenie grafów nieskierowanych :)
1. utwórz tablicę w której:
Przejdź liniowo przez wszystkie wierzchołki i zapisz je do tablicy:
Następnie weź pierwszy NIEODWIEDZONY wierzchołek z listy i np. rekurencyjnie przejdź się po grafie od wybranego wierzchołka zaznaczając przy tym w tablicy, że wierzchołek został odwiedzony (np. liczbą 1).

Ponawiasz powyższy algorytm dopóki dopóty nie zostanie znaleziony NIEODWIEDZONY wierzchołek na liście. Przy kolejnych rozpoczęciach przeszukiwań rekurencyjnych zwiększasz wartość, którą oznaczasz 'czy wierzchołek został odwiedzony'.

Na koniec sortujesz tablicę 'wizyty' po polu struktury 'iOdwiedzono' i masz rozdzielone wierzchołki wszystkich grafów występujących w zbiorze danych.

/edit:
Ale chyba nie o to Ci chodzi... :P

Ok, no to druga koncepcja (nawiązująca do Twojego problemu) :)

1. Znajdź wszystkie wierzchołki które posiadają tylko 1 krawędź.
2. Wywal te wierzchołki i krawędzie.
3. Jeżeli udało Ci się wywalić choć jeden wierzchołek -> wróć do pkt 1
4. Otrzymasz wówczas taki graf, w którym nie ma wierzchołków 'zbędnych', dzięki czemu możesz sprawdzić wszystkie możliwe cykle np. kombinatorycznie.