Hallo
DP,
die "einfache" Frage: Wie finde ich alle Zyklen in einem ungerichteten Graphen?
Ich habe mich bis jetzt ziemlich dämlich dabei angestellt, da ich vermutlich meine Gedanken nicht geordnet kriege
Überlegt habe ich mir, dass ich eine Breitensuche nutze um einen Zyklus (ausgehend von Knoten A) zu finden, doch hierbei scheitert es an der "Markierung" für bereits besuchte Knoten:
Code:
A <- 1. Rekursion
/ \
B C <- 2. Rekursion
| |
D---E <- 3. Rekursion
In der dritten Rekursion käme es ja zu einem Fehler, da der Weg D und E ja schon besucht wurden - jedoch müsste es die Wege E -> D sowie D -> E noch geben (+ den weiteren Weg zu A).
Wie könnte ich einer Breitensuche also vermitteln, dass (z.B.) der Knoten E für D erreichber ist?
Hoffe ich konnte mich verständlich ausdrücken, wenn etwas unklar ist (oder jemand mir sogar weiterhelfen kann
) würde ich weitere Infos liefern.
In Quelltext habe ich mich erst gar nicht heran gewagt, da mir die Vorüberlegungen schon Kopfschmerzen bereiten
