Algorithmen und Datenstrukturen · Senior · Frage 72 von 75
Was ist der Hauptgrund, eine Adjazenzmatrix Adjazenzlisten vorzuziehen?
- 1Schnelleres Durchlaufen aller Nachbarn
- 2Weniger Speicher bei dünnen Graphen
- 3Kantenprüfungen in O(1) bei dichten Graphen
Antwort zeigen
Richtige Antwort: Kantenprüfungen in O(1) bei dichten Graphen
Erklärung
matrix[u][v] zu prüfen geht sofort, und bei dichten Graphen ist der O(V²)-Speicher nicht verschwendet. Bei dünnen Graphen gewinnen Listen bei Speicher und Iteration über Nachbarn.