Multigraph und Adjazenzliste

Question

Ich habe ein Problem, das als Multigraph dargestellt werden kann. Um diesen Graph intern darzustellen, denke ich an eine Matrix. Ich mag die Idee einer Matrix, weil ich die Anzahl der Kanten für einen Eckpunkt zählen möchte. Dies wäre O (n) time, weil ich nur die richtige Spalte durchlaufen müsste, so dass die Zeitkomplexität linear zur Menge der Scheitelpunkte im Graphen wäre, oder? JEDOCH denke ich auch an die Raumkomplexität. Wenn dieser Graph wachsen würde, könnte viel Platz verschwendet werden. Dies führt mich dazu, eine Adjazenzliste zu verwenden. Dies mag zwar meine räumliche Komplexität verringern, klingt aber so, als wäre meine Zeitkomplexität gerade gestiegen. Wie würde ich die Zeitkomplexität darstellen, wenn ich die Anzahl der Kanten für einen bestimmten Knoten bestimmen möchte? Ich weiß, dass die Operation zuerst den Scheitel finden würde, also wäre diese Operation O (n), aber dann müsste ich auch die Liste der Kanten scannen, die auch O (n) sein könnte. Bedeutet dies, dass meine Zeitkomplexität für diese Operation O (n^2) ist?

EDIT:

Ich denke, wenn ich einen HASH-Tabelle verwenden waren, die erste Operation wäre O (1), so dass mein Betrieb bedeutet Anzahl der Kanten zu finden für einen Scheitelpunkt ist O (n)?

Answer 1

Es wird O (| e |), | e | sein kann O (| v | ** 2) sein, aber Sie möchten die Adjazenzliste verwenden, da die Matrix spärlich ist, also | e | < < | v | Also ist es besser, O (| e |) zu sagen.