Зачем говорить, что поиск в ширину выполняется во времени

9

Часто утверждается (например, в Википедии ), что время выполнения поиска в ширину (BFS) на графе G=(V,E) равно O(|V|+|E|) . Тем не менее, любой связный граф имеет |V||E|+1 , и даже в несвязном графе, BFS никогда не будет смотреть на вершинах вне компонента , который содержит начальную вершину. Этот компонент содержит максимум |E| ребра, поэтому он содержит не более |E|+1 вершина, и это единственные, которые посещает алгоритм.

Это означает, что |V|+|E|2|E|+1 , так почему бы не сказать , что время работает только O(|E|) ?

Это появилось в комментариях на вопрос о времени выполнения алгоритма Дисйкстры .

Дэвид Ричерби
источник
Почему вы предполагаете, что есть начальная вершина? Например, BFS в задаче максимального соответствия начинается со всех несопоставленных вершин в алгоритме hopcroft karp. В этом случае, если данный граф представляет собой лес из многих связанных компонентов, у нас будет больше вершин, чем у edgers, и мы посетим их все
Нарек Божикян
2
@narekBojikian Хотя BFS можно использовать по-разному, при представлении в качестве автономного алгоритма она почти всегда имеет начальную вершину.
Дэвид Ричерби,

Ответы:

9

BFS обычно описывается примерно так (из Википедии ).

 1  procedure BFS(G,start_v):
 2      let Q be a queue
 3      label start_v as discovered
 4      Q.enqueue(start_v)
 5      while Q is not empty
 6          v = Q.dequeue()
 7          if v is the goal:
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered:
11                 label w as discovered
12                 w.parent = v
13                 Q.enqueue(w)

Проблема несколько тонкая: она прячется в строке 3! Вопрос в том, какую структуру данных мы будем использовать для хранения обнаруженных вершин.

Самое простое решение - использовать логический массив с одной записью на вершину. В этом случае мы должны инициализировать каждый элемент массива, falseи это занимает время Θ(|V|) . Это применимо для каждого графа, даже если ребер нет вообще, поэтому мы не можем предполагать какую-либо связь между |V|и  |E|и мы получаем время работы O(|V|+|E|) .

Можем ли мы избежать структуры данных со временем инициализации Θ(|V|) ? Нашей первой попыткой может быть использование связанного списка. Однако теперь проверка того, была ли обнаружена вершина (строка 10), занимает линейное время по числу посещенных вершин, а не постоянное время, как раньше. Это означает, что время выполнения становится O(|V||E|) , что намного хуже в худшем случае. (Обратите внимание, что мы не хотим переписывать это какO(|E|2) так как это еще хуже: это может быть так же плохо, как|V|4 , тогда как|V||E||V|3

O(log|V|)O(|E|log|V|)

c|E|+1c+2c+4c++2|E|4|E|, Поиски и вставки в хеш-таблицу амортизируются O(1) поэтому мы действительно получаем время выполнения O(|E|) .

O(|E|)4|E|O(|E|)O(|V|+|E|)

Дэвид Ричерби
источник
1
Я думаю, что это может быть слишком сильным, чтобы утверждать, что хеш-таблицы на практике имеют низкую производительность кеша. Если реализовано с цепочкой (т.е. связанных списков), я согласен. Но если реализовано с непрерывной порцией памяти и открытой адресацией, не так уж и много.
Юхо
Чудесный ответ действительно! Однако следует отметить, что хеш-таблицы динамического размера действительно хороший выбор не только при наличии множества мелких компонентов, но и в том случае, если значение хеш-функции для любой вершины ограничено разумной константой, и это часто случается. Хороший ответ!
Карлос Линарес Лопес
1
Дэвид, у меня были похожие мысли много лет назад. Я думаю, что ответ лежит в исторических перспективах.
Келалака