Базовый алгоритм для 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
Поэтому я бы подумал, что временная сложность будет такой:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
где v
вершина 1
кn
Во-первых, правильно ли я сказал? Во-вторых, как это O(N + E)
, и интуиция относительно того, почему это было бы действительно хорошо. Спасибо
ДФС (анализ):
O(1)
времениO(n + m)
времени, если граф представлен структурой списка смежностиΣv deg(v) = 2m
BFS (анализ):
Li
O(n + m)
времени, если граф представлен структурой списка смежности.Σv deg(v) = 2m
источник
Очень упрощено без особых формальностей: каждое ребро рассматривается ровно дважды, и каждый узел обрабатывается ровно один раз, поэтому сложность должна быть постоянной, кратной количеству ребер, а также количеству вершин.
источник
Сложность времени
O(E+V)
вместо этого,O(2E+V)
потому что, если сложность времени равна n ^ 2 + 2n + 7, то она записывается как O (n ^ 2).Следовательно, O (2E + V) записывается как O (E + V)
потому что разница между n ^ 2 и n имеет значение, но не между n и 2n.
источник
Я думаю, что каждое ребро было рассмотрено дважды и каждый узел был посещен один раз, поэтому общая временная сложность должна быть O (2E + V).
источник
Интуитивно понятное объяснение этому заключается в простом анализе одного цикла:
Таким образом, общее время для одного цикла составляет O (1) + O (e). Теперь просуммируйте его для каждой вершины, поскольку каждая вершина посещается один раз. Это дает
источник
Краткое, но простое объяснение:
источник