Tiefensuche Probleme - Der "Rücksprung"

[schlachtrufe]

hi, ich habe eine adjazentenmatrix gegeben und möchte davon alle nachfolger verfolgen, bis zu einem knoten, welcher keine nachfolger hat. (der graph hat keinen kreis).
das habe ich nun hinbekommen, aber danach soll ja zu dem vorrigen knoten (von dem man gekomemn ist) zurück kehren und weiter suchen.
also z.b. so eine matrix:
01001
00101
00000
00100
00010

ich hab da irgendetwas mit stack gelesen, dass da die sprungmarken gespeichert werden. verstehe aber nicht, woher die rekursion weis, dass sie an der stelle wieder reingehen soll, wovon sie raus gesprungen ist, bzw wie man das in java schreibt.

code beispiel:

void suche_rek(int ii) {
    int i;
    int j=0;
    //"durchspringt" die ersten beiden Zeilen
    for (i = ii; j < matrix.length; j++) {    
    	
      if (g[i][j] == 1)
        suche_rek(j);
    } //for endet in der 3. Zeile, weil es keine 1 sen gibt
    
    int[] speicher  = new int[k];
    speicher[i] = k; //das i in speicher[i] entspricht der zeilennummer
    System.out.println(i + " - " + k);
    k--;
    rekursion(i); //ist wohl falsch
  } //rekursion


also, dieser algorithmus springt in der 3. zeile aus der for schleife, gibt dem array speicher eine nummer und soll dann eigentlich in der vorrigen zeile bei der ersten 1 (bzw an dem punkt welcher verlassen wurde) wieder einsteigen und gucken, ob es noch eine 1 gibt. etc... für alle knoten dann halt.

 

[Marco13]

Öhm - das macht sie schon automatisch. (Wäre auch schlimm, wenn nicht :wink: ). Eine Test-Funktion kann da zum Verständnis helfen

class RekTest
{
    public static void main(String args[])
    {
        rek(0, "");
    }


    public static void rek(int n, String indent)
    {
        System.out.println(indent+"Betrete Ebene "+n);
        if (n==4)
        {
            System.out.println(indent+"Fertig, n ist vier! Keine rekursiven Aufrufe mehr!");
            return;
        }
        else
        {
            System.out.println(indent+"Bin in Ebene "+n+" und mache Rekursion auf Ebene "+(n+1));
            rek(n+1, indent+"    ");
            System.out.println(indent+"Der Aufruf von Ebene "+(n+1)+" ist fertig, jetzt bin ich wieder in Ebene "+n);
        }
        System.out.println(indent+"Verlasse Ebene "+n);
    }
}

Was wohl nicht funktionieren wird ist, den Array in jedem Aufruf neu zu erstellen. Wenn der 'speicher' den Weg speichern soll, wird das nicht funktionieren, weil ja nicht nur EIN Weg gespeichert wird, sondern ein ganzer Baum. Beschreib' evlt. mal genauer, was das werden soll....

 

[schlachtrufe]

vielen dank für das gute beispiel. also wird der rücksprung mittels return gemacht?

wie meinst du das mit dem neuerstellen des arrays?

also das ist topologisches sortieren mit tiefensuche, an einem ungewichteten, gerichteten, kreisfreien graphen.
man sucht von einem knoten, ob es einen nachfolger gibt und wenn ja, dann springe zum nächsten knoten und suche dort wieder nach einem nachfolger, solange bis zu einem knoten, welcher keine nachfolger hat
-> dieser bekomtm die höchste wertigkeit.
dann muss zu dem vorrigen knoten zurück gesprungen werden, an der stelle wo man rausgesprungen ist, und weitersuchen, ob es noch nachbarn gibt.

also an der adjazentenmatrix da oben erklärt: (ich fang mal bei 1 an zu zählen)
- untersucht knoten 1 auf nachfolger -> knoten 2 ist nachfolger (da steht ja eine 1)
- sprung zu knoten 2 und beginne suche am anfang, knoten 3 ist nachfolger
- 3 hat keine nachfolger (alles 0), bekommt wertigkeit 5
- springe zurück, also zu knoten 2 an stelle 3 und suche weiter -> knoten 5 ist nachfolger
- sprung zu 5
- sprung zu 4
- sprung zu 3 und erkenne, dass knoten 3 schon eine nummer hat, also gehe wieder zurück zu 4 und wertigkeit-1
- zurückspringen zu 5, erkenne 4 hat nummer -> wertigkeit-1
- rücksprung 2, alle nachbarn haben nummer
- rücksprung 1 alle nachbarn haben nummer, fertig
damit ergibt sich für die knoten 1 2 3 4 5 folgende wertigkeit (in reihenfolge der knotennummer): 1 2 5 4 3

 

[Marco13]

Der "Rücksprung" wird gemacht, indem "return" aufgerufen wird, ODER wenn die Funktion bis zum Ende abgearbeitet ist (man könnte, wenn man's drauf anlegt, auch noch ein "return" in die letzte Zeile der Funktion schreiben :wink: )

Du hast dort einen durchlauf beschrieben ... :? Ich hab' nochmal bei Wikipedia nachgesehen - der dort beschriebene Algorithmus ist der, den ich gelernt hatte ... das mit der "Wertigkeit" musss man jetzt erstmal auf das Problem übertragen... Naja, das ist deine Aufgabe. Nur zu dem 'speicher': Vermutlich wäre es Sinnvoll, den Array entweder in der Klasse zu speichern, oder an die Funktion mit zu übergeben. Es darf ja nicht bei jedem Neuen Aufruf der Funktion ein neuer Array erstellt werden, sondern es muss (von Anfang bis Ende) immer derSELBE Array sein.

BTW: So eine Zeile wie
- sprung zu 3 und erkenne, dass knoten 3 schon eine nummer hat, also gehe wieder zurück zu 4 und wertigkeit-1
ist ein bißchen diffizil - und vielleicht liegt auch genau dort das Problem (!???!) Jedenfalls muss man dort ja bei Knoten 4 erkennen, dass man bei Knoten 3 eine bestimmte Wertigkeit gefunden hatte -- darum als Tipp: Es kann gut sein, dass die Funktion einen 'int' zurückgeben muss, der eine Wertigkeit beschreibt (bin da zwar nicht 100% sicher, es sieht stark danach aus)

 

[schlachtrufe]

ja das array speicher muss ausserhalb der funktion initialisiert werden.
das mit der wertigkeit hab ich ja am anfang nicht erwähnt, weil es mir erstmal darum nicht ging und ansonsten hät ich ja sagen können programmiert mal und schickt mir den vollständigen code

das mit dem rücksprung hab ich durch einen nikolaus algorithmus jetzt besser verstanden. warum das genau funktioniert zwar noch nicht richtig, aber da müsste man sich das mit dem stack nochmal angucken?

ja das problem liegt daran, zu erkennen das ein knoten schon eine wertigkeit abbekommen hat.
da weis ich nicht wie ich das machen soll. eine if überprüfung irgendwohin (vor dem rekursiven aufruf irgendwas überprüfen?) ?
bzw ich mach doch dann ein return nach der wertzuweisung?