Graphen: Punkte, Linien und was sie bedeuten
Ein Graph besteht aus Punkten, die durch Linien verbunden sind — und dasselbe Bild kann Freunde, Straßen oder eine Build-Reihenfolge beschreiben.
Ein Graph ist zweierlei: eine Menge von Knoten (die Punkte) und eine Menge von Kanten (die Linien, die sie verbinden). Das ist die ganze Definition. Die Stärke liegt darin, was du die Punkte und Linien bedeuten lässt, denn dieselbe Struktur beantwortet dann gleichzeitig Fragen zu Freunden, Städten, Computern und Aufgaben.
Knoten und Kanten — was dasselbe Bild bedeuten kann: menschen - knoten = Person, kante = „ist befreundet mit“ familie - knoten = Person, kante = „ist Elternteil von“ karten - knoten = Stadt, kante = Straße dazwischen netze - knoten = Computer, kante = Kabel oder Wi-Fi bauplan - knoten = Aufgabe, kante = „muss danach laufen“ Gerichtete Kante: A -> B ist nicht dasselbe wie B -> A. „ist Elternteil von“ ist gerichtet. „ist befreundet mit“ ist es nicht.
Ein Baum ist ein Graph ohne Schleifen: Zwischen zwei beliebigen Knoten führt genau ein Weg, und es gibt immer einen Knoten, den man Wurzel nennen kann. Ordnerstrukturen, Stammbäume und K.-o.-Turniere sind alle Bäume. Sobald ein Weg wieder dort ankommen kann, wo er begonnen hat, ist es kein Baum mehr.
Praxis
Ordne jede Situation dem zu, was ein Knoten und eine Kante darin bedeuten.
Hinweise
- Frag dich, was ein einzelner Schritt zwischen zwei Dingen in der jeweiligen Situation bedeutet.
- In einer Bauanleitung sagt der Pfeil, was zuerst passieren muss, nicht was ähnlich ist.
13 XP
Du kannst von Tom zu Ana gehen, dann von Ana zu Lena und außerdem direkt von Lena zurück zu Tom. Was ist dieser Graph?
Hinweise
- Ein Baum hat überhaupt keine Schleifen — wenn du im Kreis laufen kannst, ist es kein Baum.
- In einer Familie gehst du zu einem gemeinsamen Elternteil hinauf und dann wieder hinunter.
14 XP
Zeichne den Build-Graphen: Die Datenbank muss fertig sein, bevor der API-Server startet, der Cache muss fertig sein, bevor der API-Server startet, und das Frontend muss fertig sein, bevor der API-Server startet. Erst nach dem API-Server geht die Seite live.
Hinweise
- Zeichne für jede Regel der Beschreibung, die mit "muss vorher fertig sein" beginnt, einen Pfeil.
- Die Maschine, von der alles abhängt, steht zwischen diesen dreien und dem letzten Schritt.
18 XP