Breitensuche mit Parametern Start und Ziel

[Wave]

Hallo,
ich habe eine Frage zur Breitensuche mit den Parametern Start und Ziel:
Ich finde den Fehler nicht: wenn das Ziel gefunden ist, sollte die Breitensuche abbrechen und nach dem gefundenen Zielknoten keine weiteren Knoten mehr ausgegeben werden.
Die normale Breitensuche Methode "breitensuche(start)" mit einem Parameter Start funktioniert (denke ich).
Wie kann ich mit der Methode Breitensuche für die Parameter Start und Ziel "breitensuche2(start, ziel)" erreichen, dass beim Finden des Zielknotens dann die Breitensuche beendet wird?
Auch meine Testklasse lege ich hier bei.
Bin Schüler und weiß nicht weiter.
Danke.

public class Knoten{
    
    private String bezeichnung;
    private boolean istBesucht;
    
    public Knoten(String neueBezeichnung){
        bezeichnung = neueBezeichnung;
    }
    
    public String bezeichnungGeben(){
        return bezeichnung;
    }
    
    public void bezeichnungSetzen(String neueBezeichnung){
        bezeichnung = neueBezeichnung;
    }
    
    public boolean istBesuchtGeben(){
        return istBesucht;
    }
    
    public void istBesuchtSetzen(boolean neuIstBesucht){
        istBesucht = neuIstBesucht;
    }
}

import java.util.*;

public class Graph{

    private Knoten[] knotenfeld;
    private int[][] adjazenzmatrix;
    private int maxAnzahl;
    private int aktAnzahl;
    
    public Graph(int neueMaxAnzahl){
        knotenfeld = new Knoten[neueMaxAnzahl];
        adjazenzmatrix = new int[neueMaxAnzahl][neueMaxAnzahl];
        maxAnzahl = neueMaxAnzahl;
        aktAnzahl = 0;
    }
    
    public Knoten[] knotenfeldGeben(){
        return knotenfeld;
    }
    
    public int[][] adjazenzmatrixGeben(){
        return adjazenzmatrix;
    }
    
    public void knotenEinfuegen(Knoten k){
        if(aktAnzahl < maxAnzahl){
            knotenfeld[aktAnzahl] = k;
            aktAnzahl++;
        }
        else{
            System.out.println("Fehler! Es kann kein Knoten mehr eingefuegt werden.");
        }
    }
    
    public void knotenEinfuegen2(Knoten k){
        if (aktAnzahl < maxAnzahl){
            boolean istEingefuegt = false;
            int index = 0;
            while ((index < maxAnzahl) && (!istEingefuegt)){
                if (knotenfeld[index] == null){
                    knotenfeld[index] = k;
                    istEingefuegt = true;
                }
                else{
                    index++;
                }
            }
            aktAnzahl++;
        }
        else{
            System.out.println("Fehler! Es kann kein Knoten mehr eingefuegt werden.");
        }
    }
    
    public void kanteHinzufuegen(int startindex, int zielindex, int wert){
        if(startindex < 0 || zielindex < 0 || startindex >= aktAnzahl || zielindex >= aktAnzahl){
            System.out.println("Fehler! Falscher Index. Die Kante kann nicht hinzugefuegt werden.");
        }
        else{
            adjazenzmatrix[startindex][zielindex] = wert;
        }
    }
  
    public void kanteEntfernen(int startindex, int zielindex){
        if(adjazenzmatrix[startindex][zielindex] == 0 || startindex >= aktAnzahl || zielindex >= aktAnzahl){
            System.out.println("Fehler! Die Kante kann nicht entfernt werden.");
        }
        else{
            adjazenzmatrix[startindex][zielindex] = 0;
        }
    }
    
    public void alleKantenEntfernen(){
        for(int i = 0; i < maxAnzahl; i++){
            for(int j = 0; j < maxAnzahl; j++){
                adjazenzmatrix[i][j] = 0;
            }
        }
    }
    
    public int knotenindexSuchen(Knoten k){
        int index = -1;
        int i = 0;
        while(index < 0 && i < knotenfeld.length){
            if(knotenfeld[i].equals(k)){
                index = i;
            }
            else{
                i++;
            }
        }
        if(index < 0){
            System.out.println("Fehler! Der Knoten wurde nicht gefunden.");
        }
        return index;
    }
    
    public int knotenindexSuchen2(String name){
        int index = -1;
        int i = 0;
        while(index < 0 && i < knotenfeld.length){
            if(knotenfeld[i].bezeichnungGeben().equals(name)){
                index = i;
            }
            else{
                i++;
            }
        }
        if(index < 0){
            System.out.println("Fehler! Der Knoten wurde nicht gefunden.");
        }
        return index;
    }
    
    public void kanteHinzufuegen2(String start, String ziel, int wert){
        int startindex = knotenindexSuchen2(start);
        int zielindex = knotenindexSuchen2(ziel);
        kanteHinzufuegen(startindex, zielindex, wert);
    }
        
    public void knotenEntfernen(String name){
        int knotenindex = knotenindexSuchen2(name);
        if(knotenindex < 0){
            System.out.println("Fehler! Der Knoten konnte nicht entfernt werden.");
        }
        else{
            for(int i = 0; i < aktAnzahl; i++){
                adjazenzmatrix[knotenindex][i] = 0;
                adjazenzmatrix[i][knotenindex] = 0;
            }
            knotenfeld[knotenindex] = null;
        }   
    }   
    
    public void adjazenzmatrixAusgeben(){
        System.out.print("  ");
        for(int i = 0; i < aktAnzahl; i++){
            System.out.print("  " + i + "  ");
        }
        System.out.println("  ");
        for(int i = 0; i < aktAnzahl; i++){
            System.out.print(i + " ");
            for(int j = 0; j < aktAnzahl; j++){
                System.out.print(" " + adjazenzmatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public void knotenfeldAusgeben(){
        System.out.println("Knotendaten:");
        for(int i = 0; i < aktAnzahl; i++){
            System.out.println(knotenfeld[i].bezeichnungGeben());
            System.out.println();
        }
    }
    
    public void breitensuche(String start){
        int startindex = knotenindexSuchen2(start);
        if(startindex == -1){
            System.out.println("Fehler! Der Startknoten konnte nicht gefunden werden!");
        }
        else{
            for(int i = 0; i < aktAnzahl; i++){ // Alle Knoten auf "unbesucht" setzen
                knotenfeld[i].istBesuchtSetzen(false);
            }
            ArrayList<Integer> warteschlange = new ArrayList<Integer>();    // Warteschlange fuer die Knoten (Speichern der Indizes)
            warteschlange.add(startindex);  // Hinzufuegen des Startknotens in die Warteschlange
            knotenfeld[startindex].istBesuchtSetzen(true);  // Startknoten auf "besucht" setzen
            System.out.println("Breitensuche: ");
            System.out.println("Knoten " + knotenfeld[startindex].bezeichnungGeben() + " besucht!");
            while(!warteschlange.isEmpty()){
                int aktiverKnotenindex = warteschlange.remove(0);
                for(int i = 0; i < aktAnzahl; i++){
                    if(adjazenzmatrix[aktiverKnotenindex][i] > 0 && !knotenfeld[i].istBesuchtGeben()){
                        knotenfeld[i].istBesuchtSetzen(true);
                        warteschlange.add(i);
                        System.out.println("Knoten " + knotenfeld[i].bezeichnungGeben() + " besucht!");
                    }
                }
            }
        }
    }
    
    public void breitensuche2(String start, String ziel){
        int startindex = knotenindexSuchen2(start);
        int zielindex = knotenindexSuchen2(ziel);
        if(startindex == -1 || zielindex == -1){
            System.out.println("Fehler! Der Startknoten oder der Zielknoten konnte nicht gefunden werden!");
        }
        else{
            for(int i = 0; i < aktAnzahl; i++){ // Alle Knoten auf "unbesucht" setzen
                knotenfeld[i].istBesuchtSetzen(false);
            }
            ArrayList<Integer> warteschlange = new ArrayList<Integer>();    // Warteschlange fuer die Knoten (Speichern der Indizes)
            warteschlange.add(startindex);  // Hinzufuegen des Startknotens in die Warteschlange
            knotenfeld[startindex].istBesuchtSetzen(true);  // Startknoten auf "besucht" setzen
            System.out.println("Breitensuche: ");
            System.out.println("Knoten " + knotenfeld[startindex].bezeichnungGeben() + " besucht!");
            //int aktiverKnotenindex = startindex;
            while(!warteschlange.isEmpty()){ // && aktiverKnotenindex != zielindex
                int aktiverKnotenindex = warteschlange.remove(0);
                if(aktiverKnotenindex == zielindex){
                    System.out.println("Ziel gefunden!");
                    return;
                }
                else{
                    for(int i = 0; i < aktAnzahl; i++){
                        if(adjazenzmatrix[aktiverKnotenindex][i] > 0 && !knotenfeld[i].istBesuchtGeben()){
                            knotenfeld[i].istBesuchtSetzen(true);
                            warteschlange.add(i);
                            System.out.println("Knoten " + knotenfeld[i].bezeichnungGeben() + " besucht!");
                        }
                    }
                }
            }
        }
    }
}

public class Testablauf{
        
    private Graph g;
    
    public void ablaufen(){
        
        g = new Graph(5);   // Der Graph hat 5 Knoten
        
        Knoten k1 = new Knoten("A");
        Knoten k2 = new Knoten("B");
        Knoten k3 = new Knoten("C");
        Knoten k4 = new Knoten("D");
        Knoten k5 = new Knoten("E");
        
        g.knotenEinfuegen(k1);  // Index 0
        g.knotenEinfuegen(k2);  // Index 1
        g.knotenEinfuegen(k3);  // Index 2
        g.knotenEinfuegen(k4);  // Index 3
        g.knotenEinfuegen(k5);  // Index 4
        
        g.kanteHinzufuegen(0, 1, 3);    // A-B
        g.kanteHinzufuegen(1, 0, 3);
        g.kanteHinzufuegen(0, 2, 4);    // A-C
        g.kanteHinzufuegen(2, 0, 4);
        g.kanteHinzufuegen(0, 4, 1);    // A-E
        g.kanteHinzufuegen(4, 0, 1);
        g.kanteHinzufuegen(1, 2, 2);    // B-C
        g.kanteHinzufuegen(2, 1, 2);
        g.kanteHinzufuegen(2, 3, 1);    // C-D
        g.kanteHinzufuegen(3, 2, 1);
        g.kanteHinzufuegen(3, 4, 5);    // D-E
        g.kanteHinzufuegen(4, 3, 5);
        
        //g.breitensuche("A");
        //g.breitensuche("D");
        //g.breitensuche("C");
        g.breitensuche2("B", "D");
    }
}

 

[Barista]

Nach Ansehen des Codes würde ich sagen, dass der Code zum Beenden

return;

bereits vorhanden ist.

 

[Wave]

Hallo @Barista,
danke für die Antwort.
Ich meinte: wenn ich die Ausgabe am Bildschirm mache (über die Testklasse), dann kann es passieren, dass wenn ich die Breitensuche von "B" nach "D" mache, nach dem Knoten D noch ein Knoten ausgegeben wird. Der Algorithmus sollte dann eigentlich aber nichts mehr nach "D" ausgeben?

Oder kommen die "restlichen Knoten" noch von den Nachfolgern der unbearbeiteten Nachbarknoten?