Zyklen in ungerichteten Graphen

[MrMooed]

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 :roll:
Ü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 :stupid:) würde ich weitere Infos liefern.
In Quelltext habe ich mich erst gar nicht heran gewagt, da mir die Vorüberlegungen schon Kopfschmerzen bereiten :oops:

[Furtbichler]

Führe eine Tiefensuche durch und markiere bereits besuchte Knoten.
Hier mal Pseudocode:

Delphi-Quellcode:

Procedure Cycle (Path : TPath; Graph : TGraph)
Begin
  Foreach node in Graph.NeighborOf(Path.Last)
    if (node=Path.First) and (Path.Length>MinLength) then 
      Show(Path+node)
    else if Not node.visited then begin
      node.visited := True;
      Cylce(Path+node,Graph);
      node.visited := False;
    end
end;

Dabei wird jeder zyklische Pfad, der länger als 'MinLength' ist, ausgegeben (glaube ich).

[BUG]

Beim Googeln findet man eine Menge, unter anderem dieses schöne StackOverflow-Thema.

[Aphton]

@Furchtbichler - sofern ich mich grad nicht vertue, dürfte der Code nen kleinen Fehler enthalten (obwohls ja nur Pseudocode ist..) - und zwar merkst du nicht wirklich, welche Knoten bereits besucht sind (bzw. du überprüfst nicht, ob der Knoten bereits besucht wurde), somit kann der Fall auftreten, dass Cycle nie aufhört -> z.B. hier:
A->B->C->D->B
Edit2: Sonst sollte es aber nach diesem Prinzip gehen! Einfach eine kleine Überprüfung einbauen, ob man an einem Knoten angelangt ist, der bereits im "Path" enthalten ist, jedoch nicht der "First" Knoten ist! Hier dann abbrechen, da ja der Startknoten dann nicht im Zyklus enthalten ist sondern nur dorthin führt..

@Threadstarter - es gibt da eine Unklarheit:
Willst du alle Zyklen die einen bestimmten Knoten (A) enthalten oder willst du alle Zyklen, wo kein Element eines Zyklus' in einem anderen Zyklus vorkommt?!
Ich bin mir nicht ganz sicher, aber die Implementierung dürfte je nach dem anders aussehen. Bevor ich mir also Gedanken mache, wäre es schön, wenn du das klärst!

Edit:
Da ich grad Zeit habe, habe ich das mal schnell gezeichnet :P

[Furtbichler]

Zitat:

Zitat von Aphton (Beitrag 1252086)

@Furchtbichler - sofern ich mich grad nicht vertue, dürfte der Code nen kleinen Fehler enthalten (obwohls ja nur Pseudocode ist..) - und zwar merkst du nicht wirklich, welche Knoten bereits besucht sind (bzw. du überprüfst nicht, ob der Knoten bereits besucht wurde), somit kann der Fall auftreten, dass Cycle nie aufhört -> z.B. hier:
A->B->C->D->B

Eigentlich nicht, denn B wurde bereits im ersten Abstieg besucht und damit als Visited bezeichnet. Zyklen werden nicht auftreten, aber ein und der selbe Zyklus mehrfach ausgegeben, da die Graphen nicht gerichtet sind, also z.B. A->B->C->A und A->-C->B->A (bei einem Dreieck). Genaugenommen sind es ja zwei Wege, sozusagen linksrum und rechtsrum.

[Aphton]

Hmm ok, stimmt, hab das mit "visited" nicht bedacht. Bin bei der ersten If Condition stehen geblieben und zu dem Entschluss gekommen..

[MrMooed]

Entschuldigt die lange Wartezeit :roll:

Zitat:

Zitat von Furtbichler (Beitrag 1252062)

Delphi-Quellcode:

Procedure Cycle (Path : TPath; Graph : TGraph)
Begin
  Foreach node in Graph.NeighborOf(Path.Last)
    if (node=Path.First) and (Path.Length>MinLength) then 
      Show(Path+node)
    else if Not node.visited then begin
      node.visited := True;
      Cylce(Path+node,Graph);
      node.visited := False;
    end
end;

So etwas habe ich mir auch überlegt, allerdings habe ich da meinen Denkfehler gehabt. Ich war davon ausgegangen, dass für die Rekursion node.visited wieder auf false gesetzt werden muss :shock: ich weiß nicht wie ich auf die Idee gekommen bin..

Zitat:

Zitat von Aphton (Beitrag 1252086)

@Threadstarter - es gibt da eine Unklarheit:
Willst du alle Zyklen die einen bestimmten Knoten (A) enthalten oder willst du alle Zyklen, wo kein Element eines Zyklus' in einem anderen Zyklus vorkommt?!
Ich bin mir nicht ganz sicher, aber die Implementierung dürfte je nach dem anders aussehen. Bevor ich mir also Gedanken mache, wäre es schön, wenn du das klärst!

Wenn ich dich richtig verstanden habe, dann will ich keins von beiden. Ich möchte lediglich alle Zyklen ermitteln, die über mehr als 3 Kanten gehen.

Zitat:

Zitat von Aphton (Beitrag 1252086)

Da ich grad Zeit habe, habe ich das mal schnell gezeichnet :P

Vielen lieben Dank euch dreien für die (wie immer) schnellen Antworten. Und Entschuldigung meinerseits, für die Verzögerung :oops: