Graphenalgorithmen

Gerichteter Baum mit Kantenmarkierung

In vielen Graphen­algorithmen werden gerichtete Bäume erzeugt, so etwa bei der Breitensuche, bei der Berechnung eines minimalen Spannbaums oder bei der Berechnung der kürzesten Wege in einem Graphen.

Als Grundlage hierfür dient die folgende Klasse RootedTree; diese stellt die erforder­liche Daten­struktur sowie entsprechende Methoden zur Verfügung.

Implementierung

Ein gerichteter Baum wird durch eine Knoten­markierung repräsentiert, die jedem Knoten seinen eindeutig bestimmten Vorgänger zuordnet. Der Vorgänger der Wurzel ist der nicht vorhandene Knoten -1, denn die Wurzel des Baums hat keinen Vorgänger.

Wir benutzen Marker, um zu jedem Knoten den Vorgänger zu speichern, ferner auch um die Entfernung des Knotens, z.B. zum Vorgänger, zu speichern. Ein weiterer Marker dient dazu, während der Berechnung des Baums diejenigen Knoten zu kennzeichnen, die schon zum Baum hinzugehören.

 

// repräsentiert einen gerichteten Baum mit Wurzel und Kantengewichtungen
public class RootedTree
{
    protected int n;
    protected Marker<Integer> pred;   // Vorgänger im Baum
    protected Marker<Double> dist;    // Abstand (z.B. zum Vorgänger)
    protected BooleanMarker tree;     // Zugehörigkeit zum schon berechneten Baum

    public RootedTree(int n_)
    {
        n=n_;
        pred=new Marker<Integer>(n, -1);
        dist=new Marker<Double>(n, Double.POSITIVE_INFINITY);
        tree=new BooleanMarker(n);
    }

    // legt die Entfernung des Knotens v zum Vorgänger fest
    public void setDistance(int v, double w)
    {
        dist.setMark(v, w);
    }

    // liefert die Entfernung des Knotens v zum Vorgänger
    public double getDistance(int v)
    {
        return dist.getMark(v);
    }

    // legt den Vorgänger des Knotens v im minimalen Spannbaum fest
    public void setPredecessor(int v, int u)
    {
        pred.setMark(v, u);
    }

    // liefert den Vorgänger des Knotens v im minimalen Spannbaum
    public int getPredecessor(int v)
    {
        return pred.getMark(v);
    }

    // fügt Knoten v zum Baum hinzu
    public void toTree(int v)
    {
        tree.mark(v);
    }

    // true, wenn Knoten v zum Baum gehört
    public boolean inTree(int v)
    {
        return tree.isMarked(v);
    }

    // true, wenn Knoten v einen Vorgänger hat
    public boolean hasPredecessor(int v)
    {
        return getPredecessor(v)!=-1;
    }

    // liefert das Gesamtgewicht des Baums
    public double getWeight()
    {
        double sum=0;
        for (int v=0; v<n; v++)
            sum+=getDistance(v);
        return sum;
    }

    // liefert die Folge der Knoten vom
    // Startknoten zum Knoten v im Baum
    public ArrayList<Integer> getPathTo(int v)
    {
        ArrayList<Integer> p=new ArrayList<Integer>();
        while (v!=-1)
        {
            p.add(0, v);
            v=getPredecessor(v);
        }
        return p;
    }

    // gibt den Baum als Graphen zurück
    public WeightedUndirectedGraph getTree()
    {
        WeightedUndirectedGraph t=new WeightedUndirectedGraph(n);
        for (int v=0; v<n; v++)
            if (hasPredecessor(v))
                t.setWeight(getPredecessor(v), v, getDistance(v));
        return t;
    }

}    // end class RootedTree

 

 

Weiter mit:   [up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 17.09.2012   Updated: 20.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden