Warum ist die zeitliche Komplexität von DFS und BFS O (V + E)
Der grundlegende Algorithmus für BFS:
set start vertex to visited
load it into queue
while queue not empty
for each edge incident to vertex
if its not visited
load into queue
mark vertex
Ich würde also denken, die zeitliche Komplexität wäre:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
woherv
ist Vertex1
zun
Erstens ist das, was ich gesagt habe, richtig? Zweitens, wie ist das?O(N + E)
und die Intuition, warum das wirklich nett wäre. Vielen Dank