Graphenalgorithmen

Basisklasse Graph

 aufwärts

Gegeben ist ein gerichteter oder ungerichteter Graph G = (V, E) mit V = {0, ..., n-1},  n Element natürliche Zahlen und E enthalten in V × V.

Gesucht ist nach Möglichkeiten, einen solchen Graphen in Form einer geeigneten Datenstruktur darzustellen. Dabei soll die Datenstruktur so beschaffen sein, dass Graphenalgorithmen 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 Anwendungsfälle optimale Datenstruktur 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 Kantenmarkierungen hinzukommen.

Daher werden wir die konkrete Implementierung als Datenstruktur zunächst offen lassen. Stattdessen fassen wir zunächst nur die als sicher geltenden Gemeinsamkeiten 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 Kantenmarkierungen modelliert werden.

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

w : V × V Pfeil nach rechts T,

die jedem Knotenpaar (i, j) einen Wert aus einer Menge T zuweist. Hierbei wird ein spezieller Wert noedge Element T genau allen Knotenpaaren (i, jnicht Element 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 Kantenmarkierungen 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 Kantenmarkierungen ist beispielsweise 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 unendlich, 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

 

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