Graph Tiefensuche Methode

[FinnJ]

Hallo,
ich hab mal wieder eine Frage und zwar habe ich eine Methode geschrieben (als Vorbereitung aufs ABI und um mich wieder ein bisschen in Graphen einzulesen), welche den Graphen "durchsuchen" soll und von dem gegebenen Startknoten aus alle Knoten besuchen soll und diese zurückgeben soll.

public void GraphenDurchlauf(KNOTEN startKnoten){
        startIndex = KnotenNummerGeben(startKnoten);
       
        if (matrix[startIndex][startIndex] != -1){
                if (startKnoten.besucht == false){
                    for (int i = 0, i < AnzKnoten, i++){
                        for (int k = 0, k < AnzKnoten, k++){
                            if (matrix[i][k] != 0){
                                if (i != startIndex && k != startIndex){
                                    this.besucht = true;
                                    return this;
                                }
                            }
                        }
                    }
                }
            }
        }

Ich denke es ist vorallem viel viel zu kompliziert aufgebaut, das hätte man sicher auch einfacher machen können, aber würde der Code, vorausgesetzt Methoden wie "KnotenNummerGeben" usw. sind bereits implementiert, funktionieren oder habe ich irgendwo einen Fehler gemacht?

Und ja ich weiß ich könnte das auch einfach testen, allerdings habe ich dazu gerade nicht die Zeit und müsste mir erst einmal wieder anschauen wie das alles funktioniert. Das werde ich zwar noch machen, aber ich hoffe, dass sich jemand findet der mir kurz sagen kann, ob diese Methode vom Grundprinzip her Sinn macht oder Schwachsinn ist.
Mit freundlichen Grüßen

 

[KonradN]

Ein paar kleine Tipps:

a) if (irgendwas == false) ==> if(!irgendwas)

b) Umkehren von der Logik bei Ifs:

Dein Code mit deutlich weniger Einrückungen:

public void GraphenDurchlauf(KNOTEN startKnoten){
    startIndex = KnotenNummerGeben(startKnoten);
      
    if (matrix[startIndex][startIndex] == -1) return;

    if (startKnoten.besucht) return;
    
    for (int i = 0, i < AnzKnoten, i++){
        for (int k = 0, k < AnzKnoten, k++){
            if (matrix[i][k] == 0) continue;
                
            if (i != startIndex && k != startIndex){
                this.besucht = true;
                return this;
            }
        }
    }
}

Das zusammen mit Dingen in Methoden auslagern hilft oft, Code lesbarer zu machen.

Ansonsten ist der Code so auf jeden Fall falsch und lässt sich nicht übersetzen:
Die Methode hat als Rückgabetyp void angegeben und du hast ein return this. Und im Augenblick sehe ich nicht auf Anhieb, was Du da genau versuchst an Logik und was für typen da überhaupt wie eine Rolle spielen. Die Methode scheint in KNOTEN zu sein. Aber das mag durchaus daran liegen, dass ich da die Typischen Implementationen auch nicht im Kopf habe. Kann also sein, dass jemand, der erst vor kurzem mit so einer Aufgabe umgehen musste da evtl. etwas an Wissen hat, das er da mit übertragen kann. Aber ich bräuchte zu genaueren Aussagen die genaue Aufgabe mit gegebenen Strukturen.

 

[FinnJ]

Vielen Dank für die Tipps! Ich habe versucht mit dieser Methode einen Graphen von einem startKnoten aus zu durchlaufen, indem ich durch die gesamte Matrix durchgehe und jeden Knoten den ich besucht habe zurückgebe und auch als besucht markiere. Während ich das geschrieben habe ist mir aber aufgefallen, dass ich glaub ich ziemlichen Schmarn in mein Programm geschrieben habe, weil ich ja wenn der Knoten eine Kante zu einem anderen Knoten (der nicht er selbst ist) hat erst den Knoten auf besucht setze und ihn dann ausgebe (zumindest glaube ich dass return this in diesem Fall den Knoten zurückgibt). Macht also insgesamt nur sehr wenig Sinn, ich könnte da höchstens irgendwie ein Programm draus bauen, was jede Kante oder so zurückgibt denke ich.
Danke trotzdem für deine Hilfe auch wenn man bei dem Programm jetzt nicht wirklich viel retten konnte xD

 

[Jw456]

Frage was int AnzKnoten?
Wenn das die gesamte Anzahl an Knoten ist wir das nicht gehen mal von den Fehler mit dem return abgesehen.

Bei einem Array [10] [10]
Und AnzKnoten = 100 maximale Anzahl würdest du fehler zur Laufzeit bekommen.

 

[FinnJ]

Frage was int AnzKnoten?
Wenn das die gesamte Anzahl an Knoten ist wir das nicht gehen mal von den Fehler mit dem return abgesehen.

Bei einem Array [10] [10]
Und AnzKnoten = 100 maximale Anzahl würdest du fehler zur Laufzeit bekommen.

Bin jetzt einfach davon ausgegangen dass ich halt alle Knoten in das Array einfüge und damit die gesamtanzahl der Knoten (anzKnoten) abzüglich 1 (weil ich ja bei 0 anfange) mich durch den gesamten Knoten kommen lässt. Aber macht insgesamt leider sehr wenig Sinn das Programm.

 

[Jw456]

Aber macht insgesamt leider sehr wenig Sinn das Programm.

Da hast du recht.

 

[KonradN]

Vielen Dank für die Tipps! Ich habe versucht mit dieser Methode einen Graphen von einem startKnoten aus zu durchlaufen, indem ich durch die gesamte Matrix durchgehe und jeden Knoten den ich besucht habe zurückgebe und auch als besucht markiere.

Ich habe noch nicht verstanden, was Du überhaupt genau willst. Was soll das Ergebnis sein? Wenn das Ergebnis nur sein soll: Es gibt einen Pfad von Start zu Ende, dann wäre doch denkbar ein rekursiver Ansatz:

- Aufgerufen wird es auf dem Startknoten.
- Ist der Startknoten der Endknoten? -> Ergebnis true zurück geben.
- Ist der Knoten bereits besucht worden? -> Ergebnis false zurück geben.
- Diesen Knoten als besucht markieren.
- Für jeden Knoten, der von diesem Knoten aus erreichbar ist:
---> Zwischenergebnis = rekursiver Aufruf auf den erreichbarem Knoten
---> Wenn Zwischenergebnis true -> Ergebnis true zurück geben
- Ergebnis false zurück geben

Etwas in der Art würde mir vorschweben.

Wenn Du den Weg selbst haben willst, dann müsste man die Rückgabe ändern. Dann wäre die Rückgabe z.B, nicht true / false sondern eine Liste von Knoten. null würde dem false entsprechen. Eine Liste mit Knoten drin wäre der Weg. (Also bei dem Endknoten erreicht würde eine List.of(Endknoten) zurück gegeben. Und wenn eine Liste beim rekursiven Aufruf zurück kommt, wird der aktuelle Knoten zur Liste hinzu gefügt und die Liste weiter zurück gegeben.) Damit würde EIN Weg gefunden werden. das wäre aber nicht der kürzeste Weg.

Das einfach mal als ein paar kurze Gedanken - aber das war schon sehr lange kein Thema - mag sein, dass ich mich da jetzt gerade irre.

ABER: Schau mal im Forum in der Suchfunktion. Es gibt ein Test Driven Development Beitrag der TDD erläutert an Hand eines Graphen und der zeigt dann auch not gedrungen etwas, wie man da vorgehen kann 🙂

 

[FinnJ]

Ich habe noch nicht verstanden, was Du überhaupt genau willst. Was soll das Ergebnis sein? Wenn das Ergebnis nur sein soll: Es gibt einen Pfad von Start zu Ende, dann wäre doch denkbar ein rekursiver Ansatz:

- Aufgerufen wird es auf dem Startknoten.
- Ist der Startknoten der Endknoten? -> Ergebnis true zurück geben.
- Ist der Knoten bereits besucht worden? -> Ergebnis false zurück geben.
- Diesen Knoten als besucht markieren.
- Für jeden Knoten, der von diesem Knoten aus erreichbar ist:
---> Zwischenergebnis = rekursiver Aufruf auf den erreichbarem Knoten
---> Wenn Zwischenergebnis true -> Ergebnis true zurück geben
- Ergebnis false zurück geben

Etwas in der Art würde mir vorschweben.

Wenn Du den Weg selbst haben willst, dann müsste man die Rückgabe ändern. Dann wäre die Rückgabe z.B, nicht true / false sondern eine Liste von Knoten. null würde dem false entsprechen. Eine Liste mit Knoten drin wäre der Weg. (Also bei dem Endknoten erreicht würde eine List.of(Endknoten) zurück gegeben. Und wenn eine Liste beim rekursiven Aufruf zurück kommt, wird der aktuelle Knoten zur Liste hinzu gefügt und die Liste weiter zurück gegeben.) Damit würde EIN Weg gefunden werden. das wäre aber nicht der kürzeste Weg.

Das einfach mal als ein paar kurze Gedanken - aber das war schon sehr lange kein Thema - mag sein, dass ich mich da jetzt gerade irre.

ABER: Schau mal im Forum in der Suchfunktion. Es gibt ein Test Driven Development Beitrag der TDD erläutert an Hand eines Graphen und der zeigt dann auch not gedrungen etwas, wie man da vorgehen kann 🙂

Ich bin mir nachdem ich mir das "Programm" jetzt immer wieder durchgelesen habe selbst nicht mal mehr ganz sicher was da überhaupt rauskommen sollte, weil ich ganz grobe Logikfehler (neben den anderen Fehlern) eingebaut habe. Aber vielen Dank für die Anleitung, ich werde anhand dieser mal versuchen etwas zu programmieren nachdem ich mir erstmal den Beitrag der TDD anschaue.

Vielen Dank und noch einen schönen Abend