Stack over flow bei rekursiver Tiefensuche

[4ND1]

Wir haben folgendes Porblem

Unsere rekursive Tiefensuche erleidet einen Stack over flow, trotz langer bemühungen können wir leider keinen fehler finden

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.util.ArrayList;
import java.util.Stack;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class AdjazenzListe {

    KnotenListe[] list;
    Knoten[] knotenArray;

    public void knotenEinlesen(String dateiname) throws IOException {

        BufferedReader knotencsv = null;
        String knoten;
        String[] part;
        knotenArray = new Knoten[0];
        Knoten[] kArrayNeu;

        try {
            knotencsv = new BufferedReader(new FileReader(dateiname));
            knotencsv.readLine();

            while ((knoten = knotencsv.readLine()) != null) {

                part = knoten.split(";");

                int nodeID = Integer.parseInt(part[0]);
                double lat = Double.parseDouble(part[1]);
                double lon = Double.parseDouble(part[2]);

                Knoten knotenNeu = new Knoten(nodeID, lat, lon);

                kArrayNeu = new Knoten[knotenArray.length + 1];

                for (int i = 0; i < knotenArray.length; i++)
                    kArrayNeu[i] = knotenArray[i];

                kArrayNeu[knotenArray.length] = knotenNeu;
                knotenArray = kArrayNeu;
            }
            knotencsv.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("Knoten eingelesen!");
        return;
    }

    public KnotenListe[] kantenEinlesen(String dateiname) throws IOException {

        BufferedReader kantencsv = null;
        String kante;
        String[] part;
        String name;
        list = new KnotenListe[knotenArray.length];

        for (int i = 0; i < knotenArray.length; i++)
            list[i] = new KnotenListe();

        try {

            kantencsv = new BufferedReader(new FileReader(dateiname));
            kantencsv.readLine();

            while ((kante = kantencsv.readLine()) != null) {

                part = kante.split(";");
                int lineID = Integer.parseInt(part[0]);
                int node1 = Integer.parseInt(part[1]);
                int node2 = Integer.parseInt(part[2]);
                String type = part[3];

                if (part.length == 5) {
                    name = part[4];
                } else {
                    name = null;
                }

                Kanten kanteNeu = new Kanten(lineID, node1, node2, type, name);
                int n1 = kanteNeu.getNode1() - 1;
                int n2 = kanteNeu.getNode2() - 1;
                list[n1].fuegeHintenAn(knotenArray[n2]);
                list[n2].fuegeHintenAn(knotenArray[n1]);

            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("Kanten eingelesen!");
        return list;
    }

    ArrayList<Knoten> arrayList = new ArrayList<Knoten>();

    // Fuer Adjazenzlisten abgeanderte Tiefensuche-Methode aus der Vorlesung
    public void tiefenSuche_rekursiv(Knoten aktuell) {

        aktuell.setBesucht(true);
        int nID = aktuell.getNodeID() - 1;
        KnotenElement element = list[nID].getKopf();

        while (element != null) {
        //    while (arrayList.size() < 17207) {
          
            if (element.getWert().getBesucht() == false)
                tiefenSuche_rekursiv(element.getWert());
          
          
            element = element.getWeiter();
        }
  
        arrayList.add(aktuell);
    }

    public void tiefenSuche() {
      
        int nummer = 1;

        for (int i = 0; i < knotenArray.length; i++) {
            knotenArray[i].setBesucht(false);
        }
      
        for (int j = 0; j < knotenArray.length; j++) {
            if (knotenArray[j].getBesucht() == false) {

                arrayList = new ArrayList<Knoten>();
                tiefenSuche_rekursiv(knotenArray[j]);
              
                if (arrayList.size() > 1) {
                    try {
                        String name = " " + nummer + ".csv";
                        BufferedWriter bw = new BufferedWriter(new FileWriter(name));
                        bw.write("nodeID;lat;lon");
                        bw.newLine();
                      
                        for (int k = 0; k < arrayList.size(); k++) {
                            bw.write(arrayList.get(k).getId() + ";" + arrayList.get(k).getLat() + ";"
                                    + arrayList.get(k).getLon());
                            bw.newLine();
                        }
                        bw.close();
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                    nummer = nummer + 1;
                }
            }
        }
        System.out.println("Tiefensuche abgeschlossen!");

    }
}

 

[JCODA]

Wenn du eine Klasse mit main-Methode und passender Datei * zum Einlesen bereitstellst, probier ich es aus und versuche mich mal dran, den Fehler zu finden.

*Edit: und alle weiteren benötigten Klassen.

 

[4ND1]

Ich habe dir soweit alles wichtige in die Zip datei rein

 

[JCODA]

Okay, ich habs gerade drüber geschaut. Sehe keinen Fehler.
Wenn man das Programm mit dem Parameter -Xss4m laufen lässt, läuft es auch ohne Fehler durch. (Damit vergrößert man die Stacksize.)
Ich vermute bei solch großen Graphen ist Rekursion keine Lösung. Hier sollte man wohl mit einem Stack arbeiten.

 

[4ND1]

Danke, wie kann ich das programm mit dem parameter laufen lassen?

Nachtrag: haben es gerade selber geschafft danke!!!

 

[JCODA]

Wenn du Eclipse verwendest, unter Run-Configurations:
http://puu.sh/pOLVu/536409c365.png
z.B. in dem man Run -> Run Configurations aufruft.

EDIT: Dennoch ist dies natürlich keine "elegante" Lösung!