Was ist ein Graph?
Lektion 2 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Ein Graph ist eine Datenstruktur, die eine Menge von Dingen und die Verbindungen zwischen ihnen modelliert. Die Dinge werden Knoten (oder Vertices) genannt und die Verbindungen werden Kanten (Edges) genannt.
Graphen sind überall. Soziale Netzwerke sind Graphen (Personen sind Knoten, Freundschaften sind Kanten). Straßenkarten sind Graphen (Kreuzungen sind Knoten, Straßen sind Kanten). Das Internet, Abhängigkeitsbäume und Spielkarten sind allesamt Graphen.
In diesem Kurs konzentrieren wir uns auf einen ungerichteten Graphen: Wenn eine Kante u und v verbindet, dann ist v auch mit u verbunden. Es gibt keine Richtung. Wir werden Ganzzahlen (Integers) als Knotenschlüssel verwenden, um die Dinge einfach zu halten.
Intern werden wir den Graphen als Adjazenzliste speichern: eine Map von jedem Knoten zur Liste seiner Nachbarn. Dies macht das Nachschlagen der Nachbarn eines Knotens zu einem einzigen Map-Zugriff, was die meisten Graph-Algorithmen benötigen.
Die Operationen, die wir in unserer Graph-Klasse implementieren werden, sind:
- addVertex: Fügt einen neuen Knoten hinzu, der noch keine Kanten hat.
- addEdge: Verbindet zwei Knoten.
- hasEdge: Prüft, ob zwei Knoten verbunden sind.
- getNeighbors: Ruft die Liste der Nachbarn eines Knotens ab.
- removeEdge: Trennt die Verbindung zwischen zwei Knoten.
- size: Zählt, wie viele Knoten der Graph hat.
Lassen Sie uns eine Graph-Klasse bauen!
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.