BFS Complejidad del tiempo

BFS representa la búsqueda de la primera. La búsqueda de aliento primero es un algoritmo para buscar en un nodo particular en un árbol. Un nodo o vértice significa lo mismo para un árbol. El objetivo de este artículo es explicar el algoritmo BFS, dar una breve nota sobre la complejidad del tiempo y aprender cómo la complejidad del tiempo es aplicable al algoritmo BFS. C ++ se usa para la codificación.

Contenido del artículo

• • Introducción - Ver arriba
  • Búsqueda de la primera y respiración
  • Breve nota sobre la complejidad del tiempo
  • Buscando un vértice mediante la primera búsqueda
  • Conclusión

Búsqueda de la primera y respiración

El árbol
Un diagrama de árboles para ilustrar la búsqueda de la primera y respiración es el siguiente:

Para buscar un nodo, el algoritmo comienza con el nodo raíz 1 y luego al nodo 2, nodo 3, etc. Nivel por nivel, de arriba a abajo, de izquierda a derecha, hasta que se encuentra con el nodo que está buscando.

Almacenando el árbol
Un árbol es como un gráfico simple. En este artículo, el árbol se almacena utilizando una lista de adyacencia. Una lista de adyacencia indica un nodo (vértice) y todos sus nodos adyacentes (vértices), como sigue, en el diagrama anterior:

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

Un borde
Un borde es la línea que une un vértice y un vértice adyacente. También se puede considerar como un par, compuesto por un vértice (nodo) y un vértice adyacente (nodo adyacente). Entonces, el árbol anterior tiene los siguientes bordes para los vértices correspondientes:

3 bordes: 1 adyacente a 2, 3, 4
3 bordes: 2 adyacentes a 1, 5, 6
1 borde: 3 adyacente a 1
3 bordes: 4 adyacentes a 1, 7, 8
3 bordes: 5 adyacentes a 2, 9, 10
1 borde: 6 adyacente a 2
3 bordes: 7 adyacentes a 4, 11, 12
1 borde: 8 adyacente a 4
1 borde: 9 adyacente a 5
1 borde: 10 adyacente a 5
1 borde: 11 adyacente a 7

Estructura de C ++
La información anterior se puede almacenar en un vector C ++ de vectores. Cada fila comienza con un nodo, seguido de sus nodos adyacentes. El vector de vectores C ++, para el árbol anterior es el siguiente:

vector 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 sobre la complejidad del tiempo

Considere el siguiente código:

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

La salida es:

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

Suponiendo que la declaración de cout es una operación simple, se dice que la complejidad del tiempo (velocidad) para este bucle es O (n), donde n en este caso es 10. El Big O seguido de entre paréntesis con N es la notación para la complejidad del tiempo (velocidad). Considere el siguiente código:

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

La salida es:

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

Aunque n es 10, no se imprimen hasta 10 elementos (se han impreso 7 elementos). Todavía se dice que la complejidad del tiempo es o (n). Es el número máximo posible de operaciones lo que se tiene en cuenta.

Considere el siguiente código:

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

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

cout << endl;

La salida es:

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

Hay dos bucles para 10 variables cada una, para n y m. Se dice que la complejidad del tiempo (velocidad) es: O (N + M). Incluso si la salida es:

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

La complejidad del tiempo todavía se da como o (n + m). Es el número máximo posible de operaciones lo que se tiene en cuenta. Además, si la salida es:

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,

Por convención, la complejidad del tiempo todavía se da como o (n + m).

Buscando un vértice mediante la primera búsqueda

Wikipedia.Org da el algoritmo de la siguiente manera:

• Use una cola (primero en primera salida).
• Compruebe si se ha explorado un vértice antes de eneuar el vértice.

Continúa diciendo que la complejidad del tiempo es:

O (| V | + | E |)

Donde | V | es el número de vértices (nodos) y | E | es el número de bordes.

Si la estructura para el árbol se da como un vector de vectores, como en el caso anterior, no habrá necesidad de usar una cola. Simplemente escanee el vector de vectores, de arriba a abajo, hasta que se ve el vértice que se busca. Este procedimiento todavía da la misma complejidad de tiempo de O (| V | + | E |).

Suponga que para el árbol anterior, se debe buscar el vértice 9. Desde la tabla de bordes/nodo rediseñado a continuación, para facilitar el acceso, el número de bordes es 19 y el número de nodos es 9:

3 bordes: 1 adyacente a 2, 3, 4
3 bordes: 2 adyacentes a 1, 5, 6
1 borde: 3 adyacente a 1
3 bordes: 4 adyacentes a 1, 7, 8
3 bordes: 5 adyacentes a 2, 9, 10
1 borde: 6 adyacente a 2
3 bordes: 7 adyacentes a 4, 11, 12
1 borde: 8 adyacente a 4
1 borde: 9 adyacente a 5
1 borde: 10 adyacente a 5
1 borde: 11 adyacente a 7

Las operaciones son 9 + 19 = 28. En esta tabla, los bordes se citan a la izquierda y los vértices se citan a la derecha. Nuevamente, es la suma máxima posible la que se considera, es decir: 11 + 21 = 32. Significa que hay once vértices más 21 bordes, que es O (11 + 21), escrito en términos generales como o (| V | + | E |).

El código C ++ para buscar el vértice 9 es:

int contador = 0;
para (sin firmar i = 0; ipara (unsigned j = 0; jcontador = contador + 1;

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

cout << counter << endl;

La salida es 28, con un máximo de 32.

Conclusión

La complejidad del tiempo BFS es:

O (| V | + | E |)

Donde | V | es el número de vértices (nodos) y | E | es el número de bordes.