Объяснение времени выполнения BFS и DFS

Question

Почему время выполнения BFS и DFS O (V + E), особенно когда есть узел, имеющий направленное ребро к узлу, которого можно достичь из вершины, как в этом примере на следующем сайте1001 *

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Answer 1

E - это множество всех ребер графа, как G = {V, E}.Итак, | E |это количество всех ребер в графе.

Одного этого должно быть достаточно, чтобы убедить вас, что общая сложность не может быть | V |раз | E |, поскольку мы не выполняем итерацию по всем ребрам графа для каждой вершины.

В представлении списка смежности для каждой вершины v мы проходим только те узлы, которые прилегают к ней.

| V |фактор | V | + | E |Похоже, что из-за количества выполненных операций с очередями.

Обратите внимание, что сложность алгоритма зависит от используемой структуры данных.фактически мы обращаемся к каждой части информации, представленной в представлении графа, поэтому для матричного представления графа сложность становится квадратом V.

Цитирование из Кормена,

"Операциина постановку в очередь и снятие очереди занимает O (1) времени, поэтому общее время, отведенное для операций с очередями, составляет O (V). Поскольку список смежности каждой вершины сканируется только тогда, когда вершина снята, каждый список смежности сканируется не более одного раза.Поскольку сумма длин всех списков смежности равна Θ (E), общее время, затрачиваемое на сканирование списков смежности, составляет O (E). Затраты на инициализацию составляют O (V), и, таким образом, общее время работы BFS составляетO (V + E). "

Answer 2

Эта проблема занимает около 4 часов моего времени, но, наконец, я думаю, что у меня есть простой способ получить картину, вначале у меня возникло желание сказать O (V * E).

Подводя итогАлгоритм, который вы найдете в Cormen, то же самое на http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm у вас есть что-то вроде этого:

для (vi в V) Некоторые O (1) инструкции для (e в Adj (vi)) {Некоторые O (1) инструкции}

Вопрос в том, сколько инструкций здесь выполнено?это будет сигма-сумма (Adj (vi)), и это значение ограничено сверху 2 | E |.

В начале мы автоматически думаем о умножении количества итераций внутреннего и внешнегоциклы, но в этом случае общее число итераций во внутреннем цикле является функцией внешнего итератора, поэтому умножение невозможно.

Answer 3

Вы посещаете каждый край максимум дважды.Есть E ребер.Так что будет 2 * E пограничных визитов.Плюс узлы, у которых нет ребер или, другими словами, со степенью 0. Таких узлов может быть не более V.Таким образом, сложность оказывается: O (2 * E + V) = O (E + V)

Answer 4

Вы перебираете | V | узлы, не более | V | раз. Так как у нас есть верхняя граница | E | всего ребер в графе мы проверим самое большее | E | кромки. Разные вершины будут иметь различное количество смежных узлов, поэтому мы не можем просто умножить | V | * | E | (это означает, что для каждой вершины мы пересекаем | E | ребер, что неверно, | E | - общее количество ребер по всем узлам), скорее, мы проверяем V узлов и проверяем всего E кромки. В конце мы имеем O (| V | + | E |)

Для DFS это нечто похожее, мы перебираем все списки смежности вершин, вызывая DFS (v), если он не был посещен, что означает, что мы несем | V | временные шаги плюс время, затрачиваемое на посещение соседних узлов (по сути, они образуют ребро, и мы имеем в общей сложности | E | ребер, следовательно, время O (V + E).

    private static void visitUsingDFS(Node startNode) {
        if(startNode.visited){
            return;
        }
        startNode.visited = true;
        System.out.println("Visited "+startNode.data);
        for(Node node: startNode.AdjacentNodes){
            if(!node.visited){
                visitUsingDFS(node);
            }
        }
    }