Graphenalgorithmen

Implementierung von gerichteten und ungerichteten Graphen

Ein Graph G = (V, E) besteht aus einer Menge V von Knoten und einer Menge E von Kanten. Die Kanten sind Verbindungen zwischen den Knoten; sie können gerichtet oder ungerichtet sein. Graphen werden in vielen Anwendungs­gebieten zur Modellierung von Problemen verwendet.

Als Beispiel zeigt Bild 1 einen Graphen G.

 

Bild 1: Graph G 

Bild 1: Graph G

 

Die im Folgenden angegebenen Möglich­keiten zur Implementierung eines Graphen als Daten­struktur basieren auf einer abstrakten Klasse Graph, die grundlegende Daten und Methoden zur Verfügung stellt.

Implementierung mit Adjazenzmatrix

Eine einfache Möglichkeit zur konkreten Implementierung eines Graphen besteht darin, die Kanten des Graphen in Form einer Adjazenz­matrix darzustellen.

Definition:  Sei G = (V, E) ein Graph mit  V = {0, ..., n-1},  n ∈ ℕ. Die Adjazenz­matrix des Graphen ist eine boolesche n × n-Matrix A, für die gilt

Ai,j  =   geschweifte Klammer
true        falls (i, j) eine Kante ist, d.h. falls (i, j) ∈ E
false    sonst

für alle  i, j ∈ V.

Beispiel:  Adjazenz­matrix des Graphen G aus Bild 1   (leere Einträge = false, 1 = true)

    01234
0 11  
1  1  
21    
31    
4     

 

Es folgt eine entsprechende Implementierung des Graphen in der Klasse DirectedGraph, die von der abstrakten Klasse Graph mit Typ-Parameter Boolean abgeleitet ist.

public class DirectedGraph extends Graph<Boolean>
{
    private Boolean[][] a;

    // Konstruktor
    public DirectedGraph(int n)
    {
        super(n, false);
        a=new Boolean[n][n];
        initialize();
    }

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

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

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

}

 

Ungerichteter Graph

Ein ungerichteter Graph lässt sich als gerichteter Graph, dessen Kanten­relation symmetrisch ist, ansehen, also als Spezialfall eines gerichteten Graphen. Entsprechend modellieren wir ungerichtete Graphen, indem wir die Klasse UndirectedGraph von DirectedGraph ableiten und nur die Methode setWeight in der Weise über­schreiben, dass mit jeder Kante (i, j) auch die Kante (j, i) erzeugt wird.

public class UndirectedGraph extends DirectedGraph
{
    public UndirectedGraph(int n)
    {
        super(n);
    }

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

}

 

Implementierung mit Adjazenzlisten

Eine Adjazenz­liste ist eine Liste aller Knoten, zu denen von einem bestimmten Knoten aus eine Kante hinführt. Um einen Graphen darzustellen wird also für jeden seiner Knoten eine Adjazenz­liste benötigt.

Beispiel:  Der Graph G aus Bild 1 lässt sich durch folgende Adjazenz­listen seiner Knoten 0, ..., 4 darstellen:

 0  1  2 
12
20
30
4

Aus dieser Darstellung geht hervor, dass vom Knoten 0 aus Kanten zu den Knoten 1 und 2 hinführen, vom Knoten 1 aus eine Kante zum Knoten 2, vom Knoten 2 zum Knoten 0 usw.

Es bietet sich an, die Adjazenz­listen als ArrayList zu implementieren. Als NeighbourIterator kann dann der Standard-Iterator des Typs ArrayList verwendet werden.

Aufgabe 1:  Programmieren Sie eine entsprechende Implementierung des Graphen als Klasse DirectedGraph1, abgeleitet von der abstrakten Klasse Graph. Stellen Sie die Adjazenz­listen durch Objekte vom Typ ArrayList mit Typ-Parameter Integer dar. Implementieren Sie die abstrakten Methoden der abstrakten Klasse Graph.

 

Weiter mit:   [Graphen mit Kantenmarkierungen]   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