rekursive Tiefensuche in einem Graphen

[Kampfzwereg]

Hallo,

ich soll einen rekursiven Tiefensuche programmieren.
Mein Programm kann folgendes:

-Mittels eines Buttons kann ich GraphNodes in meinen Graphen einfügen
-Mittels eines weiteren Buttons kann ich zwischen diesen Kanten in den Graphen einfügen
-jetzt kann er mit der Methode wegsucheIterativ den kürzesten Weg zwischen zwei Knoten Suchen.

Problem: er sagt mir immer, dass der Graph nicht zusammenhängend ist. Das heißt, dass bei der Erstellung der Buttons was schief geht. Ich weiß aber nicht was -.-'

Wär cool wenn ihr mir dabei helfen könnt, muss das dringend feritg kriegen :-]

Gruß Kampfzwereg

private void jBknotenActionPerformed(java.awt.event.ActionEvent evt) {                                         
       myGraph.addNode(new GraphNode(jTFname.getText()));
       anzahlKnoten++;
       System.out.println("Knoten hinzugefügt");       
    } 

private void jBkanteActionPerformed(java.awt.event.ActionEvent evt) 
{ 
        if(myGraph.hasNode(jTFvon.getText()) && myGraph.hasNode(jTFnach.getText()))
        {
            myGraph.addEdge(myGraph.getNode(jTFvon.getText()), myGraph.getNode(jTFnach.getText()), Integer.parseInt(jTFgewicht.getText()));
            System.out.println("Kante hinzugefügt");
        }
  }    

private void jBwegActionPerformed(java.awt.event.ActionEvent evt) {                                      
       if(myGraph.hasNode(jTFstart.getText()) && myGraph.hasNode(jTFziel.getText()))
       {
           GraphNode von = new GraphNode(jTFstart.getText());
           GraphNode bis = new GraphNode(jTFziel.getText());
           wegsucheIterativ(von, bis);
          
       } 

public void wegsucheIterativ(GraphNode pStart, GraphNode pZiel)
  {
    
    myGraph.resetMarks();
    Stack myStack = new Stack();
    GraphNode aktuell = pStart;
    jTAweg.setText("");
    if(aktuell!=null)
    {
      myStack.push(aktuell);
      aktuell.mark();
      jTAweg.append("Startknoten "+aktuell.getName()+"\n");
    }
    else
    {
      jTAweg.append("Es gibt keinen Startknoten\n");
    }
    
    while(!myGraph.allNodesMarked()&& !myStack.isEmpty())
    {
      List nachbarn = myGraph.getNeighbours(aktuell);
      nachbarn.toFirst();
      boolean wegGefunden = false;
      while(!wegGefunden && nachbarn.hasAccess())
      {
        if(!((GraphNode)(nachbarn.getObject())).isMarked())
        {
          if(aktuell !=null && (GraphNode)(nachbarn.getObject())!=null)
          {
            jTAweg.append("--> "+aktuell.getName()+" --> "+((GraphNode)(nachbarn.getObject())).getName()+"\n");
          }
          aktuell=(GraphNode)(nachbarn.getObject());
          myStack.push(aktuell);
          aktuell.mark();
          wegGefunden =true;
        }
        nachbarn.next();
      }
      if(pZiel!=null&&aktuell.getName()==pZiel.getName())
      {
        myStack=new Stack();
        wegGefunden =true;
        jTAweg.append("Zielknoten : "+pZiel.getName());
      }
      if(!wegGefunden )
      {
        myStack.pop();
        aktuell=(GraphNode)(myStack.top());
        if(aktuell!=null)
        {
          jTAweg.append(aktuell.getName()+"\n <-- " +"\n");
        }
      }
    }
    if(!myGraph.allNodesMarked() && pStart != null)
    {
      jTAweg.append("Es liegt ein nicht zusammenhängender Graph vor\n");
    }
  }

 

[SlaterB]

wieso erstellt jBwegActionPerformed() neue GraphNodes?
kann nicht wie bei jBkanteActionPerformed() die Nodes aus myGraph geladen werden?

ob das ein Problem ist, ist freilich nicht zu erkennen,
> myGraph.getNeighbours(aktuell)
liefert vielleicht die richtigen Namen anhand des Textes, oder auch nicht

du hast mit System.out.println() oder Debugger alle Möglichkeiten der Welt, das (und andere Details)
in Erfahrung zu bringen, statt nur auf das Endergebnis 'hat nicht geklappt' zu schauen..

ok, paar mehr Ausgaben sind dabei, aber es geht immer mehr
logge was in myGraph passiert, liste dort alle Kanten auf wenn an einer bestimmten Stelle nicht gefunden wird,
poste diesen Code

 

[Kampfzwereg]

wieso erstellt jBwegActionPerformed() neue GraphNodes?
kann nicht wie bei jBkanteActionPerformed() die Nodes aus myGraph geladen werden?

Ich idiot das habe ich komplett übersehen...ich probiers gleich mal aus .

 

[Kampfzwereg]

alles klar es funktioniert. Nur nochmal fürs Protokoll:

er findet nix, da man nach neu erstellten Knoten sucht, die keine zugewiesenen Nachbarknoten haben. Deswegen wird der Graph als nicht zusammenhängend angegeben.

Wenn das geklärt ist hätte ich jedohc noch eine Kleine andere Frage. Einen Graphen kann man ja in einer Adjazenzmatrix anzeigen Lassen. Da habe ich mit einer Tabelle verwirklicht. Jedoch macht er nicht das, was er machen soll. Nach jedem einfügen soll er die Adjazenzmatrix aktualisieren und die Gewichte der Kanten eintragen. 0 bedeutet keinen Kante. Das macht er jedoch nicht wirklich

hier ist eine Methode zum aktualisieren einer solchen MAtrix. Jedoch wird immer überall 0 angezeigt.
Weiß du oder jmd ander vllt warum?

public void updateMatrix()
    {
       List knoten = myGraph.getNodes(); 
       for(int i = 0; i< anzahlKnoten; i++)
       {
           for(int j=1 ; j< anzahlKnoten+1;j++)
           {
               
               List nachbarn = myGraph.getNeighbours((GraphNode)knoten.getObject());
               if(nachbarn.hasAccess())
               {
                   jT1.setValueAt(""+myGraph.getEdgeWeight((GraphNode)knoten.getObject(), (GraphNode)nachbarn.getObject()), i, j);
               }
               else
               {
                   jT1.setValueAt(""+0, i, j);
               }                  
               
               knoten.next();
           }
           
       }
         
    }

 

[SlaterB]

List ist eine reichlich bekannte bekanntes Interface in Java, vom Java-Block auch mit Link hinterlegt,
bei dir aber anscheinend was anderes,

wie genau soll da eigentlich der Ablauf sein, die Liste aller Nodes wird einmal geladen und
dann per Doppelschleife ca anzahlKnoten^2 oft mit next() durchlaufen, gibt es da einen Kreis dass wieder zum Anfang zurückgekehrt wird?

dazu wird ziemlich oft nachbarn abfragt, aber doch immer nur das erste Objekt aus dieser Liste, da kein next() dort erfolgt?
mit System.out.println() könntest du auch dort genauer verfolgen, was verglichen wird,

wozu aber wohl wenn man einen Dummen im Forum fragen kann..

normalerweise nutzt man i/j um gezielt Knoten i und Knoten j aus der Gesamtliste zu holen und zu entscheiden ob dazwischen eine Kante besteht

etwas mehr Richtung deine Version empfehle ich,
knoten.next(); in die äußere Schleife zu lesen, also nur i mal, die Liste knoten einmal komplett zu durchlaufen,
für jeden dieser Nodes dann die Nachbarliste holen (auch nur i mal in der äußeren Schleife) und diese durchlaufen,
da es wohl kaum jedesmal anzahlKnoten Nodes in der Nachbarliste sein werden fällt die j-Schleife weg,
dafür auf konventionellen Weg die Nachbarliste durchlaufen, dann müsstest du für vorhandene Nachbarn aber berechnen, welches j dazu gehört..

 

[Kampfzwereg]

weiß du denn was eine adjazenzmatrix ist? der sinn ist ja, die jeweilige verbindung eines Knotens zu allen anderen darzustellen.

stimmt dann müsste es ja so gehen, dass ich mir von jedem Knoten einmal die nachbarliste hole und diese komplett durchlaufe und in die tabele schreibe , oder ?

 

[SlaterB]

was man in eine Zeile schreiben kann, stimmt recht häufig, ohne viel zu bedeuten,
muss nur korrekt gemacht werden