{"id":2733,"date":"2010-03-23T19:04:21","date_gmt":"2010-03-23T18:04:21","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2733"},"modified":"2023-05-14T10:18:38","modified_gmt":"2023-05-14T08:18:38","slug":"gemischtes-material-zum-graphendurchlauf-tiefensuche-und-dijkstra","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2010\/03\/gemischtes-material-zum-graphendurchlauf-tiefensuche-und-dijkstra.htm","title":{"rendered":"Gemischtes Material zum Graphendurchlauf (Tiefensuche und Dijkstra)"},"content":{"rendered":"
(5 Kommentare.<\/a>)<\/small> <\/div>\n

Ein Graph ist wie die verkettete Liste<\/a> eine dynamische Datenstruktur. Das ist Stoff im Fach Informatik, 11. Klasse, Bayern.<\/p>\n\n\n\n

Ein Graph ist im eigentlich nur ein Haufen von Punkten, von denen manche miteinander verbunden sind. Die Punkte hei\u00dfen auch Knoten und die Verbindungen Kanten. Ein Graph besteht also aus einer Reihe von Knoten und einer Reihe von Kanten; jede Kante verbindet zwei Knoten, und von jedem Knoten geht eine Anzahl von Kanten weg.<\/p>\n\n\n\n

So einen Graph kritzelt man ganz schnell auf ein Blatt Papier. „Das ist das Haus vom Nikolaus“ ist ein Graph. Die kleine Karte, die man sich bei einem Computerspiel anfertigt, ist ein Graph (jedenfalls bei den Spielen, die ich so spiele).<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n

Mit einem Graph kann man das U- und S-Bahn-Netz M\u00fcnchen modellieren, die Verteilung von Elementen auf einer Leiterplatte, das K\u00f6nigsberger Br\u00fcckenproblem<\/a> oder das Stra\u00dfennetz Deutschlands.<\/p>\n\n\n\n

Wenn man dann so eine Situation als Graph modelliert hat und diesen Graphen vielleicht noch auf die eine oder andere Art in einem Computerprogramm umgesetzt hat, dann will man auch etwas mit ihm anfangen. Den k\u00fcrzesten Weg von einem Knoten zum anderen finden, oder die k\u00fcrzeste Rundreise, bei der man bei jedem Knoten mindestens einmal vorbeigeschaut hat. F\u00fcr diese und \u00e4hnliche Probleme gibt es mehr oder weniger gute Algorithmen, also genaue – und damit leicht in ein Programm umsetzbare – L\u00f6sungsregeln.<\/p>\n\n\n\n

Ein einfaches solches Problem besteht darin, von einem Startknoten aus alle anderen erreichbaren Knoten zu besuchen und dabei keinen zu \u00fcbersehen. Ein einfacher Algorithmus dazu hei\u00dft „Tiefensuche“, und der steht explizit im Lehrplan. Die Tiefensuche erkl\u00e4re ich hier nicht; ich will nur die Aufzeichnung einer Pr\u00e4sentation dazu zeigen, die ich mal angefertigt aber nie benutzt habe. Die Idee f\u00fcr die H\u00f6hlenerkundung als Beispiel der Tiefensuche habe ich aus dem Buch
Informatik. Rekursive Datenstrukturen, Softwaretechnik. Sch\u00fclerbuch 11. Klasse<\/em> von Peter Hubwieser, Patrick L\u00f6ffler und Petra Schwaiger (bei Klett).<\/p>\n\n\n\n

\nhttps:\/\/www.youtube.com\/watch?v=2Fnz1atRBY\n<\/div><\/figure>\n\n\n\n

(Herunterladen als – etwas schlampig geschriebene – Open-Officen-Datei.)<\/a><\/p>\n\n\n\n

Andere Algorithmen zum Durchlauf eines Graphen sind etwa die Breitensuche oder der Dijkstra-Algorithmus<\/a>. Auch den will ich hier nicht gro\u00df erkl\u00e4ren, obwohl er ziemlich wichtig ist.Ich habe ihn zuerst nicht verstanden, obwohl ich die Erkl\u00e4rung im Buch gelesen habe. Daraufhin habe ich den Algorithmus nach und nach umgeformt, auf Papier gekritzelt, zusammengefasst, und neu f\u00fcr mich formuliert. Dann hatte ich ihn verstanden. Und als ich meine Formulierung mit der im Buch verglich, sah ich, dass da ziemlich genau das gleiche stand.<\/p>\n\n\n\n

Mit dem Dijkstra-Algorithmus lassen sich effizient nicht nur irgendwelche Wege im Graphen finden (wie bei der Tiefensuche), sondern jeweils die k\u00fcrzesten Wege von einem Startpunkt aus zu allen anderen Punkten. Auch dazu gibt es eine Pr\u00e4sentation. Das muss wohl so sein, davon gibt es bei Youtube schon so viele, aber jeder Informatiklehrer muss irgendwann mal seine eigene machen:<\/p>\n\n\n\n

\n