so jetzt haben wir bfs uns angeschaut wie das funktioniert jetzt wird es zeit zu beweisen dass

dieser algorithmus wirklich das tut was er verspricht im algorithmus also in der händischen

ausführung haben wir gesehen dass es nicht funktioniert aber unser ziel ist jetzt bei bfs

den beweis sind bekommen dass er kürzeste fahnen liefert fahnen von s überall hin das

ist eine sehr schöne übung im umgang mit der mit dem beweis so korrekt von algorithmen

das ist am anfang ein bisschen ungewohnt aber mathematisch gesehen passiert nicht so viel

es ist nur man muss die ganze überblick behalten welchem schritt des algorithmus sind wir gerade

und wir fangen jetzt an mit einer laufzeitanalyse das heißt wir wollen uns überlegen wie lange

braucht dieser algorithmus und er zu beweisen folgendes lemma nämlich dass die laufzeit

von bfs proportional ist zu der summe der anzahl der knoten und der anzahl der kanten also

angenommen wir haben drei knoten und zwei kanten dann ist die laufzeit proportional

zu fünf also wenn wir die anzahl von knoten verdoppeln verdoppelt sich dieser anteil über

die anzahl von kanten verdoppeln verdoppelt sich dieser anteil zum beispiel jetzt woran

liegt das also die initialisierung schon was hier mal an was passiert hat da wird zu jedem

knoten etwas gemacht und dann wird noch mit dem einen knoten was anderes gemacht also

weil alles hier passiert das ist jetzt hier eskaliert mit der anzahl der knoten wenn wir

doppelt so viele knoten nehmen passiert hier die initialisierung genau doppelt so viel

so entsteht dieser anzahl von v-beitrag hier und alles andere funktioniert so also diese

hauptschleife die schaut sich eingereite knoten an und wir wissen dass jeder knoten der von

s aus erreichbar ist genau einmal im q eingereitet und dann genau einmal ausgereitet das wissen

wir wegen der farben jeder knoten aus der s ist dann weiß der wird dann eingereitet

dadurch wird er grau dann wird er ausgereitet dadurch wird er schwarz und dieser schwarze

knoten wird niemals wieder weiß deswegen wird er nie wieder in diese laufzeit lange

eingereitet das heißt jeder knoten kommt genau einmal rein und alle operationen die

jetzt hier das ein rein betreffen ja die kommen genau einmal pro knoten vor pro erreichbar

knoten also weniger als die anzahl der knoten das heißt laufzeit dieser operation ist auch

prozents zu maximal anzahl von also maximal prozents anzahl von knoten wie gesagt es

könnte ein bisschen weniger sein weil knoten die von s aus nicht erreichbar sind also zum

beispiel bis zum mal gerichtete knoten haben und wir starten mit diesem s hier dann sind

diese beiden knoten hier nicht erreichbar von s das heißt die tauchen gar nicht auf

das heißt in der in diesem setting ist sehen wir gar nicht alle knoten deswegen ist es

hier weniger als alle operationen die bezieht sich auf diese durchsuchung von adjenzlisten

also hier schauen wir uns an und gehen einmal so eine komplette adjenzliste durch jetzt wissen

wir aber jede adjenzliste wird nur einmal durchsucht weil jeder knoten kommt nur einmal

rein in diese schleife und es wird ja immer nur das vordere element der kopf der warteschlange

wird entnommen das nur die adjenzliste durchsucht und dann wird das objekt weggelegt und nie

wieder durchsucht das heißt hier schauen uns von jedem objekt ist erreicht heißt einmal

komplett die adjenzliste und die alle adjenzlisten zusammen sind auf jeden fall eine teilmenge

aller kanten das heißt die die summe aller operationen die sich auf diese adjenzliste beziehen ist maximal die

menge aller kanten weil jede kante kommt in so eine adjenzliste vor aber jeder knoten wird nur einmal durchsucht

die adjenzliste wird einmal abgelaufen und damit ist jetzt hier also die die summe aller adjenzlisten

von u bei alle u und v das ist gleich der häufigkeit von e aber weil nicht alle knoten

vor sich von s erreicht werden können ist die anzahl der betrachteten objekte in diesen adjenzlisten

sogar kleiner möglich ist das heißt wir haben es hier einen anteil der es prozents zu v

ein anteil des prozents zu e und damit ist jetzt hier die summe aller operationen die skaliert mit

der summe der anzahl von e und der anzahl von v es war jetzt sehr sehr formal und so weiter also man

kann sich jetzt ein bisschen exakter machen dazu würde man die sogenannte pro notation einführen

ich weiß nicht ob sie das informatik schon gemacht haben ich wollte es jetzt nicht extra

einführen weil uns die laufzeit an den folgenden auch kaum interessieren wird aber das sollte

im kurs überblick geben wie man die laufzeit von algorithmen in abhängigkeit von den parametern