Часто утверждается (например, в Википедии ), что время выполнения поиска в ширину (BFS) на графе равно . Тем не менее, любой связный граф имеет , и даже в несвязном графе, BFS никогда не будет смотреть на вершинах вне компонента , который содержит начальную вершину. Этот компонент содержит максимум ребра, поэтому он содержит не более вершина, и это единственные, которые посещает алгоритм.
Это означает, что , так почему бы не сказать , что время работает только ?
Это появилось в комментариях на вопрос о времени выполнения алгоритма Дисйкстры .
algorithm-analysis
search-algorithms
Дэвид Ричерби
источник
источник
Ответы:
BFS обычно описывается примерно так (из Википедии ).
Проблема несколько тонкая: она прячется в строке 3! Вопрос в том, какую структуру данных мы будем использовать для хранения обнаруженных вершин.
Самое простое решение - использовать логический массив с одной записью на вершину. В этом случае мы должны инициализировать каждый элемент массива,Θ(|V|) . Это применимо для каждого графа, даже если ребер нет вообще, поэтому мы не можем предполагать какую-либо связь между |V| и |E| и мы получаем время работы O(|V|+|E|) .
false
и это занимает времяМожем ли мы избежать структуры данных со временем инициализацииΘ(|V|) ? Нашей первой попыткой может быть использование связанного списка. Однако теперь проверка того, была ли обнаружена вершина (строка 10), занимает линейное время по числу посещенных вершин, а не постоянное время, как раньше. Это означает, что время выполнения становится O(|V||E|) , что намного хуже в худшем случае. (Обратите внимание, что мы не хотим переписывать это какO(|E|2) так как это еще хуже: это может быть так же плохо, как|V|4 , тогда как|V||E|≤|V|3
источник