Einstieg in das Thema
Was brauchst du als Basiswissen?
Es reicht das Grundwissen zu Graphen. Ob man zuerst Breiten- oder Tiefensuche macht, ist egal.
Worum geht es?
Du hast nun ein Verfahren, einen Graphen zu durchlaufen kennen gelernt. Aber doppelt hält besser. Es kommt nun ein zweites Verfahren.
Was ist das Ziel?
Am Ende sollst du die Tiefensuche verstanden haben.
Erarbeitung
Theorie
Aufgaben
Aufgabe 1
Diesen Graphen kennst du schon. Wende nun den Tiefensuche-Algorithmus an und gib die Reihenfolge der besuchten Knoten an.
Aufgabe 2
Untersuche, ob dieser Weg eindeutig ist oder ob die Tiefensuche auch andere Wege finden kann, wenn man nicht alphabetisch vorgeht.
Aufgabe 3
Gib die Reihenfolge bei Tiefensuche an, wenn man bei H startet.
Aufgabe 4
Gehe mit Tiefensuche durch den Graphen.
Aufgabe 5
Gehe mit Tiefensuche durch den Graphen.
Noch was zum Schluss:
Aufgabe 6
Zeichne einen Graphen mit A,B,C,D und E, der bei Tiefen- und bei Breitensuche das gleiche Ergebnis bringt.
Zusammenfassung
Was muss man wissen/können?
Du kennst nun die Tiefensuche als zweiten Algorithmus zum Durchlaufen eines Graphen und kannst ihn anwenden, also die Reihenfolge der besuchten Knoten angeben.
Was können anschließende Themen sein?
Zum Schluss suchen wir noch den besten Weg zu einem Zieknoten.
