Benutzer:Sandrine

Aus SibiWiki
Zur Navigation springen Zur Suche springen

Strategie:

Man entfernt alle markierten Nodes aus der NachbarListe und durchläuft diese Liste und guckt, welches die kürzeste Kante zu pNode hat.

public GraphNode gibNaechstenNachbarn(GraphWithViewer gwv, GraphNode pNode) { GraphNode ergebnis = null; double gewicht; List nachbarListe = gwv.getNeighbours(pNode); // alle Nachbarn werden in die NachbarListe eingefügt nachbarListe.toFirst(); while(nachbarListe.hasAccess()) { GraphNode aktKn=(GraphNode)nachbarListe.getObject(); if(aktKn.isMarked()) // wenn ein Objekt der NachbarListe markiert ist, dann wird es entfernt. { nachbarListe.remove(); } else{ nachbarListe.next(); } } nachbarListe.toFirst(); // das erste Objekt der nachbarListe wird als Ergebnis deklariert // und das Gewicht der Kante von diesem Objekt zu pNode als Gewicht ergebnis = (GraphNode)nachbarListe.getObject(); gewicht = gwv.getEdgeWeight(pNode, ergebnis); nachbarListe.next(); while(nachbarListe.hasAccess()) { GraphNode aktuellerNode = (GraphNode)nachbarListe.getObject(); double aktuellesGewicht = gwv.getEdgeWeight(pNode, aktuellerNode); if(aktuellesGewicht<gewicht) // wenn ein Gewicht einer Kante von einem Nachbarn zu pNode kleiner ist als das Gewicht, // dann wird dieses das neue Gewicht und der Nachbar wird das Ergebnis { ergebnis = aktuellerNode; gewicht = gwv.getEdgeWeight(pNode, aktuellerNode); } nachbarListe.next(); } return ergebnis; }