Graphenalgorithmen

Implementierung von gerichteten und ungerichteten Graphen

 aufwärts

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 Anwendungsgebieten 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öglichkeiten zur Implementierung eines Graphen als Datenstruktur 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 Adjazenzmatrix darzustellen.

Definition:  Sei G = (V, E) ein Graph mit  V = {0, ..., n-1},  n Element natürliche Zahlen. Die Adjazenzmatrix 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, jElement E
false    sonst

für alle  i, j Element V.

Beispiel:  Adjazenzmatrix 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 Kantenrelation 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 überschreiben, 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 Adjazenzliste 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 Adjazenzliste benötigt.

Beispiel:  Der Graph G aus Bild 1 lässt sich durch folgende Adjazenzlisten 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 Adjazenzlisten 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 Adjazenzlisten 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

 

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