Ich bin daran interessiert, die Gesamtzahl der Zyklen und Zyklen in einem verbundenen ungerichteten Graphen zu finden. Kann ich DFS verwenden? Oder kann DFS nur einen einzigen Zyklus finden? Jeder Code wird definitiv helfen.Ermitteln der Gesamtzahl der Zyklen und der Zykluslänge
einen Blick auf die folgenden Referenz Nehmen:
Genau was ich gepostet habe. Ich habe nicht rechtzeitig eine neue Postbenachrichtigung erhalten, tut mir leid. – colithium
wie in der zitierten pdf erwähnt: Die Anzahl der Zyklen kann exponentiell in der Anzahl der Knoten sein. Mit einem einfachen DFS wird jeder Zyklus mit einem Zeitschritt gefunden, was zu einer exponentiellen Laufzeit führt. Wenn dies ein Problem wird (in einem dichten Graph sogar für weniger als 100 Knoten), muss man einen ausgefeilteren Algorithmus verwenden. Ich hatte im Hinterkopf, dass es eins gibt. – eci
Welche Sprache arbeiten Sie mit? Und ich denke, einer von denen sollte BFS sein =) – colithium
Beachten Sie auch, dass die Anzahl der Zyklen in einem Diagramm von mittlerer Größe kann RIESIG sein. – colithium
Ich möchte Java verwenden –