Graph
TODO: Kurze allgemeine Erklärung/Einführung zu Graphen
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)
TODO: Erklärungen zum Tiefendurchlauf
TODO: gut kommentierter Quellcode des Tiefendurchlaufs
Breitendurchlauf (BFS)
TODO: Erklärungen zum Breitendurchlauf
TODO: gut kommentierter Quellcode des Breitendurchlaufs
Kürzeste Wege in Graphen: Der Dijkstra-Algorithmus
TODO: Besondere Dijkstra-Schnittstelle einfügen (Lehrer)
TODO: Erklärungen zu Dijkstra (besondere Schnittstelle erklären, Strategie erklären, Besonderheiten,...)
TODO: Dijkstra-Algorithmus gut kommentiert einfügen
Anwendungsbeispiele zu Graphen
Beispiel: Minimaler Spannbaum
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
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
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
Beispiel: Knoten mit maximalen Kantenkosten bestimmen
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
Beispiel: Nächsten Nachbarn eines Knotens bestimmen
TODO: Methode erklären
TODO: Quelltext gut kommentiert einfügen
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();
}