Graph: Unterschied zwischen den Versionen
Dfox (Diskussion | Beiträge) |
(Aufbau der Seite strukturiert und TODOs eingebaut) |
||
| Zeile 1: | Zeile 1: | ||
[[Kategorie:Informatik]] | [[Kategorie:Informatik]] | ||
[[Kategorie:Komplexe Datenstrukturen]] | |||
==Schnittstellenbeschreibung== | ==Schnittstellenbeschreibung== | ||
* [[Datei:Graph.pdf]] | * [[Datei:Graph.pdf]] | ||
* [[Datei:GraphNode.pdf]] | * [[Datei:GraphNode.pdf]] | ||
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 === | |||
TODO: Erklärungen zum Tiefendurchlauf | |||
<code>TODO: gut kommentierter Quellcode des Tiefendurchlaufs</code> | |||
=== Breitendurchlauf === | |||
TODO: Erklärungen zum Breitendurchlauf | |||
<code>TODO: gut kommentierter Quellcode des Breitendurchlaufs</code> | |||
== 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,...) | |||
<code> TODO: Dijkstra-Algorithmus gut kommentiert einfügen</code> | |||
== Anwendungsbeispiele zu Graphen == | |||
===Beispiel: Alle Nachbarn zählen=== | ===Beispiel: Alle Nachbarn zählen=== | ||
TODO: Quellcode erklären und im Quellcode kommentieren | |||
<code> public int zaehleNachbarn(GraphWithViewer pGraph, GraphNode pNode){ | <code> public int zaehleNachbarn(GraphWithViewer pGraph, GraphNode pNode){ | ||
int ergebnis = 0; | int ergebnis = 0; | ||
| Zeile 19: | Zeile 43: | ||
} </code> | } </code> | ||
== | ===Beispiel: Wer hat die meisten Nachbarn=== | ||
TODO: Quellcode erklären und im Quellcode kommentieren | |||
<code> public String meisteNachbarn(GraphWithViewer Ggraph) | <code> public String meisteNachbarn(GraphWithViewer Ggraph) | ||
{ | { | ||
List hilfe=new List(); | List hilfe=new List(); | ||
hilfe.concat(Ggraph.getNodes()); | hilfe.concat(Ggraph.getNodes()); | ||
hilfe.toFirst(); | hilfe.toFirst(); | ||
GraphNode aktNode =null; | GraphNode aktNode =null; | ||
int max=-1; | int max=-1; | ||
while(hilfe.hasAccess()) | while(hilfe.hasAccess()) | ||
{ | { | ||
GraphNode aktuell=(GraphNode)hilfe.getObject(); | GraphNode aktuell=(GraphNode)hilfe.getObject(); | ||
int akt=this.kantenzahl(Ggraph, aktuell); | int akt=this.kantenzahl(Ggraph, aktuell); | ||
if(akt>max) | if(akt>max) | ||
{ | { | ||
max=akt; | max=akt; | ||
aktNode=(GraphNode)hilfe.getObject(); | aktNode=(GraphNode)hilfe.getObject(); | ||
} | } | ||
else{ | else{ | ||
hilfe.next(); | hilfe.next(); | ||
} | } | ||
} | |||
} | System.out.println(max); | ||
return aktNode.getName(); | |||
}</code> | |||
return aktNode.getName(); | |||
} | |||
</code> | |||
Version vom 29. Mai 2012, 21:15 Uhr
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
TODO: Erklärungen zum Tiefendurchlauf
TODO: gut kommentierter Quellcode des Tiefendurchlaufs
Breitendurchlauf
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: 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();
}