Graph

TODO: Kurze allgemeine Erklärung/Einführung zu Graphen

Schnittstellenbeschreibung

• Datei:Graph.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 (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

TODO: Methode erklären

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();
   }