Wieso bricht die Rekursion nicht ab?

[Luk10]

Grüße,

Ich habe immer noch Probleme mit der blöden Tiefensuche bei Graphen.
Hier ist meine Umsetztung:

	public void depthFirstSearch(int start_index, int end_index) {
		
        if (start_index != end_index) {
        	
        	nodelist[start_index].setVisited(true);
			
			for(int i = 0; i < nodelist.length; i++) {
				if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
					
					System.out.println("Kante getroffen: " + start_index + " -> " + i);
					nodelist[start_index].setNextNode(nodelist[i]);
					
					depthFirstSearch(i, end_index);
				}
			}
		}
        else {
        	System.out.println("Ende");
        }
	}

Aufruf mit start_index = 0, end_index = 6.

Die Ausgabe:

Kante getroffen: 0 -> 1
Kante getroffen: 1 -> 2
Kante getroffen: 2 -> 3
Kante getroffen: 3 -> 4
Kante getroffen: 3 -> 5
Kante getroffen: 5 -> 6
Ende
Kante getroffen: 5 -> 8
Kante getroffen: 8 -> 9
Kante getroffen: 9 -> 10
Kante getroffen: 9 -> 11
Kante getroffen: 11 -> 12

Wieso hört der Aufruf nach "Ende" nicht auf? Durch die Abbruchbedingung (start_index != end_index) sollte es doch eigentlich stoppen sobald i = 6 als start_index übergeben wird ...

:noe:
-Luk10-

 

[Marco13]

Nur überflogen, aber... er muß wohl auch die for-Schleife abbrechen. Ungetestet

// Gibt zurück, ob weitergemacht werden soll
public boolean depthFirstSearch(int start_index, int end_index) {
        
        if (start_index != end_index) {
            
            nodelist[start_index].setVisited(true);
            
            for(int i = 0; i < nodelist.length; i++) {
                if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
                    
                    System.out.println("Kante getroffen: " + start_index + " -> " + i);
                    nodelist[start_index].setNextNode(nodelist[i]);
                    
                    boolean shouldContinue = depthFirstSearch(i, end_index);
                    if (!shouldContinue) break;
                }
            }
            return true;
        }
        else {
            System.out.println("Ende");
            return false;
        }
    }

Aber bin gerade nicht sicher, wenn's das nicht war, schau' ich nochmal.

 

[Luk10]

Ja, hast recht! Das muss noch ein break rein:

public void depthFirstSearch(int start_index, int end_index) {
		
        if (start_index != end_index) {
        	
        	nodelist[start_index].setVisited(true);
			
			for(int i = 0; i < nodelist.length; i++) {
				if (ended) {
					ended = false;
					break;
				}
				
				if (adjacencyMatrix[start_index][i] != null && !nodelist[i].isVisited()) {
					
					System.out.println("Kante getroffen: " + start_index + " -> " + i);
					nodelist[start_index].setNextNode(nodelist[i]);
					
					depthFirstSearch(i, end_index);
				}
			}
		}
        else {
        	ended = true;
        }
	}

Instanzvariavle ended: boolean

Danke,
-Luk10-

 

[Marco13]

Das mit der Instanzvariable sieht irgendwie komisch aus (niemand weiß, WANN die WELCHEN Wert hat) aber ... wenn's reicht...