Dlaczego złożoność czasu zarówno DFS, jak i BFS O (V + E)
Podstawowy algorytm 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
Sądzę więc, że złożoność czasu to:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
gdziev
jest wierzchołek1
don
Po pierwsze, czy to, co powiedziałem, jest poprawne? Po drugie, jak to jestO(N + E)
i intuicja, dlaczego byłby naprawdę miły. Dzięki