Graphenalgorithmen

Basisklasse Graph

Gegeben ist ein gerichteter oder ungerichteter Graph G = (V, E) mit V = {0, ..., n-1},  n ∈ ℕ und E ⊆ V × V.

Gesucht ist nach Möglich­keiten, einen solchen Graphen in Form einer geeigneten Daten­struktur darzustellen. Dabei soll die Daten­struktur so beschaffen sein, dass Graphen­algorithmen effizient darauf zugreifen können, z.B. dass sich alle Knoten, die zu einem bestimmten Knoten benachbart sind, effizient durchlaufen lassen.

Es stellt sich heraus, dass es schwierig ist, eine für alle Anwendungs­fälle optimale Daten­struktur zu finden. Es gibt Graphen mit vielen Kanten oder wenigen Kanten, spezielle Graphen wie Gitter oder Bäume, gerichtete und ungerichtete Graphen, und später werden auch noch Graphen mit Kanten­markierungen hinzukommen.

Daher werden wir die konkrete Implementierung als Daten­struktur zunächst offen lassen. Stattdessen fassen wir zunächst nur die als sicher geltenden Gemeinsam­keiten aller dieser konkreten Implementierungen in Form einer abstrakten Klasse Graph zusammen.

Abstrakte Klasse Graph

Ähnlich wie ein Interface legt eine abstrakte Klasse abstrakte Methoden fest, die in allen konkreten Klassen, die von der abstrakten Klasse abgeleitet sind, implementiert sein müssen. Eine abstrakte Klasse kann aber zusätzlich auch Attribute und bereits implementierte Methoden enthalten. Von einer abstrakten Klasse können keine Objekte angelegt werden, sondern nur von konkreten Klassen, die von der abstrakten Klasse abgeleitet sind. Die folgende abstrakte Klasse Graph dient als Grundgerüst für konkrete Klassen, mit denen sowohl gerichtete als auch ungerichtete Graphen sowie ferner Graphen mit Kanten­markierungen modelliert werden.

Um diese Einheitlich­keit zu erzielen, modellieren wir die Kantenmenge E eines Graphen G = (V, E) als Abbildung

w : V × V → T,

die jedem Knotenpaar (i, j) einen Wert aus einer Menge T zuweist. Hierbei wird ein spezieller Wert noedge ∈ T genau allen Knotenpaaren (i, j) ∉ E zugewiesen. Kanten und Nicht-Kanten sind also mit Werten aus T markiert, und Nicht-Kanten sind daran zu erkennen, dass sie mit dem speziellen Wert noedge markiert sind.

In der Implementierung wird die Menge T der Klasse alsTyp-Parameter Type übergeben. Bei einem Graphen ohne Kanten­markierungen ist T = {false, true} = Boolean. Der spezielle Wert noedge, mit dem Nicht-Kanten markiert werden, ist gleich false. Umgekehrt bedeutet w(u, v) = true, dass (i, j) eine Kante ist.

Bei einem Graphen mit Kanten­markierungen ist beispiels­weise T = Double, bei allen Kanten entspricht w(i, j) der jeweiligen Markierung (dem "Gewicht") der Kante, und alle Nicht-Kanten (i, j) sind mit noedge markiert. Der Wert von noedge, meist ∞, aber gelegentlich auch 0 oder ein anderer Wert, wird in der konkreten, von der abstrakten Klasse Graph abgeleiteten Klasse festgelegt.

Es folgt die abstrakte Klasse Graph.

// abstrakte Klasse zur Modellierung eines Graphen;
// konkrete Implementierung mit Adjazenzmatrix oder
// mit Adjazenzlisten und ggf. mit Kantengewichtung
public abstract class Graph<Type>
{
    protected int n;
    public Type noedge;

    public Graph(int n_, Type noedge_)
    {
        n=n_;
        noedge=noedge_;
    }

    // gibt die Anzahl der Knoten zurück
    public int getSize()
    {
        return n;
    }

    // löscht alle Kanten
    protected void initialize()
    {
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                deleteEdge(i, j);
    }

    // true, wenn (i, j) eine Kante ist
    public boolean isEdge(int i, int j)
    {
        return !getWeight(i, j).equals(noedge);
    }

    // löscht die Kante (i, j)
    public void deleteEdge(int i, int j)
    {
        setWeight(i, j, noedge);
    }

    // liefert die Markierung w(i, j)
    public abstract Type getWeight(int i, int j);

    // setzt w(i, j)=x
    public abstract void setWeight(int i, int j, Type x);

    // iteriert über alle Nachbarn des Knotens i
    public Iterator<Integer> getNeighbourIterator(int i)
    {
        return new NeighbourIterator(this, i);
    }

    @Override
    public String toString()
    {
        Iterator<Integer> ni;
        String s="\n";
        for (int i=0; i<n; i++ )
        {
            s+=i+" -> ";
            ni=getNeighbourIterator(i);
            while (ni.hasNext())
                s+=ni.next()+" ";
            s+="\n";
        }
        return s;
    }

}    // end class Graph

Mit der Methode deleteEdge(i, j) wird der Kante (i, j) die Markierung noedge zugewiesen, hierdurch wird sie gelöscht. Die abstrakten Methoden setWeight und getWeight sind dazu gedacht, einem Paar von Knoten (i, j) die Markierung (das "Gewicht") w(i, j) zuzuweisen bzw. es abzurufen.

Für das Durchlaufen aller derjenigen Knoten, zu denen von einem bestimmten Knoten aus eine Kante hinführt, wird ein NeighbourIterator verwendet. Die Methode getNeighbourIterator gibt einen solchen Iterator zurück.

 

Weiter mit:   [Gerichteter und ungerichteter Graph]   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