Eine Datenstruktur für Graphen

Um Graphen zu modellieren, stehen die drei Klassen Vertex, Edge und Graph zur Verfügung.

Einen Graphen aufbauen

Der folgende Quelltext baut mithilfe der drei Klassen einen einfachen Beispielgraphen auf:

Im Quelltext ist deutlich zu sehen, dass die Knoten und Kanten des Graphen getrennt erzeugt und dem Graphen zugewiesen werden.

Graph g = new Graph();

Vertex v1 = new Vertex("1");
Vertex v2 = new Vertex("2");
Vertex v3 = new Vertex("3");

g.addVertex(v1);
g.addVertex(v2);
g.addVertex(v3);

Edge e1 = new Edge(v1,v2,5);
Edge e2 = new Edge(v1,v3,7);
Edge e3 = new Edge(v2,v3,13);

g.addEdge(e1);
g.addEdge(e2);
g.addEdge(e3);

Beispiel: Nächster Nachbar

Als exemplarische Anwendung der drei Klassen wird hier in einem gegebenem Graphen für einen gegebenen Knoten der nächstgelegene Nachbar bestimmt, d.h. die ID desjenigen Knoten, der mit dem gegebenen Knoten direkt verbunden ist und dessen zugehörige Kante das geringste Gewicht aufweist.

Dazu wird mithilfe der Methode getNeighbours() zunächst eine Liste aller Nachbarknoten erfragt. Diese Liste wird nun durchlaufen. Dabei wird jeweils überprüft, ob das bisherige minimale Kantengewicht von der aktuellen Kante (vom Ausgangsknoten zum Nchbarknoten) unterboten werden kann.

public String findeNaechstenNachbarn(String ID) {

    Vertex startnode = g.getVertex(ID);
    if (startnode==null) { return "Knoten unbekannt"; }
    else {
        List<Vertex> l = g.getNeighbours(startnode);
        l.toFirst();
        String next_neighbour = "kein Nachbar";
        double min = 10000.0;
        while (l.hasAccess()) {
            Vertex node = l.getContent();
            Edge e = g.getEdge(startnode,node);
            double distance = e.getWeight();
            if (distance<min) {
                min = distance;
                next_neighbour = node.getID();
            }
            l.next();
        }
        return next_neighbour;
    }
}

results matching ""

    No results matching ""