Bin ich richtig, warum insertVertex würde O(1) und deleteVertex würde O(m) hier nehmen?

Question

Für eine Hausaufgabe wurde mir die Frage gestellt, warum bei einer Menge von n Knoten und m Kanten, wobei der Graph durch eine Adjazenzliste dargestellt wurde, insertVertex O(1) und deleteVertex O(m) benötigen würde.

Ich bin mir meiner Antwort nicht ganz sicher, aber ich vermute, dass insertVertex O(1) ist, weil beim ersten Einfügen nur ein Knoten und ein Satz benachbarter Scheitelpunkte (d. h. Scheitelpunkte, auf die der neue Knoten zeigt) zum Array hinzugefügt werden. Diese Zeitkomplexität ist also konstant. Wenn Sie jedoch einen Knoten entfernen, müssen Sie nicht nur den Knoten und die benachbarten Kanten entfernen, die mit dem Knoten einhergehen, sondern auch die restlichen m Kanten durchgehen, um sicherzustellen, dass Sie diejenigen entfernen, die auf den zu entfernenden Knoten zeigen (da Sie keine Kante haben können, die auf nichts zeigt).

Ich bin neu in der Graphentheorie, daher weiß ich nicht, ob meine Denkweise richtig ist.

Answer 1

Die O(m)-Erklärung ist richtig.

Ihre Erklärung wäre besser, wenn Sie die Aktionen in Form von verknüpften Listenmanipulationen erklären würden. Es dauert O(1) Zeit, einen Knoten an eine verknüpfte Liste anzuhängen. Und es braucht O(n) Zeit, um ein Element zu löschen.

a) Warum ist insertVertex O(1)?

Das Einfügen eines Knotens ist nichts anderes als das Anhängen eines Knotens an eine verknüpfte Liste (O(1)) oder 2, wenn der Graph ungerichtet ist.

b) Warum ist deleteVertex O(m)?

Einen Scheitelpunkt zu löschen bedeutet:

1) Löschen einer verknüpften Liste (O(1))

2) Im schlimmsten Fall müssen Sie den Scheitelpunkt aus allen verknüpften Listen entfernen: O(m). Es ist O(m), weil die Anzahl der Knoten in allen verknüpften Listen m ist, oder 2*m, wenn der Graph ungerichtet ist.

Answer 2

InsertVertex benötigt O(1), da Sie nur ein neues Element am Ende Ihrer Datenstruktur hinzufügen.

deleteVertex benötigt O(m), da für jede Kante geprüft werden muss, ob sie auf den Scheitelpunkt zeigt oder von ihm weg zeigt (wenn G gerichtet ist).

Wenn ich mir Ihren OP so ansehe, haben Sie die Idee schon verstanden.