Graphenalgorithmen

Graphen mit Knotenmarkierungen

 aufwärts

Viele Probleme lassen sich mithilfe von Graphen modellieren, deren Knoten z.B. mit Zahlenwerten markiert sind.

Definition:  Sei G = (V, E) ein Graph und A eine Menge. Eine Abbildung

m : V Pfeil nach rechts A,

die jedem Knoten v Element V ein Element m(vElement A zuordnet, heißt Knoten­markierung.

Wir leiten Implementierungen von Graphen mit Knotenmarkierungen von der Klasse DirectedGraph bzw. von der Klasse UndirectedGraph ab.

Marker

In vielen Graphenalgorithmen werden im Verlauf der Berechnungen gewisse Knoten markiert, z.B. um sie als schon besucht zu kennzeichnen. Um derartige temporäre Markierungen anzubringen, verwenden wir die Klasse Marker.

Wir verwenden die Klasse Marker ebenfalls, um Graphen mit Knotenmarkierungen darzustellen.

Es folgt eine entsprechende Implementierung in der Klasse NodeWeightedGraph, die hier von der Klasse DirectedGraph abgeleitet ist. Hierbei wird ein Marker mit Typ-Parameter Double eingesetzt.

// modelliert einen Graphen mit Knotenmarkierungen vom Typ Double
public class NodeWeightedGraph extends DirectedGraph
{
    private Marker<Double> a;    // Knotenmarkierungen

    public NodeWeightedGraph(int n)
    {
        super(n);
        a=new Marker<Double>(n, 0.0);
    }

    public void setEdge(int i, int j)
    {
        setWeight(i, j, true);
    }

    public void setNodeWeight(int i, double x)
    {
        a.setMark(i, x);
    }

    // addiert x zum aktuellen Knotengewicht
    public void addNodeWeight(int i, double x)
    {
        a.setMark(i, a.getMark(i)+x);
    }

    public double getNodeWeight(int i)
    {
        return a.getMark(i);
    }

    // bildet die Summe aller Knoten, die in einer Liste p angegeben werden
    public double sumNodeWeight(ArrayList<Integer> p)
    {
        double sum=0;
        Iterator<Integer> it=p.iterator();
        while (it.hasNext())
            sum+=getNodeWeight(it.next());
        return sum;
    }

    @Override
    public String toString()
    {
        int i;
        String s="";
        for (i=0; i<n; i++)
            s+=i+" "+a.getMark(i)+"\n";
        return s+super.toString();
    }

}

 

 

 

Weiter mit:   [Gerichteter Baum mit Kantenmarkierung]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 28.02.2017   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