nachdem wir uns im letzten kapitel der vorlesung mit graphen allgemein und datenstrukturen für graphen beschäftigten wollen uns jetzt algorithmen auf graphen anziehen wir fangen an mit grundlegenden algorithmen der tiefen suche der breiten suche und anwendungen davon das wird uns zu topologischen sortieren danach sehen wir uns kurz dass die wege auf graphen an und im letzten kapitel beschäftigen wir uns zumindest überblicks artig noch mit dem fluss in netzwerken bestattungen diesem video mit dem durchlaufen beziehungsweise durchsuchen von graphen dieses durchlaufen von graphen ist tatsächlich nicht so neues für uns wir kennen die algorithmen im prinzip von den
bäumen schon allerdings ändern sich die spielregeln ein bisschen graphen kann als eine folge meinung von bäumen auffassen im gegensatz zum baum haben jetzt keinen ausgezeichneten wird zur knoten mehr von dem wir starten könnten sondern wir starten von einem vorgegebenen oder von einem beliebigen knoten außerdem hat ein knoten jetzt keine kinder mehr insbesondere kein rechtes oder linkes bzw heraus dass zweites oder irgendwie durch zu nummerieren das kind stattdessen haben wir ausgehende kanten ohne dass da irgend eine ordnung auf diesen kanten vorgegeben ist also es nicht klar welchen der zu erreichenden knoten der nachbar knoten wie als
erstes und welche als letztes besuchen beim baum war das anders dann einfach von links nach rechts durchnummeriert oft ist es so dass ein graf ein bestimmtes problem modelliert und der durchlauf beziehungsweise die suche den finden eine lösung oder einer optimalen lösung dient also indem wir den grafen durchlaufen suchen und finden wir hoffentlich entweder einen knoten oder den weg den pfad zu diesem knoten zu dieser lösung hin deswegen der begriff suche im graphen wir schauen uns im folgenden die tiefen suche um die breiten suche an die tiefen suche kann man relativ oder interaktiv formulieren die breiten
suche ist immer ein integrativer ein rhythmus im lauf dieser suche werden wir jedem knoten im graphen besuchen das kann bedeuten dass wir den knoten einfach ausgeben das kann bedeuten dass wir irgendwie markieren oder einfärben das kann auch bedeuten dass wir uns irgendwelche eigenschaften am knoten merken zum beispiel wann wir ihm im lauf der suche erreicht haben fangen an mit der tiefen suche die tiefen suche entspricht für einen baum dem pre order von mir aus auch post oder diverse also ein algorithmus klinischen kennen den wir massiv und interaktiv schon formulierte bzw wenn wir uns das ganze
gleich am grafen vorstellen dann kennen wir diesen algorithmus vielleicht auch zum beispiel bei der suche nach dem ausgang aus einem labyrinth dabei könnte ich wie folgt vorgehen von dem punkt aus an dem ich starte wir fangen beim eingang des labyrinths gehe ich immer so weit also so tief wie möglich dabei markiere ich mir mit in irgendeiner art und weise wo ich schon war zum beispiel mit dem marianne faden oder indem ich wie hänsel und gretel brotkrumen streu jedes mal wenn ich ihnen sagt dass sie gerade wenn es nicht weitergeht dann kehre ich um und zwar
so lange bis ich wieder an der kreuzung stehen wo es noch wege gibt die ich noch nicht untersucht hat jeden dieser wege ist untersuche ich durchlaufe ich in der gleichen art und weise also weckruf auf die gleiche art und weise und das mache ich so lange bis ich den ausgang gefunden habe wie sieht der algorithmus als erstes markieren wir den knoten den wir als argument bekommen haben danach besuchen wir ihn besuchen steht für ich gebe den knoten aus oder macht damit was immer ich will danach schaue ich mir für diesen knoten alle ausgehenden kanten an
schaue mir an welchen ziele knoten erreiche ich über diese ausgehende kannte überprüfe ob dieser neue knoten ob diese nachbar knoten markiert ist oder nicht wenn aber markiert wäre dann hätte ich ihn schon ausgegeben ist er nicht markiert dann verwende ich ihn im rezessiven durchlauf in dem ich dfs für diesen knoten wieder aufrufen schauen uns das ganze in beispielen wir fangen hier mit dem knoten 1 an also wir stellen uns vor wir rufen dfs für den knoten 1 auf das bedeutet wir markieren diesen knoten als erstes und besuchen ihn dann gegen ihn aus so jetzt rufen
wir sie für alle ausgehenden kranken das ist eine kante zu drei eine zu sechs und 18 dfs wieder relativ auf ich habe jetzt alle kannten einfach mal hier rot markiert das sind die ausgehenden kannten die ich von der einst aussehe ich habe hier einen ungerichtete grafen verwendet das heißt eingehende und ausgehende kannte ist jeweils gleich ich habe beide richtungen ich könnte das beispiel genauso mit einem gerichteten grafen machen wir müssen uns jetzt für eine reihenfolge dieser drei kanten entscheiden diese reihenfolge ist willkürlich gewählt ich mag es hier in den beispielen immer so dass ich vom
kleinsten knoten wert 3 zum größten knoten wird 8g also die reihenfolge 368 aber wie gesagt die ist liebig gewählt dementsprechend ist auch die reihenfolge des durchlaufs nicht eindeutig weil ich die reihenfolge der ausgehenden kanten beliebig wählen da nehme an es geht mit der drei weiter dann rufen jetzt rekordtief dfs für den knoten drei aus von der drei aus sehen wir die 1 und die 7 bevor wir das machen mag ihm erstmal die drei und geben so aus wir sehen die einst und die sieben die eins ist schon markiert die sieben noch nicht das heißt wir
rufen jetzt wieder die es für den knoten 7 auf markieren schauen sie nach noten haben das ist 3 und die 5 die drei ist schon markiert die fünf noch nicht das heißt wir haben wieder den rekorden aufruf und der 5 moment wir markieren die fünf besuchen sie also geben sie auch schauen uns an welche knut mir von der 5 aussehen das ist die 46 die sieben und die acht die sieben haben wir schon mal gesehen und markiert bleibt die 46 und die acht wir nehmen mit den kleinsten knoten mir gesagt die willkürliche wahl das ist
in dem fall der knoten wert 4 also haben wieder einen rekord sieben aufruf knoten 404 aussehen wird die 50 schon markiert und die sechs die es nicht markiert an der stelle die sechs kann man von der einst aus hier schon gesehen aber wir haben sie noch nicht markiert gehabt jetzt sehen was sie von der 4 aus und rufen der es auf für den knoten sex wir markieren also schauen welche knoten 706 das ist die 1 d4 d5 die sind alle schon markiert hier passiert nichts weiter so wir stehen wieder anknüpfen 4 vom knoten vier aus
können aber nichts weiter machen die fünf schon markiert die sächsische markiert also endet auch dieser aufruf wir stehen jetzt wieder an knoten 5 von knoten fünf aus sind wir weg passiv zum knoten vier gegangen der knoten sechs der es jetzt auch schon abgearbeitet der ist nämlich zwischenzeitlich markiert worden wir sehen von der fünf aus noch den knopf acht der es nicht nicht markiert das heißt wir rufen jetzt der sv für den knien 8 vom knoten acht aussehen wir die 5 die 1 und die 2 die fünf und die einst sind schon markiert das heißt wir
rufen die fsf auch für die 2 nachdem natürlich markiert ausgegeben 2 markieren wir und geben sie auch vom knoten zwei aus diez weiter nichts zu tun das heißt der aufruf kehrt zurück vom knoten 8 aus gibt's auch nichts weiter zu tun alle nachbarn sind markiert die acht von der fünf aus erreicht von der 5 aus gibt's auch nichts mehr zu tun das heißt auch dieser aufruf kehrt zurück der aufruf von der sieben kehrt zurück und schließlich kehrt der aufruf von der 1 zurück und was wir hier jetzt skizziert haben visualisierten sind die reben aufrufe diese
funktion dfs für diesen grafen wir haben hier also die knoten in dem grafen aufgezählt in der reihenfolge 1 3 754 68 2 diese reihenfolge ist nicht eindeutig weil wenn ich an einem knoten stehe ist nicht klar in welcher reihenfolge ich die nachbar knoten aufzählt ich nehme hier gerade als konvention dass ich immer mit dem kleinsten knoten wird beginnen hier das gleiche nochmal auf den folien im schnelldurchgang fangen beide 1 an und arbeiten uns regressiv vor kurz zur darstellung die dunklen kannten das sind die kanten über die ich einen knoten tatsächlich im rekurs eben aufruf erreicht
habe diese hell unterlegten kannten das sind die knoten die ich von einem knoten aussehe also erreichen könnte die zu dem zeitpunkt noch nicht markiert sind alle knoten die markiert sind in dem fall damit auch besucht sind sind dick umrandete auf den folien was man hier noch mal schön sehen ist dass sich durch diesen durchlauf jetzt eine struktur von dicken kanten ergibt und wenn ich die dünnen kannten wir jetzt weg denke wir haben bei der einst angefangen dann kann ich diesen grafen jetzt an der einst aufhängen die einst wird an die wurzeln im baum und was
ich tat was ich dabei bekommen ist tatsächlich eine baumstruktur diese in dem fall so aus und wir werden von einem sogenannten auf spannenden baum sprechen dieser baum ist ein teil traf in diesem kaff und verbindet alle knoten in dem grafen durch kanten miteinander wir haben ja mit der tiefen suche geben alle knoten in dem kranken wenigen in dem grafen aufgezählt und im baum habe ich jetzt die kranken über die ich die entsprechenden knoten erreicht hat wir wissen schon dass wir jeden rezessiven algorithmus auch interaktiv schreiben können dass wir die version durch eine schleife ersetzen können
dabei im allgemeinen eine zusätzliche datenstruktur einen stack benötigen wir haben die aktiven suche im graphen entspricht dem baum den krieg oder joe wilson für das pre order to börsen haben wir uns diese arbeit schon mal gemacht die rezession aufgelöst dementsprechend ist der interaktive algorithmus für die tiefen suche genau der interaktive algorithmus für das pre order los und das neu dazukommt ist das markieren von knoten beziehungsweise das abfragen der markierung und die tatsache dass wir heben nicht zu kindern uns fortbewegen sondern dass wir uns entlang ausgehender kanten bewegen schauen wir uns diese integrative tiefen suche jetzt
von beispielen dass hier wird unser stack wir fangen an nimmt knoten 1 den legen wir auf den stack und wir gehen in die erste generation wir holen diesen knoten umstecken aufeinander farbe zum abstreichen markieren und haben ihn besucht von der einst aus sehen wir die 36 die acht ich zeitig noten wieder in dieser reihenfolge auf und so legt muss er auch auf den stack 13 denn die sex dann die acht und wir sehen wir haben die kannten zwar bei der wecker 7 variante der gleichen reihenfolge aufgezählt aber dann unmittelbar direktion mit der drei gestartet das
heißt wir werden eine andere reihenfolge des durchlaufs bekommen somit einzelner fertig nächste generation wir holen die acht von der 8000 über die einst die schon markiert die 2 und die fünf beide kommen auf den stick auch wieder in der reihenfolge 2 und 5 und das geht in die nächste generation wir holen die fünf vom stack markieren sie besuchen sie bei der nacht vergessen von der 5 aussehen wir die 4 die sechs und sieben alle noch nicht markiert vorsichtig 6 ist schon am start aber wir haben sie noch nicht markiert deswegen kommt sie noch mal auf
dienstag und das machen wir jetzt auch 6 die fünf stunden 467 das ist unser neujahrstag wir holen als nächstes die sieben vom stack von der 7 aussehen wir die fünf dies markiert das männerteam auf die 7 wir sehen die drei die es noch nicht markiert also kommt die auf den stack und das war's dann auch die drei haben hier unten schon auf dem stack aber eben noch nicht markiert nächste generation wir holen die drei vom stack unter 3 aussehen jetzt keinen knoten dem er noch nicht markiert hätten wir holen die sechs vom stack von der
sechs aussehen noch die vier die wir noch nicht markiert haben die einst und die fünf ist markiert die drei habe ich vergessen zu markieren die sechs muss ich auch markieren jedes mal wenn ich ab streich habe ich den knoten besucht und markiert so heise kommt jetzt die vier noch mal auf den stack 362 hier liegt sie schon aber eben in der edition kriegt man sie noch mal drauf und wir gehen in den nächsten schleifen durch kennen wir holen die vier vom stack von der vier aus gibt es keinen knoten mehr zu sehen dennoch nicht markiert
wäre wir haben damit auch markiert und besucht next generation wir holen die vier noch mal vom stack die ist aber schon markiert da passiert nichts wir haben die zwei vom stack hier passiert auch nichts weiter außer dass wir die 2 markieren wir holen die sechs von stec die ist schon markiert hier passiert nichts und wir holen die drei vom stack die es auch schon markiert ihr passiert auch nichts wenn wir also mit dem weg positiven durchlauf vergleichen dann haben wir diesmal zwar auch wieder den tiefen durchlauf aber in einer anderen reihenfolge 1861 macht die 6
aber nicht gestrichen 5 7 6 3 4 2 und alle anderen waren doppelt auf dem stick dieses doppelt auf dem stack liegen dass es was das wird mir gern vermeiden und da zu ändernde den algorithmus ein kleines bisschen und die einzige änderung muss man machen die wir machen müssen ist wir ändern den zeitpunkt wann wir einen knoten markieren das heißt allerdings auch dass das besuchen und das markieren jetzt zwei unterschiedliche aktionen sind also der knoten wird platziert sobald ich ihn das erste mal sehe besucht habe ich ihn dann in einer komplett abgearbeitet und vom stack
genommen würde diese geänderte algorithmus könnte zum beispiel so aussehen und die idee ist dass wir die knoten zu früh wie möglich markieren das bedeutet wir markieren den knoten nicht mehr dann wenn man besucht haben also vollständig abgearbeitet haben sondern wir markieren einen knoten sobald er auf den stick kommt das machen wir gleich beim start knoten wenn man ihn auf den stack legen wird unmittelbar markiert und in unserer schleife auch wieder wenn wir den knoten nach banknoten auf den stack legen wird unmittelbar markiert und ihr betracht dabei nur die nach noten die noch nicht markiert sind
auf die art und weise kann kein knoten auf dem stack lang auf dem stück land und der dort noch ist oder schon mal war gleichzeitig hat sich die bedeutung die semantik von der markierung geändert markieren bedeutet jetzt nicht mehr der knoten ist auch gleichzeitig besucht sondern markieren bedeutet der knoten ist jetzt in bearbeitung im sinn von er liegt auf dem stick oder er ist schon vom stick wieder runden das heißt oder ist vollständig bearbeitet schauen uns das am gleichen beispiel an wir haben wieder einen stack wir fangen wieder mit der einzelnen staates knoten an die
legen auf den stack und markieren sie gehen in die erste generation wir holen die einst von stec geben sie aus ich mag hier die ausgabe jetzt explizit noch mal mit dem türkisen kringe von der eins auf 736 und die acht alle noch nicht passiert also kommen die jetzt der reihe nach auf den stack die 3 wir markieren gleich die 6 und die nächste generation wir wollen die acht vom stack besuchen sie bzw geben aus von der acht aussehen wir die 2 die fünf und die einstige schon markiert das heißt die zwei und die fünf kommen
noch auf den stack die einst markiert ist aber schon wieder vom spektrum also die drei und die sechs liegen schon am stack die 2 kommt dazu wird markiert und die fünf kommt augen obendrauf wird markiert nächste generation wir holen die fünf von stec und geben sie auch unter 5 aussehen die vier die 67 und die acht die vier und sieben sind die einzigen die noch nicht markiert sind die sechs liegt noch im stack die achte schon wieder runden also 36 jährige und die zwei liegen bereits im stack und jetzt kommt die vier neu dazu wird
markiert und die 79 dazu wird auch markiert nächste generation wir wollen die sieben von stec und geben sie aus und s7 aus immer die 3 und die 5 beide sind schon markiert jetzt nichts weiter zu tun wir holen die vier vom stack und geben sie auch von der firma die sechs und die fünf beide sind schon markiert ja nichts weiter zu tun wir haben die zwei von stec und geben sie auch von der zwei ausländer die acht die er schon markiert es gibt nichts weiter zu tun next generation wir haben die sechs vom stack geben
sie auf 0 610 die einst die vier und fünf alle drei schon markiert es gibt nichts zu tun nächste generation junger die drei vom stack und das gleiche spiel es gibt nichts mehr zu tun jetzt ist das deck leer und wir sind fertig wir haben also die knoten in der reihenfolge 1857 4263 ausgegeben die wichtige eigenschaft für uns ist hier allerdings dass wir durch das frühe markieren erreichen dass jeder knoten höchstens einmal auf dem stack liegen kann damit wird man auch wenn der graf in knoten hat dann wird der stack nie höher als in ein
träger sein wir können uns auch hier wieder vorstellen dass wir einen auf spannenden baum erzeugen das heißt wir merken uns für die für jeden knoten von welchem knoten aus berlin erreichte bei der einst angefangen haben die acht mal von der einst aus erreicht die 508 aus von der fünf ausländer die sieben und die vier erreicht die 208 aus erreicht die drei und die 6 ganz am anfang gleich markiert diese mit der einst benachbart das heißt beide haben auch von der einst aus erreicht wenn wir das ganze jetzt am start knoten der einst als wurzel knoten
aufhängen und den baum zeichnen dann sieht er so aus und wenn man noch mal vergleichen mit dem baum den wir bekommen haben durch die rezessive tiefen suche dann ist der hier tatsächlich anders das hat jetzt nicht nur mit der reihenfolge der nachbar kanten zu tun sondern mit der tatsache dass wir früh markieren was wir in der rag kursiven variante so nicht gemacht haben david zimmer meter tiefen suche auch fertig im nächsten teil wollen uns die breiten suche ansehen es wird eine interaktive algorithmus und eine relativ leichte übung denn es geht genauso wie der übergang vom
trio börse zum iterativen level oder zu wissen wir müssen einfach nur die datenstruktur den stack ersetzen durch eine kuh bekomme dann aus statt der tiefen suche eine breiten suche das macht man im nächsten teil