algorithm - prim - busqueda profundidad iterativa java

Complejidad temporal del algoritmo de grafo de profundidad primero

Question

Estoy empezando a aprender la complejidad del tiempo, y busqué en los ejemplos la complejidad del tiempo para una especie simple.

Quería saber cómo calculamos la complejidad de tiempo promedio para una búsqueda en profundidad en un gráfico con |V|=n y |E|=m , deje que el nodo inicial sea ''u'' y el nodo final sea ''v''.

Answer 1

La complejidad del tiempo para DFS es O (n + m). Obtenemos esta complejidad considerando el hecho de que estamos visitando cada nodo solo una vez y en el caso de un árbol (sin ciclos) cruzamos todos los bordes una vez.

Por ejemplo, si el nodo de inicio es u, y el nodo final es v, estamos pensando en el peor de los casos en que v será el último nodo visitado. Así que estamos comenzando a visitar cada uno de los componentes del primer vecino de u conectado, luego el componente conectado del segundo vecino, y así sucesivamente hasta el componente conectado del último vecino, donde encontramos v. Hemos visitado cada nodo solo una vez, y no cruzamos El mismo borde más de una vez.

Answer 2

será O (n + m) si la gráfica se presenta en forma de lista de adyacencia, pero si la gráfica tiene la forma de matriz de adyacencia, entonces la complejidad es O (n * n), ya que tenemos que recorrer todo el conjunto Fila hasta que encontremos un borde.