Einstieg in das Thema
Was brauchst du als Basiswissen?
Du kennst Graphen, weißt, was das ist und
erkennst sie.
Worum geht es?
Siehst du ein Bild von einem Graphen,
kannst du diesen sofort überblicken.
Graphen können aber "unsichtbar" sein. Zum einen
kann das passieren, wenn es sich um unbekannte Wege
im Wald oder um ein Höhlensystem handelt.
Aber es kann auch sein, dass man in einem Graphen
ganz bestimmte Knoten sucht.
Es kann aber auch sein, dass du als Programmierer
einen Datenstruktur als Graph bekommst, und dich erst
einmal durch diese hangelt musst.
Für das "Erkunden" von Graphen gibt es zwei
klassische Algorithmen. Mit der Breitensuche
fangen wir an.
Was ist das Ziel?
Am Ende kennst du ein Verfahren, um einen
Graphen zu durchlaufen
Erarbeitung
Aufgaben
Aufgabe 1
Gehe per Breitensuche durch die Höhle und notiere alle Knoten, bis die Höhle vollständig erforscht ist.
Aufgabe 2
Nehmen wir an, es wurde nur nach C gesucht. Nach wie vielen Schritten ist man am Ziel?
Aufgabe 3
Durchlaufe den Graphen von I ausgehend.
Stell dir vor, jemand hat mittels Breitensuche
einen Graphen durchlaufen. Auf seinem Zettel steht
ABDCEF.
Aufgabe 4
Zeichne einen Graphen mit Startknoten A, der diese Knotenfolge bei einer Breitensuche liefert.
Aufgabe 5
Ist das Ergebnis eindeutig oder gibt es mehrere Möglichkeiten? Begründe kurz.
Aufgabe 6
Es wird bei A gestartet. Drei Schüler versuchen gleichzeitig, den Graphen mit Breitensuche zu durchlaufen. Günther beginnt mit BEF, Fritz mit FEB und Heinrich mit EFB. Wer hat Recht?
Aufgabe 7
Durchlaufe nun den Graphen wieder mit Breitensuche und gib die Reihenfolge der Knoten an.
Aufgabe 8
Unabhängig von der Reihenfolge des Aufschreibens ist eindeutig, welche Knoten zuletzt gefunden werden. Gib alle Knoten an.
Aufgabe 9
Jemand macht den Vorschlag, immer den Knoten auszuwählen, der im Alphabet als nächstes kommt. Werden die Ergebnisse dann eindeutig? Gibt es dann genau eine Reihenfolge?
Aufgabe 10
Nun hast du einen teilweise gerichteten Graphen. Durchlaufe diesen nun mit der Breitensuche. Wähle die Reihenfolge für eine bessere Vergleichbarkeit nun nach dem Alphabet.
Zusammenfassung
Was muss man wissen/können?
Du kannst einen Graphen komplett oder bis zu einem
bestimmten Knoten in Breitensuche durchlaufen
und kennst die Besonderheiten (Abstände, Reihenfolge).
Was können anschließende Themen sein?
Es gibt noch weitere Arten, einen Graphen zu durchlaufen.
Auf zur Tiefensuche.
