Graph: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 35: Zeile 35:
===Beispiel: Alle Nachbarn zählen===
===Beispiel: Alle Nachbarn zählen===
TODO: Quellcode erklären und im Quellcode kommentieren
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;
     List neighbours = graph.getNeighbours(pNode);
     List neighbours = graph.getNeighbours(pNode);
Zeile 45: Zeile 46:
     }
     }
     return ergebnis;
     return ergebnis;
   } </code>
   }  
</code>


===Beispiel: Wer hat die meisten Nachbarn===
===Beispiel: Wer hat die meisten Nachbarn===
TODO: Quellcode erklären und im Quellcode kommentieren
TODO: Quellcode erklären und im Quellcode kommentieren
  <code> public String meisteNachbarn(GraphWithViewer Ggraph){  
 
List hilfe=new List();  
<code> public String meisteNachbarn(GraphWithViewer Ggraph){
hilfe.concat(Ggraph.getNodes());  
    List hilfe=new List();
hilfe.toFirst();  
    hilfe.concat(Ggraph.getNodes());
GraphNode aktNode =null;  
    hilfe.toFirst();
int max=-1;  
    GraphNode aktNode =null;
while(hilfe.hasAccess())  
    int max=-1;
{  
    while(hilfe.hasAccess())
GraphNode aktuell=(GraphNode)hilfe.getObject();  
    {
int akt=this.kantenzahl(Ggraph, aktuell);  
        GraphNode aktuell=(GraphNode)hilfe.getObject();
if(akt>max)  
        int akt=this.kantenzahl(Ggraph, aktuell);
{
        if(akt>max)
max=akt;  
        {
aktNode=(GraphNode)hilfe.getObject();  
            max=akt;
}
            aktNode=(GraphNode)hilfe.getObject();
else{  
        }
hilfe.next();  
        else{
}  
            hilfe.next();
}
        }
System.out.println(max);
    }
return aktNode.getName();
    System.out.println(max);
    return aktNode.getName();
} </code>
} </code>

Version vom 29. Mai 2012, 21:26 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 (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: 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();

}