Graphen - einfache Pfade - Algorithmus gesucht



  • Guten Tag,
    existiert eine Algorithmus, der in einem gegebenen Graphen alle einfachen Pfade von einem Startknoten s mit der Länge k findet?



  • Ja, ich denke das ist ein entscheidbares Problem (ohne Beweis). Im Zweifelsfall Brute Force:

    Rekursiv durch die Kanten laufen, die vom Knoten ausgehen, dabei speichern, über welche Kanten man geht,
    damit sie nicht zweimal durchlaufen werden, nach kk Schritten die Rekursion abbrechen und den Pfad ausgeben.



  • Bei mir tauchte bei diesem Lösungsansatz das Problem des speicherns eines einzelnen Pfades auf. Das Programm soll am Ende nämlich alle Pfade seperat angeben können.



  • Finnegan schrieb:

    Ja, ich denke das ist ein entscheidbares Problem (ohne Beweis).

    Bei einem Entscheidungsproblem geht es immer um eine Ja-Nein-Frage. Meinst du vielleicht berechenbar? Das lässt sich ganz einfach beweisen: Man kann für jedes der endlich vielen Elemente von E^k prüfen, ob es sich um einen einfachen Pfad handelt.

    Im Zweifelsfall Brute Force:

    Rekursiv durch die Kanten laufen, die vom Knoten ausgehen, dabei speichern, über welche Kanten man geht,
    damit sie nicht zweimal durchlaufen werden, nach kk Schritten die Rekursion abbrechen und den Pfad ausgeben.

    Das klingt sinnvoll. Im Worst Case (vollständiger Graph) ist dieser Algorithmus auch nicht (signifikant) in der Laufzeit zu schlagen, weil die Laufzeit in derselben Größenordnung wie die Ausgabegröße liegt.

    numbo: Was genau ist dein Problem beim Speichern der Pfade? An der Stelle, an der Finnegan den Pfad ausgibt, kannst du ihn natürlich auch in einer Datenstruktur speichern.



  • Ich habe eine Knoten-Klasse. Diese besitzt ein vector<int> Element, dass so groß ist, wie die maximale Anzahl der möglichen Verbindugen unter allen Knoten. Dieser Vektor gibt an, zu welchen anderen Knoten der jetzige Verbunden ist (0: keine Verbindung; 1: eine Verbindung)
    Beispiel dazu: Mein Graph sieht so aus(---: Verbindung): A---B---C
    Knoten A:
    vector[0]: 0
    vector[1]: 1
    vector[2]: 0

    Knoten B:
    vector[0]: 1
    vector[1]: 0
    vector[2]: 1

    Knoten C:
    vector[0]: 0
    vector[1]: 1
    vector[2]: 0

    Ich wollte mir nun die Pfade in einem string speichern, also z.b "ACBD" und alle Pfade dann in einem vector<string> speichern.

    Da taucht dann auch schon mein Problem auf:

    rekursive Methode (anderes Beispiel)

    push_back(string)
      push_back(A)
        push_back(C)
          push_back(B)
            push_back(D)
        push_back(Z)
          push_back(C)
            push_back(X)
    

    Pfade müssten also lauten: 1: "ACBD" und 2: "AZCX" tun sie aber mit dieser Methode nicht. Daran rätsel ich jetz schon eine ganze Weile



  • Naja, du musst natürlich auch pop_back zwischendurch benutzen.

    void func(currentVertex)
    {
        if(stack.contains(currentVertex))
            return;
    
        stack.push(currentVertex)
        if(stack.size == k)
            paths.push_back(stack.toString())
        for each vertex adjacent to currentVertex
            func(vertex)
        stack.pop()
    }
    


  • Danke dir


Log in to reply