3. Finden von Zyclen in Graf????

Finden von Zyclen in Graf????

  • M

    Gibt es eina algorithmus das alle Zyclen in ein gerichteten graf findet?. Aber alle zyclen wen es überhaubt zyclen gibt. Ich kenn kein algorithmus kann mir einer weiterhelfen. Zeit ist egal haubsachlich ich muss nicht viel rum programmieren.

    0
  • ?

    Du kannst ja noch nicht mal Graph schreiben...

    0
  • C

    Breitensuche/Tiefensuche: wenn du bei einem bereits besuchten Knoten ankommst, hast du einen Zyklus. Danach mußt du nur noch sehen, wo der entlanggegangen ist.

    (wenn Zeit keine Rolle spielt, kannst du auch blind raten: bilde nacheinander alle Kombinationen von Knoten (sind nur 2^|V| ;)) und schau nach, ob sie einen Zyklus bilden)

    0
  • V

    CStoll schrieb:

    (wenn Zeit keine Rolle spielt, kannst du auch blind raten: bilde nacheinander alle Kombinationen von Knoten (sind nur 2^|V| ;)) und schau nach, ob sie einen Zyklus bilden)

    er/sie wollte es möglichst einfach haben. das teilproblem "und schau nach, ob sie einen Zyklus bilden" ist viel zu komplex, finde ich. das ergibt ja zeilenweise code.
    viel besser isses so:

    schleife
  tmpknotenmenge=knotenmenge
  tmpknotenmenge.push_back(zufälligen aus tmpoknotenmenge)
  random_shuffle(tmpknotenmenge)
  aktuellerknoten=tmpknotenmenge[0]
  schleife2
    aktueller=zufälliger nachfolger
    oder break schleife2, wenn kein nachfolger gefunden
    if aktueller==tmpknotenmenge[0]
       ausgabe zyklus gefunden
    /if
  /schleife2
/schleife

    also das sollte einen zyklus finden. hoffentlich ist einer drin. und naja, minimal ist der zyklus unter umstönden nicht. aber das war ja nicht verlangt. und er/sie braucht sich nicht mit komplizierten sachen wie tiefensuche zu beschäftigen.

    0
  • C

    [quote="volkard"]

    CStoll schrieb:

    er/sie wollte es möglichst einfach haben. das teilproblem "und schau nach, ob sie einen Zyklus bilden" ist viel zu komplex, finde ich.

    Er will doch alle Zyklen finden 😉
    In dem Fall dürfte sich das Teilproblem "schau nach, ob sie einen Zyklus bilden" dann darauf beschränken, alle Permutationen der Knoten zu durchlaufen (STL hat dafür die Funktion next_permutation()) und jeweils zu prüfen, ob die Knoten in der aktuellen Reihenfolge miteinander verbunden sind.

    (PS @Master: Aus meinen Ansätzen ein Programm zu schreiben, überlasse ich dir als Übungsaufgabe :D)

    0
  • M

    xmmmmmmmmm ok danke danke fur die hilfe, ich uberlegs mir, ich galub ich mache breitensuche. Jedebfals danke an alle.

    0
  • V

    Master User schrieb:

    xmmmmmmmmm ok danke danke fur die hilfe, ich uberlegs mir, ich galub ich mache breitensuche. Jedebfals danke an alle.

    jup.
    dein "Zeit ist egal haubsachlich ich muss nicht viel rum programmieren." hat uns ein wenig erschreckt. deshalb die nonsense-antworten. breitensuche ist eine gute wahl und du wirst vermutlich wenige stunden brauchen.
    wenn es noch wo hakt, sag bescheid, bei konkreten fragen sind wir ernsthafter.

    0
  • M

    :'(.

    ich habe die funktion fast fertich aber ich habe mir folgendes überlegt.

    A---->B---------->C-------D-----
/\     |                 /\     |
|     \/                /       |
|     F----------E-----|        |
|-------------------------------.

    Mit der tiefensuche bekome ich A,B, (F geht in stack),C,D, danch kuke ich weiter bekomme ich A ein ziklus gefunden. Dannach hole ich F vom stack offne E kuke weiter D habe ich schon besucht und fertich. kein zilus A,B,F,E,D,A. DAs gleiche bekomme ich bei breitensuche.

    Danach habe ich mir überlegt ein baum zu bauen das immer alle knoten offnet aber wenn mein graf folgendes sub Graf habe, dann wird mein algorithmus nie beended.

    F---------> G
       /\          |
       |           |
-------J           |
       /\          |
       |           |
       |          \/
       V<---------K

    Dannach habe ich mir überlegt alle wege zu bilden aber hat kein sin, da es nie alle ziklen finded wenn z.b. ein ziklus zwei mal durch ein knoten gehen mus. z.b.

    A,B,C,D,B,G,A

    zwei mal durch B. Dann habe ich mir überlegt n -mal alle knoten in mein weg zu tun aber was geschit wenn es n+1 -mal duch ein knoten mus damit es ein ziklus findet :/. Verdammt 2 tage fur die katz programmiert. Wieso mach ich mir so viele gedanken was muss ich machen dammit ich die lössung finde :/.

    0
  • M

    Was were wenn ich fur alles knoten auser fur den startknote herausfinde wie fiehle mal ich die benutze und dann ein leksikon bilde mit all den werscheinlichen wege und ich eins nach einander kucke ob es ein ziklus bilded?.

    0
  • C

    Master User schrieb:

    Mit der tiefensuche bekome ich A,B, (F geht in stack),C,D, danch kuke ich weiter bekomme ich A ein ziklus gefunden. Dannach hole ich F vom stack offne E kuke weiter D habe ich schon besucht und fertich. kein zilus A,B,F,E,D,A. DAs gleiche bekomme ich bei breitensuche.

    Da ist dein Fehler drin - du hattest D zwar schon besucht, aber auf einem anderen Weg - also zählt es für die Suche über F->E-> wieder als unbesucht.

    PS: Du benötigst vielleicht erstmal ein Lexikon der deutschen Sprache 🤡

    0
  • P

    Ich denke grad, dass alle Kreise zu bestimmen sehr viel Zeit in Anspruch nehmen kann. In einem gerichteten Graphen, in dem zwischen allen Knotenpaaren beide Kanten vorhanden sind, gibt es mal abgeschätzt für jede Teilmenge von Knoten und dann für jede Permutation der Knoten geteilt durch die zweifache Anzahl der Knoten einen Kreis. Es gibt aber mindestens 2^Knotenanhahl - Knotenanzahl - 1 Kreise.

    Zum Aufzählen würde ich folgendes Verfahren vorschlagen:
    1. Bestimme alle starken Zusammenhangskomponenten.
    2. Backtracking innerhalb der Komponenten um die Kreise aufzuzählen.

    Ich denke auch grad, dass es nicht schneller geht.

    0
  • M

    Da ist dein Fehler drin - du hattest D zwar schon besucht, aber auf einem anderen Weg - also zählt es für die Suche über F->E-> wieder als unbesucht.

    so funktioniert aber die tiefensuche soweit ich mich erinere. Sonst wurde ich ja bis zum mein lebensende in den graf herumspazieren.

    0
  • C

    Ja, so funktioniert die Tiefensuche unter normalen Bedingungen - aber normalerweise bis du dir auch sicher, daß du jeden Knoten nur einmal besuchen mußt, um alle darin verfügbaren Informationen abzusammeln. Für dein Problem mußt du die Tiefensuche aber richtig anpassen, damit du alle Lösungen findest.

    sprich: Du mußt beim zurücklaufen durch den Graph eventuell gesetzte "besucht"-Marken wieder entfernen. Indem du die Marken auf dem aktuell untersuchten Weg (noch) stehenläßt, verhinderst du wirksam eine Endlosschleife.

    0
Anmelden zum Antworten