Complexidade do tempo do BFS

BFS significa Pesquisa de Blânsito. Pesquisa de respiração é um algoritmo para pesquisar um nó específico em uma árvore. Um nó ou vértice significa a mesma coisa para uma árvore. O objetivo deste artigo é explicar o algoritmo BFS, dar uma breve nota sobre a complexidade do tempo e saber como a complexidade do tempo é aplicável ao algoritmo BFS. C ++ é usado para a codificação.

Conteúdo do artigo

• • Introdução - Veja acima
  • Pesquisa de respiração primeiro
  • Breve nota sobre a complexidade do tempo
  • Procurando por um vértice pela primeira pesquisa
  • Conclusão

Pesquisa de respiração primeiro

A árvore
Um diagrama de árvores para ilustrar a primeira pesquisa é o seguinte:

Para procurar um nó, o algoritmo começa com o nó raiz 1 e depois para o nó 2, nó 3, etc. Nível por nível, de cima para baixo, da esquerda para a direita, até encontrar o nó que está procurando.

Armazenando a árvore
Uma árvore é como um gráfico simples. Neste artigo, a árvore é armazenada usando uma lista de adjacência. Uma lista de adjacência indica um nó (vértice) e todos os seus nós adjacentes (vértices), como segue, no diagrama anterior:

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

Uma borda
Uma borda é a linha que une um vértice e um vértice adjacente. Também pode ser considerado um par, composto de um vértice (nó) e um vértice adjacente (nó adjacente). Portanto, a árvore anterior possui as seguintes bordas para os vértices correspondentes:

3 arestas: 1 adjacente a 2, 3, 4
3 arestas: 2 adjacente a 1, 5, 6
1 borda: 3 adjacente a 1
3 arestas: 4 adjacentes a 1, 7, 8
3 arestas: 5 adjacentes a 2, 9, 10
1 borda: 6 adjacente a 2
3 arestas: 7 adjacente a 4, 11, 12
1 borda: 8 adjacente a 4
1 borda: 9 adjacente a 5
1 borda: 10 adjacente a 5
1 borda: 11 adjacente a 7

Estrutura C ++
As informações anteriores podem ser armazenadas em um vetor C ++ de vetores. Cada linha começa com um nó, seguido por seus nós adjacentes. O vetor de vetores C ++, pois a árvore anterior é a seguinte:

vetor 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 a complexidade do tempo

Considere o seguinte código:

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

A saída é:

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

Supondo que a declaração cout seja uma operação simples, a complexidade do tempo (velocidade) para este loop for considerada O (n), onde n neste caso é 10. O grande O seguido de colchetes com n é a notação para a complexidade do tempo (velocidade). Considere o seguinte código:

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

A saída é:

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

Embora n seja 10, não até 10 elementos são impressos (7 elementos foram impressos). A complexidade do tempo ainda é considerada O (n). É o número máximo possível de operações que é levado em consideração.

Considere o seguinte código:

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

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

cout << endl;

A saída é:

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

Existem dois loops para 10 variáveis ​​cada, para N e M. Diz -se que a complexidade do tempo (velocidade) é: o (n + m). Mesmo se a saída for:

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

A complexidade do tempo ainda é dada como O (n + m). É o número máximo possível de operações que é levado em consideração. Além disso, se a saída for:

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 convenção, a complexidade do tempo ainda é dada como O (n + m).

Procurando por um vértice pela primeira pesquisa

Wikipedia.Org fornece o algoritmo da seguinte forma:

• Use uma fila (primeiro na primeira saída).
• Verifique se um vértice foi explorada antes de envolver o vértice.

Continua dizendo que a complexidade do tempo é:

O (| v | + | e |)

Onde | v | é o número de vértices (nós) e | e | é o número de bordas.

Se a estrutura da árvore for dada como um vetor de vetores, como no caso anterior, não haverá necessidade de usar uma fila. Basta escanear os vetores de vetores, de cima para baixo, até que o vértice que seja procurado seja visto. Este procedimento ainda fornece o mesmo tempo a complexidade de O (| v | + | e |).

Suponha que, para a árvore anterior, o vértice 9 deve ser pesquisado. A partir das bordas/tabela de nó se distribuía novamente, para facilitar o acesso, o número de arestas é 19 e o número de nós é 9:

3 arestas: 1 adjacente a 2, 3, 4
3 arestas: 2 adjacente a 1, 5, 6
1 borda: 3 adjacente a 1
3 arestas: 4 adjacentes a 1, 7, 8
3 arestas: 5 adjacentes a 2, 9, 10
1 borda: 6 adjacente a 2
3 arestas: 7 adjacente a 4, 11, 12
1 borda: 8 adjacente a 4
1 borda: 9 adjacente a 5
1 borda: 10 adjacente a 5
1 borda: 11 adjacente a 7

As operações são 9 + 19 = 28. Nesta tabela, as bordas são citadas à esquerda e os vértices são citados à direita. Novamente, é a soma máxima possível que é considerada, ou seja: 11 + 21 = 32. Isso significa que existem onze vértices mais 21 arestas, que é O (11 + 21), escritas em termos gerais como o (| v | + | e |).

O código C ++ para procurar o vértice 9 é:

int contador = 0;
para (não assinado i = 0; ipara (j não assinado = 0; jcontador = contador + 1;

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

cout << counter << endl;

A saída é 28, com um máximo de 32.

Conclusão

A complexidade do tempo do BFS é:

O (| v | + | e |)

Onde | v | é o número de vértices (nós) e | e | é o número de bordas.