Graphen und Wegsuche — Informatik, 14–17 Jahre
Ein Graph stellt Dinge und ihre Verbindungen dar. Ist ein Problem so gezeichnet, kann ein Computer Wege, Verbindungen oder Abhängigkeiten untersuchen, statt jede Situation als Sonderfall zu behandeln.
Dinge und Verbindungen
In einem Graphen steht ein Knoten für ein Ding und eine Kante für eine Beziehung oder Verbindung. Städte können Knoten und Straßen Kanten sein; Menschen können Knoten und Freundschaften Kanten sein. Kanten können Richtungen oder Gewichte haben, etwa Einbahnstraßen oder Kilometerentfernungen.
Warum einen Graphen zeichnen?
Viele echte Probleme betreffen Verbindungen: Pakete ausliefern, Nachrichten weiterleiten, Freunde vorschlagen oder Aufgaben mit Voraussetzungen ordnen. Listen einzelner Fakten verbergen diese Beziehungen. Graphen geben dem Computer eine gemeinsame Form für Straßen, Websites oder Abhängigkeiten.
Die kürzeste Route wählen
Nehmen wir an: A ist 4 km von B, 1 km von C entfernt, C ist 2 km von B und B 3 km von D entfernt. Direkt von A nach B sind es 4 km, über A–C–B aber 1 + 2 = 3 km. Von A nach D über C und B beträgt die Summe 1 + 2 + 3 = 6 km.
Die wenigsten Schritte sind nicht immer der kürzeste Weg
Es ist naheliegend, nur die Zahl der Verbindungen zu zählen: Zwei Straßen wirken besser als drei. Doch Verbindungen können sehr unterschiedliche Längen, Verzögerungen oder Preise haben. Drei Kanten mit 1 km können besser sein als zwei mit 10 km; der Graph muss also das Wichtige messen.
Graphen außerhalb der Schule
Navigations-Apps verwenden Straßengraphen mit Entfernungen und Verkehrszeiten. Soziale Plattformen nutzen Graphen aus Konten und Beziehungen, während eine Suchmaschine Links zwischen Seiten verfolgt. Das Ergebnis hängt davon ab, was als Verbindung gilt und welches Gewicht zählt: Entfernung, Zeit, Kosten oder Relevanz.
Weiter erkunden
Andere Sprachen
MyLeoNes™ wird geladen…