Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Okay, ich würde sagen, wir fangen an. Also der Professor Martin ist heute auf einem Workshop,

deswegen werde ich nochmal die Vorlesung vertreten. Also worum geht es heute? Also ihr habt letzte

Woche ja zum ersten Mal mit Grafen zu tun gehabt. Also ihr wisst jetzt, was ein Graf ist. Ihr habt

so paar Eigenschaften von Grafen kennengelernt. Ihr wisst, wie man Grafen abspeichert. Und ihr habt

schon mal ein bisschen was über Algorithmen gehört. Und die beiden Sachen wollen wir jetzt

verknüpfen. Heute geht es darum, also die ersten Algorithmen auf Grafen, also für Grafenprobleme

kennenzulernen. Ja, was es da so gibt und wie sie funktionieren. Und wir fangen an mit so den

einfachsten Algorithmen, die es gibt. Das sind Suchalgorithmen auf Grafen.

Also wir haben einen Grafen gegeben. Es kann auch ein gerichteter sein, aber wir gehen jetzt

erstmal von ungerichteten Grafen aus. Und auf diesen Grafen wollen wir jetzt Fragen beantworten,

wie gibt es einen Weg vom Knoten U zum Knoten V? Welche Knoten kann man von einem bestimmten

Knoten aus erreichen oder wie viele Zusammenhangskomponenten gibt es überhaupt in

diesem Grafen?

Okay, also Zusammenhangskomponenten kürze ich immer mit ZSH ab. Das ist kürzer als das immer

aufzuschreiben. Ich weiß nicht, ob der Professor Martin hat letzte Woche gesagt,

was Zusammenhangskomponenten sind. Also wenn man Grafen hat, der ist ja zusammenhängt,

wenn zwischen je zwei Knoten ein Weg existiert und er kann halt aus verschiedenen Zusammenhangskomponenten

bestehen. Das sind dann quasi die Teilgrafen, die jeweils zusammenhängen sind. Also wenn man

dies Ganze jetzt als einen Grafen sieht, dann wäre das halt eine Zusammenhangskomponente und das wäre

eine zweite Zusammenhangskomponente. Also dieser Graf hat jetzt zwei Zusammenhangskomponenten.

Und ja, eine von diesen Fragen wäre halt dann, wie viele Zusammenhangskomponenten hat unser Graf

denn überhaupt? So, diese drei Fragen kann man mit der sogenannten Tiefensuche oder der Breitensuche

lösen. Und da stelle ich jetzt mal vor, wie das geht.

Also die Tiefensuche und die Breitensuche sind streng genommen zwei Algorithmen. Also einmal die

Tiefensuche ist einer und der Breitensuche ist ein anderer Algorithmus. Die sind aber sehr ähnlich

zueinander und deswegen schreibe ich sie jetzt hier mal einfach zusammen auf und wir gucken dann

gleich mal, was der Unterschied zwischen diesen beiden Algorithmen ist. Eine kleine Anmerkung,

ich mache das jetzt ein bisschen anders als im Skript. Also ich finde, die Notation, die da im

Skript für diese beiden Algorithmen ist, ist etwas kompliziert. Ich mache es jetzt ein bisschen

einfacher. Der Algorithmus macht genau das gleiche, aber ich denke, es ist jetzt ein bisschen

verständlicher, so wie ich es gleich aufschreiben will und das ist vielleicht den ersten Algorithmus,

den ihr jetzt so seht, ja vielleicht ein bisschen netter, wenn er nicht gleich so kompliziert aussieht.

Also Eingabe ist irgendwie ein Graf und ein Knoten in diesem Graf. Und diesen Knoten nenne

ich jetzt mal S. Und die Ausgabe, also das, was wir jetzt berechnen wollen, sind all die Knoten,

die von S aus erreichbar sind, also sprich, für die es einen Weg gibt von S aus.

Und diese Menge nenne ich mal R. So, wie funktioniert dieser Algorithmus jetzt? Also

als erstes initialisieren wir mal einige Mengen. Also in diese Menge R, das ist also die Menge,

die ich nachher ausgeben will, wo also quasi alle Knoten drin sind, die ich erreichen kann.

Da tue ich am Anfang nur das S rein. Na, also das ist ja schon mal klar, von S komme ich nach S.

Also den kann ich auf jeden Fall schon mal reinrufen. Ich mache mir so noch so eine Hilfsmenge,

die nenne ich Q. Da kommt auch mein S rein. Und ich mache mir eine Hilfsmenge T, die ist

erstmal R. Wofür stehen diese Mengen? Also R ist wie gesagt unsere Ausgabe, das ist die Teilmenge

alle von S erreichbaren Knoten. Diese Menge Q, das seht ihr gleich erst im Algorithmus,

für die wirklich gut ist. Ich nenne sie mal Liste aktueller Knoten. Da speichern wir gleich die

Knoten drin, die wir schon abgearbeitet haben, also sprich, wo wir schon hingelaufen sind und von

denen wir nicht mehr weiter laufen können. Und unser T, das wird unser Wegeteilgrad. Das braucht man

jetzt vielleicht nicht unbedingt, aber wenn man jetzt nicht nur die Teilmenge aller Knoten haben

will, sondern auch wissen will, wie komme ich denn zu diesen Knoten hin, also sprich, was sind denn

meine Wege, die speichere ich dann in diesem T ab. So, das war unser erster Schritt, die Initialisierung.