Larghezza Prima analisi della complessità del tempo di ricerca

Question

La complessità del tempo per superare ciascun lato adiacente di un vertice è dire O(N), dove N è il numero di bordi adiacenti. Quindi per V numero di vertici la complessità temporale diventa O(V*N) = O(E), dove E è il numero totale di spigoli nel grafico. Poiché la rimozione e l'aggiunta di un vertice da/a Queue è O(1), perché viene aggiunta alla complessità temporale complessiva di BFS come O(V+E).

Answer 1

Spero che questo sia utile a chiunque abbia difficoltà a comprendere la complessità temporale computazionale per la ricerca di ampiezza a.k.a 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); 

Tempo complessità è la seguente:

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

Ho cercato di semplificare il codice e la complessità di calcolo, ma ancora se avete domande fatemi sapere.

Answer 2

Esecuzione di un'operazione O(1)L volte, risultati a O(L) complessità. Quindi, la rimozione e l'aggiunta di un vertice da/a coda è O (1), ma quando si esegue questa operazione per i vertici V, si ottiene la complessità O(V). Pertanto, O(V) + O(E) = O(V+E)

Answer 3

Considerando il grafico seguente vediamo come la complessità temporale sia O (| V | + | E |) ma non O (V * E).

lista di adiacenza

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

operativo come BFS Opere Step by Step

Step1:

liste di adiacenza:

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

Step2:

liste di adiacenza:

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

Step3: Attuarsi

liste di adiacenza:

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

Fase 4:

liste di adiacenza:

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

Fase 5:

liste di adiacenza:

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

Step6:

liste di adiacenza:

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

numero totale di passi:

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

Assumere una rappresentazione di lista di adiacenza, V è il numero di vertici, E il numero di bordi.

Ogni vertice viene accodato e rimosso dalla coda al massimo una volta.

La scansione per tutti i vertici adiacenti richiede O (| E |) tempo, poiché la somma delle lunghezze degli elenchi di adiacenze è | E |.

Di conseguenza, la complessità temporale di BFS fornisce una complessità di tempo pari a O (| V | + | E |).

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?