Anzahl der Zyklen in einem ungerichteten Graphen

Question

Das Problem ist, wie der Titel andeutet, das Diagramm ist in Adjazenzliste aufgeführt. Mein Ansatz ist, DFS in irgendeinem Eckpunkt aufzurufen, und immer wenn ich einen besuchten Eckpunkt während meines rekursiven DFS-Schritts betrachte, inkrementiere ich den Zähler einer globalen Variablen beginnend mit 0 und rufe DFS nicht für diesen besuchten Eckpunkt auf (wie allgemein üblich). Wird das funktionieren, denke ich richtig? Ich habe auch keinen relevanten Artikel im Internet gefunden, um über #Anzahl von Zyklen in ungerichteten Graphen zu erfahren.

Ausarbeitung: Ich meine, eine einfache DFS-Methode zu verwenden. Während wir im rekursiven Schritt beim Auffinden eines besuchten Eckpunkts nichts tun, erhöhe ich den globalen Variablenwert counter für diese Situation. Ich tue dies, denn wenn ich auf eine besuchte Ecke stoße, bedeutet das, dass ich einen Zyklus vollende. Ich behaupte das: Jeder Zyklus im Graphen wird nur einmal (atleast und fast einmal) in irgendeinem DFS-Lauf angetroffen. BIN ICH IN DIESEM ANSPRUCH KORREKT?

Edit: Keine Kanten zurück

Answer 1

Es tut mir leid Antwort auf meine Antwort zu schreiben selbst, sondern nur für diejenigen, die ähnliche Zweifel in Zukunft haben: Ich fand, dass ich viele Zyklen redundant, zum Beispiel wird zu zählen: -

Starten von DFS von A-> B-> C-> DI bekommen den Zyklus CBD zweimal gezählt. Ich lernte auch das Problem, alle Zyklen in einem ungerichteten Graphen zu finden, ist np-schwer. Pech: '(