Complessità del tempo BFS

BFS sta per la prima ricerca. La prima ricerca del respiro è un algoritmo per la ricerca di un particolare nodo in un albero. Un nodo o un vertice significa la stessa cosa per un albero. Lo scopo di questo articolo è di spiegare l'algoritmo BFS, dare una breve nota sulla complessità del tempo e apprendere come la complessità temporale è applicabile all'algoritmo BFS. C ++ viene utilizzato per la codifica.

Contenuto dell'articolo

• • Introduzione - Vedi sopra
  • Ricerca al respiro
  • Breve nota sulla complessità del tempo
  • Alla ricerca di un vertice mediante la prima ricerca
  • Conclusione

Ricerca al respiro

L'albero
Un diagramma ad albero per illustrare la prima ricerca del respiro è il seguente:

Per cercare un nodo, l'algoritmo inizia con il nodo radice 1 quindi al nodo 2, nodo 3, ecc. Livello per livello, dall'alto verso il basso, da sinistra a destra, fino a quando non incontra il nodo che sta cercando.

Memorizzando l'albero
Un albero è come un grafico semplice. In questo articolo, l'albero viene archiviato utilizzando un elenco di adiacenza. Un elenco di adiacenza indica un nodo (vertice) e tutti i suoi nodi adiacenti (vertici), come segue, nel diagramma precedente:

1 adiacente a 2, 3, 4
2 adiacente a 1, 5, 6
3 adiacente a 1
4 adiacente a 1, 7, 8
5 adiacente a 2, 9, 10
6 adiacente a 2
7 adiacente a 4, 11, 12
8 adiacente a 4
9 adiacente a 5
10 adiacente a 5
11 adiacente a 7
12 Adiacente a 7

Un bordo
Un bordo è la linea che unisce un vertice e un vertice adiacente. Può anche essere considerato come una coppia, composta da un vertice (nodo) e un vertice adiacente (nodo adiacente). Quindi, l'albero precedente ha i seguenti bordi per i vertici corrispondenti:

3 bordi: 1 adiacente a 2, 3, 4
3 bordi: 2 adiacenti a 1, 5, 6
1 bordo: 3 adiacente a 1
3 bordi: 4 adiacenti a 1, 7, 8
3 bordi: 5 adiacenti a 2, 9, 10
1 bordo: 6 adiacente a 2
3 bordi: 7 adiacenti a 4, 11, 12
1 bordo: 8 adiacente a 4
1 bordo: 9 adiacente a 5
1 bordo: 10 adiacente a 5
1 bordo: 11 adiacente a 7

Struttura C ++
Le informazioni precedenti possono essere memorizzate in un vettore C ++ di vettori. Ogni riga inizia con un nodo, seguito dai suoi nodi adiacenti. Il vettore dei vettori C ++, per l'albero precedente è il seguente:

vettore vtr = 1, 2, 3, 4,
2, 1, 5, 6,
3, 1,
4, 1, 7, 8,
5, 2, 9, 10,
6, 2,
7, 4, 11, 12,
8, 4,
9, 5,
10, 5,
11, 7,
12, 7;

Breve nota sulla complessità del tempo

Considera il seguente codice:

int n = 10;
per (int i = 0; icout << i << ", ";

L'output è:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Supponendo che la dichiarazione Cout sia un'operazione semplice, si dice che la complessità del tempo (velocità) per questo per loop sia O (n), dove n in questo caso è 10. Il grande O seguito da parentesi con n è la notazione per la complessità del tempo (velocità). Considera il seguente codice:

int n = 10;
per (int i = 0; i<7; i++)
cout << i << ", ";

L'output è:

0, 1, 2, 3, 4, 5, 6,

Sebbene N sia 10, non vengono stampati fino a 10 elementi (sono stati stampati 7 elementi). Si dice ancora che la complessità del tempo sia O (n). È il numero massimo possibile di operazioni che viene preso in considerazione.

Considera il seguente codice:

int n = 10;
int m = 10;
per (int i = 0; icout << i << ", ";

cout << endl;
per (int i = 0; icout << i << ", ";

cout << endl;

L'output è:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Ci sono due per loop per 10 variabili ciascuno, per n e m. Si dice che la complessità del tempo (velocità) qui sia: o (n + m). Anche se l'output è:

0, 1, 2, 3, 4, 5, 6
0, 1, 2, 3, 4, 5, 6

La complessità del tempo è ancora data come O (n + m). È il numero massimo possibile di operazioni che viene preso in considerazione. Inoltre, se l'output è:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Per convenzione, la complessità del tempo è ancora data come O (N + M).

Alla ricerca di un vertice mediante la prima ricerca

Wikipedia.Org fornisce l'algoritmo come segue:

• Usa una coda (prima al primo fuori).
• Controlla se è stato esplorato un vertice prima di accusare il vertice.

Continua dicendo che la complessità del tempo è:

O (| v | + | e |)

Dove | V | è il numero di vertici (nodi) e | e | è il numero di bordi.

Se la struttura per l'albero è data come vettore di vettori, come nel caso precedente, non sarà necessario utilizzare una coda. Basta scansionare il vettore dei vettori, dall'alto verso il basso, fino a quando si vede il vertice che viene esaminato. Questa procedura fornisce ancora la stessa complessità temporale di O (| v | + | e |).

Supponiamo che per l'albero precedente, il vertice 9 deve essere cercato. Dai bordi/tabella dei nodi ri-esplay nel seguente, per un facile accesso, il numero di bordi è 19 e il numero di nodi è 9:

3 bordi: 1 adiacente a 2, 3, 4
3 bordi: 2 adiacenti a 1, 5, 6
1 bordo: 3 adiacente a 1
3 bordi: 4 adiacenti a 1, 7, 8
3 bordi: 5 adiacenti a 2, 9, 10
1 bordo: 6 adiacente a 2
3 bordi: 7 adiacenti a 4, 11, 12
1 bordo: 8 adiacente a 4
1 bordo: 9 adiacente a 5
1 bordo: 10 adiacente a 5
1 bordo: 11 adiacente a 7

Le operazioni sono 9 + 19 = 28. In questa tabella, i bordi sono citati a sinistra e i vertici sono citati a destra. Ancora una volta, è la massima somma possibile che viene considerata, cioè: 11 + 21 = 32. Significa che ci sono undici vertici più 21 bordi, che è O (11 + 21), scritto in termini generali come O (| v | + | e |).

Il codice C ++ per cercare il vertice 9 è:

int counter = 0;
per (non firmato i = 0; iper (non firmato j = 0; jcontatore = contatore + 1;

if (vtr [i] [0] == 9)
rottura;

cout << counter << endl;

L'uscita è 28, con un massimo di 32.

Conclusione

La complessità del tempo BFS è:

O (| v | + | e |)

Dove | V | è il numero di vertici (nodi) e | e | è il numero di bordi.