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.