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)

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

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

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