Lehrzeit

Schule & Informatik

Monat: März 2017

Tiefensuche mit Processing

Basierend auf meinem letzten Beitrag habe ich jetzt noch die Tiefensuche mit Hilfe einer Adjazenzmatrix implementiert. Besuchte Knoten werden mit Gelb markiert und der aufspannenden Baum besteht aus gelben Kanten.

Die Knoten 1 und 7 wurden nicht besucht, was man an dem fehlenden gelben Punkt sieht. Ob ein Graph zusammenhängend ist, lässt sich daher mit der Tiefesuche feststellen.

Zum besseren Verständnis habe ich noch das in meinem Fall benötigte besucht[]:boolean – Feld ausgeben lassen, sowie den zu jedem Knoten gehörigen Vorgänger-Knoten, den ich in einem Feld vorgaenger[]:int speichere.

Die darüberstehenden Zahlen gibt die Durchlaufreihenfolge der Knoten wieder.

Den bisherigen Stand biete ich hier wieder zum Download an: ProcessingTiefensuche

Im nächsten Schritt möchte ich natürlich den schrittweisen Durchlauf animiert darstellen. Aber dazu muss ich die rekursive Implementierung des Algorithmus aufbrechen, damit bei jedem Durchlauf der draw()-Methode nur 1 Schritt gemacht wird.

Graphen und Processing

Angeregt durch die Videos von Daniel Shiffman möchte ich dieses Jahr das Implementieren der Graphenalgorithmen in der elften Jahrgangsstufe auf Basis von processing mit wie immer Java machen.

Hierzu habe ich jetzt in BlueJ ein Grundprojekt programmier, dass den Schüler als Vorlage zum Weitermachen dienen soll. Folgende Features habe ich dabei umgesetzt:

  1. Graphen werden per Zufall erzeugt.
    Hierzu werden 20 Knoten zufällig im Fenster erzeugt, Die Kanten werden ebenfalls zufällig erzeugt. Um nicht nur vollständige Graphen zu bekommen, habe ich zu folgender Implementierung gegriffen:

    for(int i=0; i < maxKnoten; i=i+1) {
        for(int j=0; j < maxKnoten; j=j+1) {
            if(i==j) { //Diagonale mit Nullen belegen
                adjazenzmatrix[i][j] = 0;
            } else {
                int zufallsGewicht = (int)random(1,60);
                 //Die 3 oder das == durch != ersetzen
                if (zufallsGewicht%3==0)
                    adjazenzmatrix[i][j] = zufallsGewicht;
                else
                    adjazenzmatrix[i][j] = 0;
            }
        }
    }
    

    Dadurch erhalte ich alle möglichen Graphen mit einer unterschiedlichen Anzahl an Kanten. Auch mal nicht zusammenhängende Graphen.

  2. Ist der Graph mal erzeugt können die Knoten mit der Maus noch verschoben werden. Hierzu muss der Graph aber im Verschiebmodus sein. Dieser ist standardmäßig aktiviert und kann durch Drücken der Taste ‚m‘ verändert werden.
  3. Durch Drücken der Taste ‚i‘ werden die Knotennamen eingeblendet. Die Kantengewichte werden durch Drücken der Taste ‚e‘ ausgegeben.
    Die erstmalige Anzeige der Knotennamen dauert am Anfang etwas. Warum weiß ich nicht.
  4. Durch Drücken der Taste ‚a‘ wird ein Algorithmus gestartet, wobei im Moment noch keiner implementiert ist.
  5. Durch Drücken der Taste ’s‘ und mit einem Mausklick wird ein möglicher Startknoten grün markiert oder entmarkiert.
  6. Durch Drücken der Taste ‚t‘ und mit einem Mausklick wird ein möglicher Zielknoten rot markiert oder entmarkiert.
  7. Durch Drücken der Taste ‚h‘ kann auch während der Benutzung des Programms die Hilfe angezeigt werden. Auch das dauert am Anfang etwas.

Hier noch die zip-Datei zum Runterladen und weiterentwickeln:  ProcessingAdjazenzMatrix.

© 2017 Lehrzeit

Theme von Anders NorénHoch ↑