Почему время работы BFS и DFS O (V + E), особенно когда есть node, который имеет направленный край к node, который может быть достигнут из вершины, как в этом примере в следующий сайт
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
E - множество всех ребер графа, так как G = {V, E}. Итак, | E | - количество всех ребер в графе.
Этого должно быть достаточно, чтобы убедить вас, что общая сложность не может быть | V | times | E |, так как мы не итерируем по всем ребрам в графе для каждой вершины.
В представлении списка смежности для каждой вершины v мы пересекаем только те узлы, которые находятся рядом с ним.
| V | фактор | V | + | E | похоже, исходит из числа выполненных операций с очередью.
Обратите внимание, что сложность алгоритма зависит от используемой структуры данных. эффективно мы посещаем каждую часть информации, присутствующую в представлении графа, поэтому для матричного представления графа сложность становится квадратичной.
Цитата из Cormen,
"Операции enqueuing и dequeuing занимают O (1) раз, поэтому общее время, затрачиваемое на операции с очередью, равно O (V). Поскольку список смежности каждой вершины проверяется только тогда, когда вершина выгружена, каждый список смежности поскольку сумма длин всех списков смежности равна Θ (E), общее время, затрачиваемое на сканирование списков смежности, равно O (E). Накладные расходы для инициализации составляют O (V), и, следовательно, общее время работы BFS равно O (V + E)."
Эта проблема расходуется, как 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) }
Вопрос в том, сколько команд выполняется здесь? это будет Sigma-Sum (Adj (vi)), и это значение ограничено сверху на 2 | E |.
Вначале мы автоматически думаем о умножении числа итераций внутренней и внешней петель, но в этом случае общее число итераций во внутреннем цикле является функцией внешнего итератора, поэтому не возможно умножение.
Вы чаще всего посещаете каждое ребро. Есть E ребер. Таким образом, будут выполняться операции с краем 2 * E. Плюс узлы, которые не имеют ребер или, другими словами, со степенью 0. Там может быть не более V таких узлов. Таким образом, сложность оказывается равной O (2 * E + V) = O (E + V)
Вы перебираете | 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);
}
}
}