AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Zyklen in ungerichteten Graphen

Ein Thema von MrMooed · begonnen am 14. Mär 2014 · letzter Beitrag vom 25. Mär 2014
 
Benutzerbild von MrMooed
MrMooed

Registriert seit: 18. Feb 2012
101 Beiträge
 
Delphi 7 Enterprise
 
#1

Zyklen in ungerichteten Graphen

  Alt 14. Mär 2014, 21:26
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
Gruß,
MrMooed
"Unsere Luft hat einen Vorteil: Man sieht was man einatmet" - Ein Chinese
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:33 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz