Graph
Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert.
Die mathematischen Abstraktionen der Objekte werden dabei Knoten des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten.
Ein Graph kann entweder in als Graph, in einer Adjazenzliste oder in einer Adjazenzmatrix dargestellt werden.
Schnittstellenbeschreibung
TODO: Erklärungen zur Schnittstelle
Traversierungen von Graphen
Wie bei Bäumen gibt es auch bei Graphen viele Anwendungen, in denen ein Graph knotenweise durchlaufen werden muss. Die Traversierungsverfahren ähneln denen bei Bäumen, berücksichtigen allerdings noch die speziellen Gegebenheiten von Graphen, nämlich:
- Graphenknoten können mehr als zwei Nachbarn haben
- Graphen können Querverbindungen und "Kreise" enthalten
Tiefendurchlauf (DFS)
Der Tiefendurchlauf durch einen Graphen funktioniert rekursiv und entspricht der Preorder-Traversierung eines Baumes.
public List erreichbareNodes(Graph pGraph, GraphNode pNode){
List knoten = new List();
pNode.mark();
//Alle Nachbarn des Startknoten holen
List h = pGraph.getNeighbours(pNode);
//Nachbarn mit for-Schleife durchlaufen
for(h.toFirst(); h.hasAccess(); h.next()){
GraphNode curNode = (GraphNode)h.getObject();
//Wenn der aktuelle Nachbar nicht markiert ist, also noch nicht abgelaufen wurde,
//zur Liste hinzufügen und auch seine Nachbarn durch den rekursiven Aufruf ablaufen.
if( !curNode.isMarked() ){
knoten.append(curNode);
curNode.mark();
//Rekursiver Aufruf
knoten.concat(erreichbareNodes(pGraph, curNode));
}
}
return knoten;
}
Breitendurchlauf (BFS)
TODO: Erklärungen zum Breitendurchlauf
TODO: gut kommentierter Quellcode des Breitendurchlaufs
Kürzeste Wege in Graphen: Der Dijkstra-Algorithmus
Idee
TODO: Erklärungen zu Dijkstra (besondere Schnittstelle erklären, Strategie erklären, Besonderheiten,...)
Implementierung
TODO: kommmentieren!
public class DijkstraAlgorithmus {
GraphWithViewer map;
ListWithViewer gelbeListe;
public void initMap(){
map = new GraphWithViewer();
DijkstraGraphNode kiel = new DijkstraGraphNode("Kiel");
map.addNode(kiel);
DijkstraGraphNode luebeck = new DijkstraGraphNode("Luebeck");
map.addNode(luebeck);
DijkstraGraphNode hamburg = new DijkstraGraphNode("Hamburg");
map.addNode(hamburg);
DijkstraGraphNode berlin = new DijkstraGraphNode("Berlin");
map.addNode(berlin);
DijkstraGraphNode bremen = new DijkstraGraphNode("Bremen");
map.addNode(bremen);
DijkstraGraphNode hannover = new DijkstraGraphNode("Hannover");
map.addNode(hannover);
DijkstraGraphNode dortmund = new DijkstraGraphNode("Dortmund");
map.addNode(dortmund);
DijkstraGraphNode bochum = new DijkstraGraphNode("Bochum");
map.addNode(bochum);
DijkstraGraphNode koeln = new DijkstraGraphNode("Koeln");
map.addNode(koeln);
DijkstraGraphNode bonn = new DijkstraGraphNode("Bonn");
map.addNode(bonn);
DijkstraGraphNode mainz = new DijkstraGraphNode("Mainz");
map.addNode(mainz);
DijkstraGraphNode frankfurt = new DijkstraGraphNode("Frankfurt");
map.addNode(frankfurt);
DijkstraGraphNode kassel = new DijkstraGraphNode("Kassel");
map.addNode(kassel);
DijkstraGraphNode wuerzburg = new DijkstraGraphNode("Wuerzburg");
map.addNode(wuerzburg);
DijkstraGraphNode leipzig = new DijkstraGraphNode("Leipzig");
map.addNode(leipzig);
DijkstraGraphNode nuernberg = new DijkstraGraphNode("Nuernberg");
map.addNode(nuernberg);
DijkstraGraphNode stuttgart = new DijkstraGraphNode("Stuttgart");
map.addNode(stuttgart);
DijkstraGraphNode muenchen = new DijkstraGraphNode("Muenchen");
map.addNode(muenchen);
DijkstraGraphNode karlsruhe = new DijkstraGraphNode("Karlsruhe");
map.addNode(karlsruhe);
map.addEdge(kiel, hamburg, 97);
map.addEdge(kiel, luebeck, 84);
map.addEdge(luebeck, hamburg, 74);
map.addEdge(luebeck, berlin, 284);
map.addEdge(berlin, hamburg, 289);
map.addEdge(hamburg, bremen, 119);
map.addEdge(bremen, hannover, 122);
map.addEdge(hannover, hamburg, 150);
map.addEdge(berlin, hannover, 290);
map.addEdge(berlin, leipzig, 188);
map.addEdge(hannover, kassel, 167);
map.addEdge(leipzig, kassel, 250);
map.addEdge(kassel, dortmund, 160);
map.addEdge(dortmund, bremen, 234);
map.addEdge(dortmund, hannover, 210);
map.addEdge(dortmund, bochum, 22);
map.addEdge(dortmund, koeln, 93);
map.addEdge(koeln, bochum, 82);
map.addEdge(koeln, bonn, 29);
map.addEdge(bonn, mainz, 169);
map.addEdge(frankfurt, mainz, 45);
map.addEdge(frankfurt, kassel, 193);
map.addEdge(leipzig, nuernberg, 278);
map.addEdge(kassel, wuerzburg, 209);
map.addEdge(wuerzburg, nuernberg, 110);
map.addEdge(wuerzburg, frankfurt, 119);
map.addEdge(nuernberg, muenchen, 166);
map.addEdge(muenchen, stuttgart, 223);
map.addEdge(nuernberg, stuttgart, 208);
map.addEdge(stuttgart, karlsruhe, 82);
map.addEdge(karlsruhe, frankfurt, 147);
map.addEdge(frankfurt, koeln, 189);
map.switchToISOMLayout();
}
public void dijkstraAlgorithmus(String startpunkt) {
gelbeListe = new ListWithViewer();
DijkstraGraphNode startNode = (DijkstraGraphNode) map.getNode(startpunkt);
startNode.setDistanz(0);
startNode.setWeg(new List());
gelbeListe.append(startNode);
while(gelbeListe.isEmpty() == false){
gelbeListe.toFirst();
DijkstraGraphNode node = (DijkstraGraphNode) gelbeListe.getObject();
//System.out.println("node: "+node);
gelbeListe.remove();
node.mark();
node.ausgeben();
List neighbours = map.getNeighbours(node);
neighbours.toFirst();
while(neighbours.hasAccess()){
DijkstraGraphNode currentNeighbour = (DijkstraGraphNode) neighbours.getObject();
//System.out.println("currentNeighbour: "+currentNeighbour);
double streckeNodeCurrentNeighbour = map.getEdgeWeight(node, currentNeighbour);
if(currentNeighbour.getDistanz() > node.getDistanz()+streckeNodeCurrentNeighbour){
// ueber node fuehrt eine kuerzere Strecke zu currentNeighbour!
currentNeighbour.setWeg(node.getWeg());
currentNeighbour.setDistanz(node.getDistanz()+streckeNodeCurrentNeighbour);
// currentNeighbour in gelbeListe einfuegen bzw. ersetzen
inGelbeListeUpdaten(currentNeighbour);
}
neighbours.next();
}
}
}
private void inGelbeListeUpdaten(DijkstraGraphNode node) {
boolean inserted = false;
gelbeListe.toFirst();
while(gelbeListe.hasAccess()){
DijkstraGraphNode aktuell = (DijkstraGraphNode) gelbeListe.getObject();
if(aktuell.getDistanz() >= node.getDistanz()){
gelbeListe.insert(node);
inserted = true;
break;
}
gelbeListe.next();
}
if(inserted){
// ggf. taucht currentNeighbour nochmal in der Liste auf!
// dann muss er entfernt werden!
while(gelbeListe.hasAccess()){
DijkstraGraphNode aktuell = (DijkstraGraphNode) gelbeListe.getObject();
if(aktuell.getName().equals(node.getName())){
gelbeListe.remove();
break;
}
gelbeListe.next();
}
}
else{
// der Knoten wurde noch nicht eingefuegt!
gelbeListe.append(node);
}
}
public static void main(String[] args) {
DijkstraAlgorithmus da = new DijkstraAlgorithmus();
da.initMap();
da.dijkstraAlgorithmus("Muenchen");
}
}
public class DijkstraGraphNode extends GraphNode implements Comparable {
private List weg;
private double distanz;
public DijkstraGraphNode(String name) {
super(name);
distanz = 1000000;
weg = new List();
}
public void setDistanz(double distanz){
this.distanz = distanz;
}
public double getDistanz(){
return distanz;
}
public void setWeg(List neuerWeg){
this.weg = new List();
neuerWeg.toFirst();
while(neuerWeg.hasAccess()){
weg.append(neuerWeg.getObject());
neuerWeg.next();
}
// den Knoten selber anhaengen!
weg.append(this.getName());
}
public void ausgeben(){
System.out.println(toString());
weg.toFirst();
String wegString = "";
while(weg.hasAccess()){
wegString+= weg.getObject();
wegString+= "->";
weg.next();
}
System.out.println(wegString);
}
public String toString(){
String ergebnis = this.getName()+": "+this.distanz;
return ergebnis;
}
@Override
public int compareTo(Object arg0) {
DijkstraGraphNode dgn2 = (DijkstraGraphNode) arg0;
if(this.distanz < dgn2.distanz){
return -1;
}
if(this.distanz > dgn2.distanz){
return 1;
}
return 0;
}
public List getWeg() {
return weg;
}
}
Anwendungsbeispiele zu Graphen
Beispiel: Minimaler Spannbaum
Diese Methode erstellt aus einem Graphen die kürzeste Methode alle Knoten des Graphen zu verbinden.
Hauptmethode
Alle Kanten werden ausgelesen und ihrem Gewicht nach, bei der kuerzesten angefangen,durchgegangen.
Kann die momentan betrachtete Kante eingefuegt werden, ohne dass ein Kreis entsteht, wird sie eingefuegt.
public Graph minimalerSpannbaum(Graph pGraph){
System.out.println("minimalerSpannbaum()");
//es wird ein neuer Graph erstellt, der das Ergebnis hinterher anzeigt
Graph ergebnis = new Graph();
//alle Knoten des uebergebenen Graphen werden in den spaeteren Ergebnisgraphen eingetragen
List nnodes = pGraph.getNodes();
nnodes.toFirst();
while(nnodes.hasAccess()){
GraphNode akt = (GraphNode)nnodes.getObject();
ergebnis.addNode(akt);
nnodes.next();
}
//alle Kanten werden ihrem Gewicht nach sortiert in einem Vector uebergeben
Vector<Edge> edges = alleKantenSortiert(pGraph);
//dieser Vector wird duchgegangen
for(int i = 0; i < edges.size(); i++){
//kann die aktuell im Vector betrachtete Kante eingefuegt werden, ohne dass ein Kreis entsteht,
//wird sie eingefuegt
Edge akt = edges.elementAt(i);
if(!erzeugtKreis(ergebnis, edges.elementAt(i))){
ergebnis.addEdge(akt.getNodeA(), akt.getNodeB(), akt.getWeight());
System.out.println("addEdge");
}
}
return ergebnis;
}
Hilfsmethoden
Fuer die Ueberpruefung ob ein Kreis erzeugt wird ist eine eigene Methode hilfreich. Hier wird von einem Knoten der einzufuegenden Kantre ausgehend ueberprueft, ob der andere Knoten erreichbar ist. Wenn ja, dann wuerde durch einfuegen ein Kreis erzeugt, wenn nein nicht.
private boolean erzeugtKreis(Graph pGraph, Edge pEdge) {
//von dem einen Knoten aus erreichbare Nodes werden ausgelesen un in einer Liste gespeichert
List erreichbare = erreichbareNodes(pGraph, pEdge.getNodeA());
//und werden durchgegangen
erreichbare.toFirst();
while(erreichbare.hasAccess()){
//wird der Knoten, von dem ausgegangen wurde gefunden wuerde ein Kreis erzeugt und true ausgegeben
if(pEdge.getNodeB() == (GraphNode)erreichbare.getObject()){
return true;
}
erreichbare.next();
}
//wird der KNoten nicht gefunden wird false zurueckgegeben, da kein Kreis erzeugt wuerde
return false;
}
Anmerkung: Es gibt natürlich noch weitere Möglichkeiten die Strategie zu realisieren. Eine sehr einfache kommt ohne die Methode erreichbareNodes(...) aus: Man markiert alle bereits verbundenen Knoten (im Bsp. eines Stromnetzes: alle bereits "angeschlossenen" Knoten), also beim Einfügen jeder Kante die zu ihr gehörenden Knoten, falls diese noch nicht markiert sind. Diese Taktik macht das Überprüfen, ob beim Einfügen ein Kreis entsteht, sehr einfach: Falls beide zur Kante gehörenden Knoten bereits markiert sind, entstünde ein Kreis und die Kante darf nicht eingefügt werden.
Beispiel: Erreichbare Knoten
Um alle erreichbaren Knoten zu bekommen erstellen wir erst eine Liste ergebnis, die am Ende ausgegen wird.Danach wird der Liste ergebnis der startNode angehangen. Dieses Node wird dann im Graphen makiert. Danach wird eine while-Schleife geöffnet, die solange läuft wie die Liste ergebnis ein aktuelles Objekt besitzt. Sie fügt die Nachbarn des aktuellen Nodes in eine Liste nachbarliste1 ein. Eine weitere while-Schleife wird geöffnet, die solange läuft, wie die Liste nachbarliste1 ein aktuelles Objekt hat. Wenn das aktuelle Node nicht markiert ist wird das Objekt dem ergebnis angefügt (also der erreichbare Nachbar wird in das Ergebnis geschrieben) und das Node wird makiert. So werden am Ende mit der Liste ergebnis alle erreichbare Nachbarn ausgegeben.
public List erreichbareNodes(Graph pGraph,GraphNode pNode){
pGraph.resetMarks();
List ergebnis = new List();
ergebnis.append(pNode);
pNode.mark();
ergebnis.toFirst();
while(ergebnis.hasAccess()){
GraphNode akt1=(GraphNode) ergebnis.getObject();
List nachbarliste1 =pGraph.getNeighbours(akt1);
nachbarliste1.toFirst();
while(nachbarliste1.hasAccess()){
GraphNode akt2=(GraphNode) nachbarliste1.getObject();
if(akt2.isMarked()==false){
ergebnis.append(akt2);
akt2.mark();
}
nachbarliste1.next();
}
ergebnis.next();
}
return ergebnis;
}
Beispiel: Knoten mit ungerader Kantenzahl markieren
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
Beispiel: Summe der Kantenkosten eines Knotens bestimmen
public int Kantenkosten(GraphWithViewer pGraph, GraphNode pNode)
{
int ergebnis = 0; // Variable zum Speichern der Kosten wird deklariert
List nachbarn = pGraph.getNeighbours(pNode);
nachbarn.toFirst();
while(nachbarn.hasAccess()) // Schleife durchläuft einmal alle Nachbarn
{
GraphNode akt = (GraphNode)nachbarn.getObject();
int help = (int) pGraph.getEdgeWeight(pNode, akt);
ergebnis=ergebnis+help; //Distanz wird hinzugefügt
nachbarn.next();
}
return ergebnis; // Distanz wird ausgegeben
}
Beispiel: Knoten mit maximalen Kantenkosten bestimmen
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
Beispiel: Nächsten Nachbarn eines Knotens bestimmen
Strategie:
Man entfernt alle markierten Nodes aus der NachbarListe und durchläuft diese Liste und guckt, welches die kürzeste Kante zu pNode hat.
public GraphNode gibNaechstenNachbarn(GraphWithViewer gwv, GraphNode pNode)
{
GraphNode ergebnis = null;
double gewicht;
List nachbarListe = gwv.getNeighbours(pNode);
// alle Nachbarn werden in die NachbarListe eingefügt
nachbarListe.toFirst();
while(nachbarListe.hasAccess())
{
GraphNode aktKn=(GraphNode)nachbarListe.getObject();
if(aktKn.isMarked())
// wenn ein Objekt der NachbarListe markiert ist, dann wird es entfernt.
{
nachbarListe.remove();
}
else{
nachbarListe.next();
}
}
nachbarListe.toFirst();
// das erste Objekt der nachbarListe wird als Ergebnis deklariert
// und das Gewicht der Kante von diesem Objekt zu pNode als Gewicht
ergebnis = (GraphNode)nachbarListe.getObject();
gewicht = gwv.getEdgeWeight(pNode, ergebnis);
nachbarListe.next();
while(nachbarListe.hasAccess())
{
GraphNode aktuellerNode = (GraphNode)nachbarListe.getObject();
double aktuellesGewicht = gwv.getEdgeWeight(pNode, aktuellerNode);
if(aktuellesGewicht<gewicht)
// wenn ein Gewicht einer Kante von einem Nachbarn zu pNode kleiner ist als das Gewicht,
// dann wird dieses das neue Gewicht und der Nachbar wird das Ergebnis
{
ergebnis = aktuellerNode;
gewicht = gwv.getEdgeWeight(pNode, aktuellerNode);
}
nachbarListe.next();
}
return ergebnis;
}
Beispiel: Überprüfen, ob im Graphen ein Dreierkreis existiert
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
Beispiel: Alle Nachbarn zählen
TODO: Quellcode erklären und im Quellcode kommentieren
public int zaehleNachbarn(GraphWithViewer pGraph, GraphNode pNode){
int ergebnis = 0;
List neighbours = graph.getNeighbours(pNode);
neighbours.toFirst();
while(neighbours.hasAccess()){
ergebnis++;
neighbours.next();
}
return ergebnis;
}
Beispiel: Wer hat die meisten Nachbarn
TODO: Quellcode erklären und im Quellcode kommentieren
public String meisteNachbarn(GraphWithViewer Ggraph){
List hilfe=new List();
hilfe.concat(Ggraph.getNodes());
hilfe.toFirst();
GraphNode aktNode =null;
int max=-1;
while(hilfe.hasAccess())
{
GraphNode aktuell=(GraphNode)hilfe.getObject();
int akt=this.kantenzahl(Ggraph, aktuell);
if(akt>max)
{
max=akt;
aktNode=(GraphNode)hilfe.getObject();
}
else{
hilfe.next();
}
}
System.out.println(max);
return aktNode.getName();
}