Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Im­ple­men­tie­rung von Gra­phen-Al­go­rith­men im Gra­phen­tes­ter

Der Gra­phen­tes­ter ist nicht nur für die Er­for­schung und Si­mu­la­ti­on von Al­go­rith­men ge­eig­net, son­dern auch für die Im­ple­men­ta­ti­on ei­ge­ner Al­go­rith­men. Diese kön­nen dann ge­nau­so im Si­mu­la­ti­ons­fens­ter aus­ge­führt und un­ter­sucht wer­den, wie schon fer­ti­ge Al­go­rith­men. Damit kann die im Leis­tungs­fach ge­for­der­te Im­ple­men­tie­rung min­des­tens eines Gra­phen­al­go­rith­mus er­füllt wer­den2.

Dazu muss für jeden Al­go­rith­mus eine ei­ge­ne von der Klas­se Gra­phAl­go ab­ge­lei­te­te Klas­se er­stellt wer­den, deren Name mit "Gra­phAl­go_" be­ginnt. Diese Klas­sen wer­den im Un­ter­ord­ner "ei­ge­ne­Al­go­rith­men" ab­ge­legt. In­ner­halb die­ser Klas­se müs­sen die zwei Me­tho­den get­Be­zeich­nung() und fu­eh­re­Al­go­rith­mus­Aus() im­ple­men­tiert wer­den. get­Be­zeich­nung gibt nur den Namen des Al­go­rith­mus zu­rück, der im Gra­phen­tes­ter im Si­mu­la­ti­ons­fens­ter zur Aus­wahl an­ge­zeigt wird. fu­eh­re­Al­go­rith­mus­Aus im­ple­men­tiert den Al­go­rith­mus. Dafür ste­hen fol­gen­de At­tri­bu­te und Me­tho­den be­reit:

At­tri­bu­te:
Graph g Re­fe­renz auf den kom­plet­ten Graph. Eine Be­schrei­bung der wich­tigs­ten Me­tho­den der Klas­sen Graph, Knoten und Kante be­fin­den sich im Ord­ner 03_­tausch­ord­ner. Die voll­stän­di­ge Ja­va­Doc- Do­ku­men­ta­ti­on liegt im Un­ter­ord­ner doc des Gra­phen­tes­ters.
Me­tho­den:
getStartKnoten() lie­fert den beim Start des Al­go­rith­mus aus­ge­wähl­ten Kno­ten zu­rück. Wurde kein Kno­ten aus­ge­wählt, wird der Kno­ten mit Num­mer 0 zu­rück­ge­ge­ben. Eine Be­schrei­bung der Klas­se Knoten be­fin­det sich im Ord­ner 03_­tausch­ord­ner.
step() legt fest, dass der Al­go­rith­mus an die­ser Stel­le im Ein­zel­schritt­mo­dus an­ge­hal­ten wer­den soll.
info(String text) gibt einen Text im Hil­fe­fens­ter aus, um den Ab­lauf des Al­go­rith­mus zu be­schrei­ben. Dabei wird au­to­ma­tisch auch der Zu­stand des Gra­phen im Hil­fe­fens­ter ge­spei­chert. Daher soll­te die Me­tho­de nach der Aus­füh­rung der Än­de­rung am Gra­phen auf­ge­ru­fen wer­den, die durch den Text be­schrie­ben wird.
infoIndentMore() die fol­gen­den In­fo­tex­te wer­den eine Ebene tie­fer ein­ge­rückt. Der zu­letzt ein­ge­füg­te Text wird mit einem Auf­klapp­me­cha­nis­mus ver­se­hen.
infoIndentLess() die Ein­rü­ckung wird eine Ebene zu­rück­ge­nom­men.
melde(String text) gibt einen Text in einem Popup-Fens­ter aus, um das Er­geb­nis eines Al­go­rith­mus dem An­wen­der mit­zu­tei­len. Dabei wird au­to­ma­tisch auch der Be­fehl info aus­ge­führt.

Bei der Im­ple­men­tie­rung der Al­go­rith­men ist es sinn­voll, viel mit Lis­ten von Kno­ten und Kan­ten zu ar­bei­ten. Die Klas­se Graph er­mög­licht es, Lis­ten aller Kno­ten/Kan­ten, die Liste der Nach­bar­kno­ten und der aus­ge­hen­den/ein­ge­hen­den Kan­ten zu er­hal­ten. Dabei kann durch einen Lamb­da-Aus­druck die Aus­wahl be­schränkt wer­den (z.B. nur nicht mar­kier­te, aber schon be­such­te Kno­ten):

List knoten = g.getAlleKnoten(k->!k.isMarkiert() && k.isBesucht());

Mit Collections.sort(...) kön­nen Kno­ten oder Kan­ten auf­stei­gend nach ihrem Wert / Ge­wicht sor­tiert wer­den, da Kno­ten und Kan­ten das In­ter­face Com­pa­ra­ble im­ple­men­tie­ren. Da­durch ist es recht ein­fach, z.B. den Kno­ten mit dem ge­rings­ten Wert zu fin­den (Di­jk­s­tra- oder to­po­lo­gi­sche Sor­tie­rung). Na­tür­lich lei­det die Per­for­mance eines Al­go­rith­mus dar­un­ter, da die Er­mitt­lung eines kleins­ten Ele­ments in O(n) im­ple­men­tiert wer­den kann und das Sor­tie­ren mit an­schlie­ßen­dem Ent­neh­men des ers­ten Ele­ments in O(n log n) liegt. Hier muss der Fokus aber auf der ein­fa­chen Im­ple­men­tie­rung lie­gen, da in die­sem Be­reich nur wenig im­ple­men­tiert wird.

Für viele Al­go­rith­men ist eine toDo-Liste mit noch zu be­ar­bei­ten­den Kno­ten / Kan­ten not­wen­dig. Mit die­ser toDo-Liste kann z.B. Tie­fen- und Brei­ten­su­che rea­li­siert wer­den, je nach­dem ob man ein Schlan­ge oder einen Sta­pel ver­wen­det. Hier bie­tet es sich auch an, die selbst ge­schrie­be­nen Klas­sen aus dem Ka­pi­tel ADT (siehe dort) zu ver­wen­den. In den Mus­ter­lö­sun­gen wur­den sie nicht ver­wen­det, da Sie als Leh­rer die Rei­hen­fol­ge der Un­ter­richts­ein­hei­ten frei wäh­len kön­nen.

Ei­ni­ge Hil­fe­kar­ten zu Stan­dar­dim­ple­men­ta­tio­nen be­fin­den sich im Ord­ner 02_­ko­pier­vor­la­gen.

 

2 Bil­dungs­plan In­for­ma­tik: 3.​3.​1.​2 (11) einen Al­go­rith­mus auf Gra­phen im­ple­men­tie­ren (unter Ver­wen­dung ge­eig­ne­ter Bi­blio­the­ken oder Frame­works)

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][298 KB]

 

Wei­ter zu Struk­tur der Ar­beits­blät­ter