Kreis in Baum finden

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Kreis in Baum finden

    Hallo allerseits,

    da meine Kenntnisse der theo. Inf. schon einige Jahre alt sind und nicht mehr aufgefrischt wurden,
    dachte ich, ich frage hier mal nach!

    Habe gerade das Problem, dass ich in hierarchisch abgelegten Daten (Vater-Kind-Beziehung in Tabelle)
    einen bzw. alle Kreise finden muss. Mir fallen derzeit aber nur naive Ansätze ein.

    Kann mir bitte jmd. wieder auf die Sprünge helfen?
    Will keinen eulerschen oder Hamiltonkreis o.ä. finden, nur feststellen, ob ein bzw. mehrere Kreise in
    den Daten vorhanden sind und diese dann ausgeben!
    Es gibt auch keinerlei Gewichtung usw., nur besagte Vater-Kind-Beziehung.

    Die DB-Abfrage zu den Daten sagt mir zwar, dass ein Kreis vorhanden ist (rekursive Query), aber leider
    nicht wo!

    Vielen Dank schon mal!

    Ciao

  • Ich häng dir dazu gerademal eine Folie unserer Vorlesung an.
    Also um einen Zyklus zu finden, machst du eine Tiefensuche und merkst dir dabei einfach Anfang und Ende der rekursiven Suche (oder in der einfachsten Implementierung einfach alle).
    Triffst du auf eine bereits genutzten Knoten hast du einen Zyklus.

    Quellcode

    1. boolean acyclic(Graph g) {
    2. Map<String, Status> visited = new TreeMap<String, Status>();
    3. for (Iterator<String> it = g.nodeIterator(); it.hasNext(); ) {
    4. String n = it.next();
    5. if (!visited.containsKey(n))
    6. if (!acyclicRek(g, n, visited))
    7. return false;
    8. }
    9. return true;
    10. }
    11. boolean acyclicRek(Graph g, String node, Map<String, Status> visited) {
    12. visited.put(node, Status.start); // Start Knoten expandieren
    13. for (Iterator<String> it = g.edgeIterator(node); it.hasNext(); ) {
    14. String expanded = it.next();
    15. if (visited.containsKey(expanded)) {
    16. if (visited.get(expanded).equals(Status.start)) // Back-Edge, Zyklus
    17. return false; // else Cross-Edge, ok
    18. } else { // !visited.containsKey(expanded)
    19. visited.put(expanded, Status.start);
    20. if (!acyclicRek(g, expanded, visited)) // rekursiv Zyklus erkannt
    21. return false;
    22. }
    23. }
    24. visited.put(node, Status.stop); // Stop Knoten expandieren
    25. return true;
    26. }
    Alles anzeigen


    Aber das hast du wohl bereits, wenn du einen Zyklus findest? Dann musst du dir also nur noch die Wege merken? Hast du einen ähnlichen Ansatz?
    Bilder

    • zyklenfreiheit.png

      54,24 kB, 587×439, 242 mal angesehen