Kurs:Algorithmen und Datenstrukturen/Vorlesung/DatenstrukturGraphen

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Graphen[Bearbeiten]

In diesem Kapitel beschäftigen wir uns mit Graphen.

Definition[Bearbeiten]

Ein (gerichteter) Graph G is ein Tupel G=(V,E) mit V als der endlichen Menge der Knoten von G und als der endlichen Menge der Kanten von G. Um ein Graph als Datenstruktur zu nutzen, können sowohl Knoten als auch Kanten weitere Attribute beinhalten. Ein gerichteter Graph mit den Werten F ist ein Tupel mit (V,E) als Graph, als Wert des Knotens und als Wert der Kante .

Beispiel[Bearbeiten]

Graph Beispiel

G=(V,E)

V={1,2,3,4,5}

E={(1,2),(3,4),(5,1),(2,5),(5,4)}

Graph Beispiel 2

F=(V,E,)

V={1,2,3,4,5}

E={(1,2),(3,4),(5,1),(2,5),(5,4)}

(1)="Anna", (2)="Carl",...,(1,2)="kennt",...

Graphen als Datenstruktur[Bearbeiten]

Knoten und Kanten können auch komplexere Werte enthalten, wie beispielsweise mehrere Werte oder Arrays. Der Einfachheit halber identifizieren wir(in diesem Kurs) den Wert eines Knotens mit dem Knoten selber und nutzen meist natürliche Zahlen als Knotenbezeichner:

  • für alle

Listen und Bäume sind Spezialfälle von Graphen.

Anwendungen[Bearbeiten]

Graphen werden für Verbindungsnetzwerke wie Bahnnetze, Flugverbindungen oder Strassenkarten benutzt. Aber auch für Verweise wie WWW, Literaturverweise, Wikipedia, symbolische Links und vieles mehr. Auch bei technischen Modellen kommen Graphen zum Einsatz, beispielsweise bei Platinen-Layout, finite Elemente und Computergrafik. In Sozialen Netzwerken und Argumentationsgraphen kommen Graphen auch zum Einsatz.

Atomare Operationen auf Graphen[Bearbeiten]

Zu dem Operationen zählen lesen mit

  • Adj(x,y): Sind Knoten x und y benachbart?

Adj(1,2)=true, Adj(4,5)=false

  • Suc(x): Menge der Nachfolger von x

Suc(1)={2}, Suc(5)={1,4}

  • Bei Graphen mit expliziten Werten: Wert eines Knotens/Kante lesen

und schreiben mit

  • Add(x)/Del(x): Knoten x hinzufügen/löschen
  • Add(x,y)/Del(x,y): Kante (x,y) hinzufügen/löschen

Typische Problemstellungen[Bearbeiten]

Zu den typischen Problemstellungen zählen die Traversierung, die Findung des kürzesten Wegs, die Graphfärbung, das Flussproblem, die Verbundheit und das Graphclustering (Community Detection).

Graphen in Java[Bearbeiten]

In Java gibt es keine hauseigene Graphenimplementierung, allerdings gibt es diverse Pakete für verschiedene Anwendungen.

Graph<Integer, String> g = new SparseMultigraph<Integer, String>();g.addVertex((Integer)1);g.addVertex((Integer)2);g.addEdge("Edge1", 1, 2);
GraphDatabaseService= new 
GraphDatabaseFactory().newEmbeddedDatabase(PATH);Transaction tx = graphDb.beginTx();try{Node firstNode = graphDb.createNode();Node secondNode = graphDb.createNode();Relationship relationship = firstNode.createRelationshipTo(secondNode,
 );tx.success();}finally{tx.finish();}

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 16 zu finden.

Vorheriges Thema.jpg Discussion Nächstes Kapitel .jpg