algorithm - profundidad - dfs pseudocode

Breadth First Análisis de complejidad del tiempo de búsqueda

Question

La complejidad del tiempo para revisar cada borde adyacente de un vértice es, por ejemplo, O(N) , donde N es el número de bordes adyacentes. Entonces, para el número V de vértices, la complejidad del tiempo se convierte en O(V*N) = O(E) , donde E es el número total de aristas en el gráfico. Como eliminar y agregar un vértice de / a cola es O(1) , por qué se agrega a la complejidad general de tiempo de BFS como O(V+E) .

Answer 1

Al realizar una operación O(1) L veces, resulta en O(L) complejidad. Por lo tanto, eliminar y agregar un vértice de / a la cola es O (1), pero cuando haces eso para V vértices, obtienes O(V) complejidad. Por lo tanto, O(V) + O(E) = O(V+E)

Answer 2

Considerando el siguiente Gráfico, vemos cómo la complejidad del tiempo es O (| V | + | E |) pero no O (V * E).

Lista de adyacencia

V E
v0:{v1,v2}
v1:{v3}
v2:{v3}
v3:{}

Cómo funciona BFS Works Step by Step

Paso 1:

Listas de adyacencia:

V E
v0: {v1,v2} mark, enqueue v0
v1: {v3}
v2: {v3}
v3: {}

Paso 2:

Listas de adyacencia:

V E
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2
v1: {v3}
v2: {v3}
v3: {}

Paso 3:

Listas de adyacencia:

V E
v0: {v1,v2}
v1: {v3} dequeue v1; mark,enqueue v3
v2: {v3}
v3: {}

Etapa 4:

Listas de adyacencia:

V E
v0: {v1,v2}
v1: {v3}
v2: {v3} dequeue v2, check its adjacency list (v3 already marked)
v3: {}

Paso 5:

Listas de adyacencia:

V E
v0: {v1,v2}
v1: {v3}
v2: {v3}
v3: {} dequeue v3; check its adjacency list

Paso 6:

Listas de adyacencia:

V E
v0: {v1,v2} |E0|=2
v1: {v3} |E1|=1
v2: {v3} |E2|=1
v3: {} |E3|=0

Número total de pasos:

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E|
4 + 2 + 1 + 1 + 0 == 4 + 4
8 == 8

Suponga una representación de lista de adyacencia, V es el número de vértices, E es el número de bordes.

Cada vértice se pone en cola y se quita de la cola a lo sumo una vez.

El escaneo de todos los vértices adyacentes toma el tiempo O (| E |) , ya que la suma de las longitudes de las listas de adyacencia es | E | .

Por lo tanto, la complejidad temporal de BFS da una complejidad de tiempo O (| V | + | E |) .

Answer 3

Espero que esto sea útil para cualquiera que tenga problemas para comprender la complejidad de tiempo computacional para Breadth First Search, también conocido como BFS.

Queue graphTraversal.add(firstVertex);
// This while loop will run V times, where V is total number of vertices in graph.
while(graphTraversal.isEmpty == false)
currentVertex = graphTraversal.getVertex();
// This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex.
while(currentVertex.hasAdjacentVertices)
graphTraversal.add(adjacentVertex);
graphTraversal.remove(currentVertex);

La complejidad del tiempo es la siguiente:

V * (O(1) + Eaj + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

Intenté simplificar el cálculo del código y la complejidad, pero aun así, si tiene alguna pregunta, hágamelo saber.

Answer 4

I understood the part V+E in the complexity.
But I have 2 questions
1). V * Eaj should give 2E?
(as it is the total no of edges accessed, and each edge is checked twice, by each of it ends)
2) Also the complexity is V + E
but in worst case we take E = V*(V-1)/2
So V isn''t required here as we could say we E = V²...
Can''t we say complexity O(E) only?