# Breitensuche



## LauraHe (9. Mrz 2010)

Ich soll diese Breitensuche abgegeben und bei der abgabe wird als Fehler angegeben: BFS.search() auf Graph ohne Pfeile fehlerhaft expected:<true> but was:<false>
Kann mir jmd sagen was bei mir da falsch ist?

```
public class BFS {
    /**
     * Diese Methode soll mittels Breitensuche pruefen, ob ein Weg vom
     * Startknoten source zum Zielknoten target existiert.
     * 
     * @param <search>
     *            Suche
     * 
     * @param graph
     *            Wege
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @return true, wenn Weg existiert
     */
    public static boolean search(ISimpleGraph graph, int source, int target) {

        if (source <= 0 || target <= 0 || source > graph.getNodeCount()
                || target > graph.getNodeCount())
            return false;
        if (source == target)
            return true;
        if (graph.getEdgeCount() == 0)
            return false;
        LinkedList<Integer> sucher = new LinkedList<Integer>();
        LinkedList<Integer> tester = new LinkedList<Integer>();
        sucher.add(source);
        tester.add(source);
        while (!sucher.isEmpty()) {
            int c;
            c = sucher.remove();
            if (c == target)
                return true;

            if (graph.getSuccessors(c) != null) {
                for (int i = 0; i < graph.getSuccessors(c).length; i++) {
                    if (!tester.contains(graph.getSuccessors(c))) {
                        sucher.add(graph.getSuccessors(c)[i]);
                        tester.add(graph.getSuccessors(c)[i]);
                    }
                }
            }
        }
        return false;
    }
}
```


----------



## SlaterB (9. Mrz 2010)

> if (!tester.contains(graph.getSuccessors(c))) {

-> 

if (!tester.contains(graph.getSuccessors(c)_)) {
?

oder noch besser:
int x = graph.getSuccessors(c));
if (!tester.contains(x)) {
                        sucher.add(x);
                        tester.add(x);
                    }

------



		Java:In die Zwischenablage kopieren


if (graph.getSuccessors(c) != null) {
                for (int i = 0; i < graph.getSuccessors(c).length; i++) {
                    if (!tester.contains(graph.getSuccessors(c)[i])) {
                        sucher.add(graph.getSuccessors(c)[i]);
                        tester.add(graph.getSuccessors(c)[i]);
                    }
                }
            }


ist insgesamt auch heftig in Bezug auf graph.getSuccessors(c),
wenn c vier Nachfolger hat, die alle bisher unbekannt sind, dann wird insgesamt 18x graph.getSuccessors(c) bestimmt,
vielleicht muss dabei jedesmal das Netz durchsucht, ein Array neu erstellt werden

schreib doch vorher EINMAL
int[] nachfolger = graph.getSuccessors(c);
und aller Code bezogen auf das lokal gemerkte Array

lokale Variablen, wichtig wichtig_


----------



## LauraHe (9. Mrz 2010)

Habe ich geschrieben in der SimpleGraph klasse.Wie kann ich den an dieser stelle verwenden.Heißt int[]nachfolgerknoten. Ich hab den Code jetzt selbst noch ein wenig umgeschrieben. Jetzt ist anscheinend der Fehler das in einem bestimmten Fall true rauskommen sollte bei mir aber false ausgegeben wird.

```
package jpp.simplegraph;

import java.util.*;

/**
 * In dieser Klasse wird die Breitensuche implementiert, welche ueberprueft ob
 * ein Weg von einem gegebenen Startknoten zu einem bestimmten Zielknoten
 * existiert.
 * 
 * @author Laura
 * 
 */

public class BFS {
    /**
     * Diese Methode soll mittels Breitensuche pruefen, ob ein Weg vom
     * Startknoten source zum Zielknoten target existiert.
     * 
     * @param <search>
     *            Suche
     * 
     * @param graph
     *            Wege
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @return true, wenn Weg existiert
     */
    public static boolean search(ISimpleGraph graph, int source, int target) {

        if (source < 0 || target < 0 || source >= graph.getNodeCount()
                || target >= graph.getNodeCount())
            return false;
        if (source == target)
            return true;
        if (graph.getEdgeCount() == 0)
            return false;

        LinkedList<Integer> sucher = new LinkedList<Integer>();
        LinkedList<Integer> tester = new LinkedList<Integer>();
        sucher.add(source);
        tester.add(source);
        while (!sucher.isEmpty()) {
            int c = sucher.remove();
            if (c == target)
                return true;

            if (graph.getSuccessors(c) != null) {
                for (int i = 0; i < graph.getSuccessors(c).length; i++) {
                    int x = graph.getSuccessors(c)[i];
                    if (!tester.contains(x)) {
                        sucher.add(x);
                        tester.add(x);
                    }
                }
            }
        }
        return false;
    }
}
```


----------



## SlaterB (9. Mrz 2010)

> Jetzt ist anscheinend der Fehler das in einem bestimmten Fall true rauskommen sollte bei mir aber false ausgegeben wird.

war das nicht am Anfang auch schon so (expected:<true> but was:<false>)? 

mir fällt beim Durchschauen nichts wichtiger mehr auf, außer der Möglichkeit, dass die Zahlen beliebig hoch sein können, 
deine Bedingung
 if ([..] source >= graph.getNodeCount() || target >= graph.getNodeCount())  return false;
dann fälschlicherweise false zurückgibt, aber dabei hast du dir doch sicher was gedacht, gibt es eine Regel, dass die Nodes von 0 bis n nummeriert sind?
sonst von mir jedenfalls keine Idee, 

mit System.out.println() usw. könntest du alles herausfinden, falls das technisch erlaubt ist,
schau dir an was als Start und Ziel gegeben sind, was die Successor sind usw.


----------



## LauraHe (10. Mrz 2010)

Also der eine fehler ist jetzt weg dafür wird ein neuer angezeigt. java.lang.ArrayIndexOutOfBoundsException: 4
    at jpp.simplegraph.SimpleGraph.<init>(SimpleGraph.java:35)
    at level_1.TestBFSRequired.testSearch(TestBFSRequired.java:35)



```
package jpp.simplegraph;

/**
 * Diese Klasse implementiert das Interface ISimpleGraph.
 * 
 * @author Laura
 * 
 */
public class SimpleGraph implements ISimpleGraph {
    private double[][] matrix;
    private int knotenanzahl;
    private int kantenanzahl;

    /**
     * Konstruktor erzeugt einen Graphen mit n Knoten ohne Pfeile, wenn n
     * negativ ist, so wird ein leerer Graph erzeugt.
     * 
     * @param n
     *            Knotenanzahl
     */
    public SimpleGraph(int n) {
        if (n <= 0) {
            this.matrix = null;
            this.kantenanzahl = 0;
            this.knotenanzahl = 0;
        } else {
            this.kantenanzahl = 0;
            this.knotenanzahl = n;
            this.matrix = new double[n - 1][n - 1];
            for (int i = 0; i <= n - 1; i++) {
                for (int j = 0; j <= n - 1; j++) {
                    if (i == j) {
                        this.matrix[i][j] = 0;
                    } else
                        this.matrix[i][j] = -1;
                }

            }
        }

    }

    /**
     * Erzeugt einen Graphen anhand der Adjazenzmatrix matrix (Kopie);
     * entspricht die Adjazenzmatrix nicht den oben genannten Eigenschaften, so
     * wird ein leerer Graph erzeugt.
     * 
     * @param matrix
     *            Matrix
     */
    public SimpleGraph(double[][] matrix) {
        this.kantenanzahl = -1;
        if (matrix == null) {
            throw new NullPointerException("Matrix darf nicht null sein");
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix.length != matrix[i].length) {
                this.matrix = null;
                this.kantenanzahl = 0;
                this.knotenanzahl = 0;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][i] != 0) {
                this.matrix = null;
                this.kantenanzahl = 0;
                this.knotenanzahl = 0;
            }
            for (int j = 0; j < matrix.length; j++) {
                if (i != j) {
                    if (matrix[i][j] <= 0 && matrix[i][j] != -1) {
                        this.matrix = null;
                        this.kantenanzahl = 0;
                        this.knotenanzahl = 0;
                    }
                }
            }
        }
        if (this.kantenanzahl == -1) {
            this.kantenanzahl = 0;
            this.matrix = new double[matrix.length][matrix.length];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    this.matrix[i][j] = matrix[i][j];
                    if (matrix[i][j] > 0) {
                        this.kantenanzahl++;
                    }
                }
            }
            this.knotenanzahl = matrix.length;

        }
    }

    /**
     * Fuegt einen neuen Pfeil ein, existierende Pfeile werden ueberschrieben.
     * 
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @param cost
     *            Kosten
     * @return true wenn erfolgreich
     */
    public boolean addEdge(int source, int target, double cost) {
        if (source < 0 || target < 0 || source >= this.knotenanzahl
                || target >= this.kantenanzahl)
            return false;
        if (cost <= 0)
            return false;
        this.matrix[source][target] = cost;
        return true;
    }

    /**
     * Prueft ob ein Pfeil im Graphen existiert.
     * 
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @return Wahrheitswert
     */
    public boolean containsEdge(int source, int target) {
        if (source < 0 || target < 0 || source >= this.knotenanzahl
                || target >= this.kantenanzahl)
            return false;
        if (this.matrix[source][target] <= 0)
            return false;
        else
            return true;
    }

    /**
     * Prueft ob ein Knoten im Graphen vorhanden.
     * 
     * @param node
     *            Knoten
     * @return Wahrheitswert
     */
    public boolean containsNode(int node) {
        if (node < 0 || node >= this.knotenanzahl)
            return false;
        return true;

    }

    /**
     * Gibt die Kosten eines Pfeils zurueck.
     * 
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @return Kosten (-1.0 wenn kein Pfeil existiert)
     */
    public double getEdgeCost(int source, int target) {
        if (source < 0 || target < 0 || source >= this.knotenanzahl
                || target >= this.knotenanzahl)
            return -1;

        return this.matrix[source][target];
    }

    /**
     * Gibt die Anzahl der Pfeile des Graphen zurueck.
     * 
     * @return Pfeilanzahl
     */
    public int getEdgeCount() {
        return this.kantenanzahl;
    }

    /**
     * Gibt die Adjazenzmatrix (Kopie) des Graphen zurueck.
     * 
     * @return Adajazenzmatrix
     */
    public double[][] getMatrix() {
        return matrix;
    }

    /**
     * Gibt die Anzahl der Knoten des Graphen zurueck.
     * 
     * @return Knotenanzahl
     */
    public int getNodeCount() {
        return this.knotenanzahl;
    }

    /**
     * Gibt die Vorgaengerknoten eines Knoten in aufsteigender Reihenfolge
     * zurueck; Existiert der Knoten nicht im Graphen, so wird ein leeres Array
     * zurueck gegeben.
     * 
     * @param node
     *            Knoten
     * @return Array mit Vorgaengerknoten
     */
    public int[] getPredecessors(int node) {
        if (node < 0 || node >= this.knotenanzahl)
            return null;
        int[] vorgaengerknoten = null;
        int j = 0;

        for (int i = 0; i < this.knotenanzahl; i++) {
            if (this.matrix[i][node] > 0) {
                vorgaengerknoten[j] = i + 1;
                j++;
            }
        }
        return vorgaengerknoten;

    }

    /**
     * Gibt die Nachfolgerknoten eines Knoten in aufsteigender Reihenfolge
     * zurueck.
     * 
     * Existiert der Knoten nicht im Graphen, so wird ein leeres Array zurueck
     * gegeben.
     * 
     * @param node
     *            Knoten
     * @return Array mit Nachfolgerknoten
     */
    public int[] getSuccessors(int node) {
        if (node < 0 || node >= this.knotenanzahl)
            return null;
        int[] nachfolgerknoten = null;
        int j = 0;

        for (int i = 0; i < this.knotenanzahl; i++) {
            if (this.matrix[node][i] > 0) {
                nachfolgerknoten[j] = i + 1;
                j++;
            }
        }
        return nachfolgerknoten;
    }

    /**
     * Loescht einen Pfeil.
     * 
     * @param source
     *            Startknoten
     * @param target
     *            Zielknoten
     * @return true wenn erfolgreich
     */
    public boolean removeEdge(int source, int target) {
        if (source < 0 || target < 0 || source >= this.knotenanzahl
                || target >= this.kantenanzahl)
            return false;
        if (matrix[source][target] <= 0)
            return false;
        else
            this.matrix[source][target] = -1;
        return true;

    }

    /**
     * Setzt den Graphen anhand der Adjazenzmatrix (Kopie).
     * 
     * Entspricht die Adjazenzmatrix nicht den oben genannten Eigenschaften, so
     * wird ein leerer Graph erzeugt.
     * 
     * @param matrix
     *            Adjazenzmatrix
     */
    public void setMatrix(double[][] matrix) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                this.matrix[i][j] = matrix[i][j];
            }

        }

    }
}
```


----------



## LauraHe (10. Mrz 2010)

Also bei dem letzten Problem hab ich meinen Fehler selbst gefunden. Aber wenn mir irgendjemand sagen könnte in welchem fall bei mir false rauskommt obwohl true rauskommen sollte und warum false rauskommt wär echt super!


----------



## Don_Alfredo (10. Mrz 2010)

hi,

könntest du vielleicht bitte kurz zeigen, wo der fehler war? wir haben gerade in der berufsschule auch java, insbesondere das finden von fehlern. allerdings komm ich hier nicht auf den fehler für die arrayoutofbound exception. mir ist klar, dass es um


```
if (i == j) {
                        this.matrix[i][j] = 0;
                    } else
                        this.matrix[i][j] = -1;
                }
```
gehen muss. ich hab den verdacht, dass -1 falsch ist. kann das sein?

gruß


----------



## eRaaaa (10. Mrz 2010)

Don_Alfredo hat gesagt.:


> ich hab den verdacht, dass -1 falsch ist. kann das sein?



nein ....

/edit: ach, das bezieht sich ja auf den Code darüber..okay hab nichts gesagt


----------



## SlaterB (10. Mrz 2010)

das ist doch vollständig und simpel:

this.matrix = new double[n - 1][n - 1];
            for (int i = 0; i <= n - 1; i++) {

das Array hat eine Länge von n-1, damit sind die Indexe 0 bis n-2 erlaubt,
i läuft aber bis n-1 -> Arrayzugriff mit Index n-1 OutOfBound


-1 ist der Wert und welcher Wert in einen double geschrieben wird kann doch keine Bedeutung haben


----------

