Mit Google fortfahren
Wenn du eine Route zur Schule suchst, denkst du selten an Informatik. Trotzdem steckt dahinter oft ein Netz aus Orten und Verbindungen. Computer brauchen dafür genaue Regeln, damit sie nicht einfach irgendwie suchen.
- Du verstehst, was ein Graph ist.
- Du erkennst Knoten, Kanten, Pfade und Gewichte.
- Du kannst erklären, wofür Graphenalgorithmen benutzt werden.
- Du unterscheidest Breitensuche, Tiefensuche und Dijkstra.
- Du prüfst einfache Aufgaben zu Wegen in Graphen.
Vom Netz zum Graphen
Stell dir einen U-Bahn-Plan vor. Die Stationen sind wichtige Punkte. Die Linien dazwischen zeigen, wo du direkt weiterfahren kannst.
Ein Graph ist ein Modell für solche Netze. Ein Modell ist eine vereinfachte Darstellung der Wirklichkeit. Beim Graphen interessieren uns vor allem Punkte und Verbindungen.
Ein Knoten ist ein Punkt im Graphen. Er kann zum Beispiel eine Stadt, eine Person, eine Webseite oder ein Computer sein. Eine Kante ist eine Verbindung zwischen zwei Knoten. Sie zeigt, dass zwei Knoten direkt zusammenhängen.
Ein Graph besteht aus Knoten und Kanten. Knoten sind die Punkte. Kanten sind die Verbindungen zwischen den Punkten.
Ein kleines Schulnetz:
Knoten: Schule, Bahnhof, Sporthalle, Bibliothek
Kanten: Schule - Bahnhof Schule - Sporthalle Bahnhof - Bibliothek Sporthalle - Bibliothek
Du kannst von der Schule zur Bibliothek gehen. Eine Möglichkeit ist: Schule - Bahnhof - Bibliothek.
Ein Graph fragt nicht zuerst, wie etwas aussieht. Er fragt: Was ist verbunden?
Interaktive Quizfrage wird geladen ...
Wege, Richtung und Gewicht
Wenn du in einem Netz von einem Punkt zum anderen kommst, benutzt du einen Pfad. Ein Pfad ist eine Folge von Knoten, bei der jeder nächste Knoten durch eine Kante erreichbar ist.
Manche Kanten haben eine Richtung. Ein gerichteter Graph hat Kanten, die nur in eine Richtung gelten. Das passt zum Beispiel zu Einbahnstraßen oder Links auf Webseiten. Ein ungerichteter Graph hat Kanten ohne feste Richtung. Dann kannst du die Verbindung in beide Richtungen nutzen.
Manche Kanten haben außerdem ein Gewicht. Ein Gewicht ist eine Zahl an einer Kante. Sie kann Entfernung, Zeit, Kosten oder Schwierigkeit bedeuten.
Gerichteter Graph:
Start -> Aufgabe Aufgabe -> Lösung
Das bedeutet: Du gehst erst von Start zu Aufgabe und dann zur Lösung. Zurück geht es nur, wenn es auch eine passende Rückkante gibt.
Gewichteter Graph:
Schule - Bahnhof: 4 Minuten Schule - Sporthalle: 7 Minuten Bahnhof - Bibliothek: 5 Minuten
Dann ist Schule - Bahnhof - Bibliothek insgesamt 9 Minuten lang.
Bei einem ungewichteten Graphen zählt oft nur, wie viele Kanten du benutzt. Bei einem gewichteten Graphen zählt die Summe der Gewichte.
Interaktiver Lückentext wird geladen ...
Interaktive Quizfrage wird geladen ...
Was ein Graphenalgorithmus macht
Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, die ein Problem löst. Ein Graphenalgorithmus ist ein Algorithmus, der auf einem Graphen arbeitet.
Er beantwortet Fragen wie: Welche Knoten sind erreichbar? Was ist der kürzeste Weg? Gibt es einen Kreis? Welche Knoten gehören zusammen? Welche Verbindung ist besonders wichtig?
Das ist nützlich, weil viele echte Probleme wie Netze aussehen. Routenplanung, soziale Netzwerke, Paketlieferung, Computernetze und Stundenplan-Abhängigkeiten lassen sich als Graph beschreiben.
Ein Graphenalgorithmus ist ein Verfahren, das Knoten und Kanten systematisch untersucht, um eine Frage über den Graphen zu beantworten.
Aufgabe: Finde heraus, ob du von der Schule zur Bibliothek kommst.
Graph: Schule - Bahnhof Bahnhof - Bibliothek Sporthalle - Mensa
Der Algorithmus startet bei Schule. Er findet Bahnhof. Von Bahnhof findet er Bibliothek. Also ist Bibliothek erreichbar.
Erst modellierst du die Situation als Graph. Dann wählst du den passenden Graphenalgorithmus.
Interaktive Lernkarten wird geladen ...
Interaktive Quizfrage wird geladen ...
Breitensuche und Tiefensuche
Wenn ein Computer ein Netz absucht, braucht er eine Reihenfolge. Zwei wichtige Suchverfahren heißen Breitensuche und Tiefensuche.
Die Breitensuche besucht zuerst alle Knoten, die direkt neben dem Startknoten liegen. Danach besucht sie die Knoten mit zwei Schritten Entfernung, dann drei Schritte und so weiter. In einem ungewichteten Graphen findet sie dadurch einen Weg mit möglichst wenigen Kanten.
Die Tiefensuche folgt erst einem Weg so weit wie möglich. Wenn sie nicht weiterkommt, geht sie zurück und probiert eine andere Kante. Sie eignet sich gut, um Strukturen zu entdecken, zum Beispiel ob ein Graph zusammenhängt oder ob es Kreise gibt.
Graph: A - B A - C B - D C - E
Start bei A.
Breitensuche besucht zuerst B und C. Danach D und E.
Tiefensuche könnte A, B, D besuchen. Dann geht sie zurück und besucht C, E.
Breitensuche denkt in Entfernungsstufen. Tiefensuche folgt erst einem Weg in die Tiefe.
Interaktiver Lückentext wird geladen ...
Interaktive Quizfrage wird geladen ...
Kürzeste Wege mit Dijkstra
Manchmal reicht die Anzahl der Kanten nicht. Eine Strecke mit einer Kante kann sehr lang sein. Zwei kurze Strecken können zusammen schneller sein.
Der Dijkstra-Algorithmus findet kürzeste Wege in einem gewichteten Graphen, wenn die Gewichte nicht negativ sind. Nicht negativ bedeutet: Die Gewichte sind null oder größer. Der Algorithmus merkt sich zu jedem Knoten die bisher beste bekannte Entfernung vom Start.
Er beginnt beim Start mit Entfernung 0. Dann wählt er immer den noch nicht endgültig erledigten Knoten mit der kleinsten bekannten Entfernung. Von dort prüft er, ob Nachbarn über diesen Knoten günstiger erreichbar sind.
Kanten mit Zeiten:
A - B: 2 A - C: 6 B - C: 1 B - D: 5 C - D: 2
Start ist A.
Direkt nach C kostet 6. Über B kostet es 2 plus 1, also 3. Deshalb ist A - B - C besser als A - C.
Nach D kostet A - B - D insgesamt 7. Über C kostet A - B - C - D insgesamt 5. Der kürzeste Weg nach D ist also A - B - C - D.
Dijkstra ist kein Raten. Er verbessert bekannte Entfernungen Schritt für Schritt und legt Knoten fest, sobald ihre beste Entfernung sicher ist.
Interaktive Quizfrage wird geladen ...
Typische Aufgaben und Denkweg
Bei Graphenalgorithmen ist der erste Schritt fast immer: Übersetze die Aufgabe sauber in einen Graphen. Danach entscheidest du, welche Frage wirklich gestellt wird.
Frage dich: Was sind die Knoten? Was sind die Kanten? Gibt es Richtungen? Gibt es Gewichte? Suche ich Erreichbarkeit, wenige Kanten oder geringe Kosten?
Aufgabe: Eine App soll den schnellsten Schulweg finden.
Knoten: Kreuzungen und Haltestellen. Kanten: Straßen oder Fahrverbindungen. Gewichte: Fahrzeit oder Gehzeit. Passender Algorithmus: Dijkstra, wenn alle Zeiten nicht negativ sind.
Die App sucht dann nicht den Weg mit den wenigsten Straßen. Sie sucht den Weg mit der kleinsten Gesamtzeit.
Interaktive Mindmap wird geladen ...
Die wichtigste Frage lautet nicht: Welchen Algorithmus kenne ich? Die wichtigste Frage lautet: Welche Graphenfrage steckt in der Aufgabe?
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Ein Graph ist ein Netz aus Knoten und Kanten. Knoten stehen für Dinge wie Orte, Personen oder Webseiten. Kanten stehen für direkte Verbindungen zwischen ihnen.
Ein Pfad ist ein möglicher Weg durch den Graphen. Kanten können gerichtet sein und Gewichte haben. Gewichte beschreiben zum Beispiel Zeit, Länge oder Kosten.
Ein Graphenalgorithmus untersucht einen Graphen nach festen Schritten. Breitensuche findet in ungewichteten Graphen Wege mit möglichst wenigen Kanten. Tiefensuche verfolgt Wege in die Tiefe und hilft beim Erkunden der Struktur. Dijkstra findet kürzeste Wege in gewichteten Graphen mit nicht negativen Gewichten.
Interaktive Quizfrage wird geladen ...