Временная сложность дерева, чтобы найти вершину с помощью BFS Algo

Question

Я немного путать о временной сложности BFS для tree.If не имеют п нет ребенка родительского узла, то, что будет время, сложность найти значение?

, например: -

Именно граф image.I хотите найти вершину «K» с помощью BFS Algo то, что будет временная сложность? пожалуйста, объясните.

Answer 1

• Здесь приведенная структура данных дерева такая же, как и без направленного, не взвешенного, простого графика.

• По вашему вопросу мы можем запустить алгоритм BFS из вершины вершины в K, мы получим путь A-> B-> C-> D-> E-> F-> G-> H-> I-> J-> K

• Структура данных очереди более удобна при поиске вершин с помощью BFS.

• Сложность вычисления:

1) Сложность BFS реализован с использованием матрицы смежности будет O (| V |^2). Причина: В матрице смежности вам нужно дважды посещать один узел, поскольку они повторяются в строке и столбце.

2) При реализации в списке смежности O (| V | + | E |). Причина: Из-за списка смежности нам нужно просто один раз посетить вершину.