Algorithmen und Datenstrukturen · Junior · Frage 57 von 75
Wie speichert man einen Graphen meist, wenn er viele Knoten, aber wenige Kanten hat?
- 1Als n × n-Matrix voller Nullen und Einsen
- 2Als ein sortiertes Array mit allen Knoten
- 3Als Adjazenzliste: jeder Knoten mit seinen Nachbarn
Antwort zeigen
Richtige Antwort: Als Adjazenzliste: jeder Knoten mit seinen Nachbarn
Erklärung
Eine Adjazenzliste braucht O(V + E) Speicher, eine Matrix immer O(V²), was bei dünnen Graphen verschwenderisch ist. Die Matrix ist praktisch, wenn der Graph dicht ist oder man eine O(1)-Prüfung „gibt es eine Kante?“ braucht.