Поиск в ширину, в котором проверенные вершины хранятся в списке, а не в множестве. Граф связный, в нём V вершин и E рёбер. Определите время выполнения.
Проверенные вершины в списке
Код
from collections import deque
def reachable(graph: dict[str, list[str]], start: str) -> list[str]:
searched = []
queue = deque([start])
while queue:
node = queue.popleft()
if node in searched:
continue
searched.append(node)
for neighbor in graph.get(node, []):
queue.append(neighbor)
return searchedКакое время выполнения?
Ответ: O(V · E)
Здесь вершина добавляется в очередь при каждом просмотре ребра, ведущего в неё, поэтому извлечений из очереди — около E. Каждое извлечение проверяет node in searched по списку длиной до V — это O(V). Итого O(V · E). Чтобы получить O(V + E) из главы, searched должен быть множеством (set) — хеш-таблицей с проверкой за O(1).
- Подсказка 1
Сколько раз выполняется queue.popleft()? Вершина может попасть в очередь несколько раз — по разу на каждое входящее ребро.
- Подсказка 2
Сколько стоит проверка node in searched, когда searched — список длины до V?