Временная сложность первого поиска ширины с представлением матрицы смежности?
В bfs мы должны искать каждый узел, и для каждого узла мы должны искать все элементы строки.Не требует ли это O (V^2) (количество элементов в матрице смежности) времени и, следовательно, для матрицы смежности общее время не должно быть O (V^2+E).
1 ответ:
Сложность BFS, реализуемой с использованием матрицы смежности, будет O (|V|2). Это происходит главным образом потому, что каждый раз, когда мы хотим найти, какие ребра примыкают к данной вершине 'U', нам придется пересечь весь массив смежности[U], который отклоняется от курса длины |V|.
Представьте себе, что BFS прогрессирует как границы. Вы берете начальную вершину S, которая находится на уровне-0. Все соседние вершины находятся на уровне-1. Затем мы помечаем все смежные вершины всех вершин на уровне-1, который не имеет уровня, на уровне - 2. Таким образом, каждая вершина будет принадлежать только одной границе (или уровню). И когда элемент находится на границе, мы проверяем один раз его соседние вершины, что занимает O(|V|) времени. Поскольку граница охватывает| V / элементов в течение алгоритма, общее время станет O (|V / * / V|), которое равно O (|V|2).
Разница в сложности в БФС при реализации списков смежности и матрицы возникает из-за того, что в смежности Матрица, чтобы сказать, какие узлы примыкают к данной вершине, мы берем O (|V/) время, независимо от ребер. Тогда как в списке смежности, непосредственно доступном нам, требуется время, пропорциональное самим смежным вершинам, которое при суммировании по всем вершинам |V| равно |E|. Итак, BFS по списку смежности дает O (|V| + |E|).
Я надеюсь, что мой ответ помог вам, если это так, дайте мне знать...! ☺