Graphenalgorithmen

Graphen mit Kantenmarkierungen

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

w : E → A,

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

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

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

Implementierung mit Gewichtsmatrix

Eine einfache Möglichkeit zur konkreten Implementierung eines Graphen mit Kanten­gewichten besteht darin, die Kanten­gewichte w(i, j) als Einträge in einer Gewichts­matrix zu speichern.

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

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

Hierbei ist der Wert noedge eine Zahl, die nicht als Kanten­gewicht vorkommen kann, z.B. je nach Anwendung ∞ 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 über­schrieben, um einen Vergleich von double-Werten auf ungefähre Gleichheit im Rahmen von Rundungs­fehlern zu gewähr­leisten.

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]

 

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