Я немного смущен временной сложностью BFS для дерева. Если нет n дочерних узлов родительского узла, то какова будет временная сложность, чтобы найти значение?
Это изображение графа. Я хочу найти вершину «K» с помощью алгоритма BFS, тогда какова будет временная сложность? Пожалуйста, объясните это.
Здесь приведенная выше древовидная структура данных такая же, как ненаправленный, невзвешенный, простой граф.
Что касается вашего вопроса, мы можем запустить алгоритм BFS из вершины A в вершину K, мы получим путь A-> B-> C-> D-> E-> F-> G-> H-> I-> J- >К
Структура данных очереди более удобна при поиске вершин по BFS.
Расчет сложности:
1) Сложность BFS, реализованной с использованием матрицы смежности, будет O(|V|^2). Причина: в матрице смежности вам нужно посетить один узел дважды, так как они повторяются в строке и столбце.
2) При реализации списком смежности это O(|V| + |E|). Причина: из-за списка смежности нам достаточно посетить вершину один раз.
