Zyklen in ungerichteten Graphen

[Furtbichler]

Zitat von 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

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

Zitat von Furtbichler:

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 ich weiß nicht wie ich auf die Idee gekommen bin..

Zitat von Aphton:

@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 von Aphton:

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

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