Kurs:Algorithmen und Datenstrukturen/Vorlesung/DatenstrukturGraphen
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
G=(V,E)
V={1,2,3,4,5}
E={(1,2),(3,4),(5,1),(2,5),(5,4)}
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.
- Jung (http://jung.sourceforge.net)
Graph<Integer, String> g = new SparseMultigraph<Integer, String>();
g.addVertex((Integer)1);
g.addVertex((Integer)2);
g.addEdge("Edge1", 1, 2);
- Neo4j (http://www.neo4j.org)
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.