data structures - profundidad - Explicación de los tiempos de ejecución de BFS y DFS

dfs algorithm

Question

¿Por qué los tiempos de ejecución de BFS y DFS O (V + E), especialmente cuando hay un nodo que tiene un borde dirigido a un nodo que se puede alcanzar desde el vértice, como en este ejemplo en el siguiente sitio

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

Answer 1

E es el conjunto de todos los bordes en el gráfico, como G = {V, E}. Entonces, | E | es el recuento de todos los bordes en el gráfico.

Esto solo debería ser suficiente para convencerlo de que la complejidad general no puede ser | V | veces | E |, ya que no estamos iterando sobre todos los bordes en el gráfico para cada vértice.

En la representación de la lista de adyacencia, para cada vértice v, solo atravesamos aquellos nodos adyacentes a él.

El | V | factor de | V | + | E | parece provenir del número de operaciones de cola realizadas.

Tenga en cuenta que la complejidad del algoritmo depende de la estructura de datos utilizada. de hecho estamos visitando cada pieza de información presente en la representación del gráfico, que es por lo que para la representación matricial del gráfico, la complejidad se convierte en V al cuadrado.

Citando de Cormen,

"Las operaciones de poner en cola y decaminar toman O (1) tiempo, por lo que el tiempo total dedicado a las operaciones de cola es O (V). Debido a que la lista de adyacencia de cada vértice se escanea solo cuando el vértice se quita, cada lista de adyacencia se escanea en la mayoría una vez. Dado que la suma de las longitudes de todas las listas de adyacencia es Θ (E), el tiempo total empleado en escanear listas de adyacencia es O (E). La sobrecarga para la inicialización es O (V) y, por lo tanto, el tiempo total de ejecución de BFS es O (V + E) ".

Answer 2

Este problema consume como 4 horas de mi tiempo, pero finalmente creo que tengo una manera fácil de obtener la imagen, al principio tuve la tentación de decir O (V * E).

Resumiendo el algoritmo que encuentras en Cormen, que es el mismo en http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm tienes algo como esto:

para (vi en V) Algunas O (1) instrucciones para (e en Adj (vi)) {Algunas O (1) instrucciones}

La pregunta es cuántas instrucciones se ejecutan aquí? esa será la sigma-suma (Adj (vi)), y este valor estará limitado por 2 | E |.

Al principio pensamos automáticamente en multiplicar el número de iteraciones de los bucles interno y externo, pero en este caso el número total de iteraciones en el bucle interno es una función del iterador externo, por lo que no es posible la multiplicación.

Answer 3

Usted itera sobre el | V | nodos, a lo sumo | V | veces. Como tenemos un límite superior de | E | bordes en total en el gráfico, comprobaremos a lo sumo | E | bordes. Diferentes vértices tendrán un número variable de nodos adyacentes, por lo que no podemos simplemente multiplicar | V | * | E | (significa que para cada vértice, atravesamos | E | bordes, lo cual no es verdadero, | E | es el número total de bordes sobre todos los nodos), más bien, verificamos los nodos V, y verificamos un total de E bordes. Al final, tenemos O (| V | + | E |)

Para DFS, es algo similar, recorremos todas las listas de adyacencias de vértices, llamando a DFS (v) si no se ha visitado, lo que significa que incurrimos en | V | Pasos de tiempo, más el tiempo incurrido para visitar nodos adyacentes (esencialmente, estos forman un borde, y tenemos un total de | E | bordes, por lo tanto, O (V + E) tiempo.

    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);
            }
        }
    }

Answer 4

Usted visita cada borde como máximo dos veces. Hay bordes E Entonces habrá 2 * E operaciones de visita al borde. Además de los nodos, estos no tienen bordes o, en otras palabras, con grado 0. Puede haber como máximo V tales nodos. Entonces la complejidad resulta ser O (2 * E + V) = O (E + V)