Graphenalgorithmen

Graphen mit Kantenmarkierungen

 aufwärts

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

w : E Pfeil nach rechts A,

die jeder Kante e Element E ein Element w(eElement A zuordnet, heißt Kanten­markierung.

Wenn die Markierungen der Kanten reelle Zahlen sind, d.h. wenn A = reelle Zahlen ist, sprechen wir auch von Kantengewichten.

Wir leiten Implementierungen von Graphen mit Kantengewichten von der abstrakten Klasse Graph mit entsprechendem Typ-Parameter Double ab.

Implementierung mit Gewichtsmatrix

Eine einfache Möglichkeit zur konkreten Implementierung eines Graphen mit Kantengewichten besteht darin, die Kantengewichte w(i, j) als Einträge in einer Gewichtsmatrix zu speichern.

Definition:  Eine Gewichtsmatrix eines Graphen ist eine n × n-Matrix A, für die gilt

ai,j  =   geschweifte Klammer
w(i, j)    falls (i, jElement E
noedge    sonst

Hierbei ist der Wert noedge eine Zahl, die nicht als Kantengewicht vorkommen kann, z.B. je nach Anwendung unendlich oder 0.

Es folgt eine entsprechende Implementierung in der Klasse WeightedDirectedGraph, die von der abstrakten Klasse Graph mit Typ-Parameter Double abgeleitet ist.

// modelliert einen Graphen mit Kantengewichten vom Typ Double
public class WeightedGraph extends Graph<Double>
{
    private double[][] a;

    // Anzahl der Knoten n; nicht vorhandene Kanten werden
    // durch das Gewicht noedge dargestellt
    public WeightedGraph(int n, double noedge)
    {
        super(n, noedge);
        a=new double[n][n];
        initialize();
    }

    public WeightedGraph(int n)
    {
        this(n, Double.POSITIVE_INFINITY);
    }

    @Override
    public void setWeight(int i, int j, Double w)
    {
        a[i][j]=w;
    }

    // ermöglicht die Übergabe von int-Kantengewichten
    public void setWeight(int i, int j, double w)
    {
        setWeight(i, j, (Double) w);
    }

    public void addWeight(int i, int j, double w)
    {
        a[i][j]+=w;
    }

    @Override
    public Double getWeight(int i, int j)
    {
        return a[i][j];
    }

    // überschreibt die Methode der Oberklasse Graph:
    // Vergleich von double-Werten auf annähernde Gleichheit
    @Override
    public boolean isEdge(int i, int j)
    {
        return Math.abs(getWeight(i, j)-noedge)>1e-14;
    }

}

 

Die zweite Version der Methode setWeight ist erforderlich, damit auch int-Zahlen als Parameter übergeben werden können; diese werden nämlich automatisch in double umgewandelt, jedoch nicht in Double.

Die Methode isEdge der Oberklasse Graph wird überschrieben, um einen Vergleich von double-Werten auf ungefähre Gleichheit im Rahmen von Rundungsfehlern zu gewährleisten.

Ungerichteter Graph mit Kantengewichten

Wir fassen ungerichtete Graphen als gerichtete Graphen auf, bei denen die Kanten stets in beide Richtungen verlaufen.

 

// modelliert einen ungerichteten Graphen mit Kantengewichten vom Typ Double
public class WeightedUndirectedGraph extends WeightedGraph
{
    // Anzahl der Knoten n; nicht vorhandene Kanten werden
    // durch das Gewicht noedge dargestellt
    public WeightedUndirectedGraph(int n, double noedge)
    {
        super(n, noedge);
    }

    public WeightedUndirectedGraph(int n)
    {
        super(n);
    }

    @Override
    public void setWeight(int i, int j, Double w)
    {
        super.setWeight(i, j, w);
        super.setWeight(j, i, w);
    }

    @Override
    public void addWeight(int i, int j, double w)
    {
        super.addWeight(i, j, w);
        super.addWeight(j, i, w);
    }

}

 

 

Weiter mit:   [Graphen mit Knotenmarkierungen]   oder   up

 

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