Graphenalgorithmen

Gerichteter Baum mit Kantenmarkierung

 aufwärts

In vielen Graphenalgorithmen 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 erforderliche Datenstruktur sowie entsprechende Methoden zur Verfügung.

Implementierung

Ein gerichteter Baum wird durch eine Knotenmarkierung 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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 17.09.2012   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik