Breadth First Search (BFS)
BFS (breadth-first search, width-first search) - um método de travessia de grafo, muito frequentemente usado em algoritmos simples e avançados. A busca em largura funciona percorrendo os níveis individuais do gráfico, começando no nó de origem e gradualmente se afastando dele. Isso fica claro na animação.
Para escrever o BFS mais simples, você precisa ser capaz de trabalhar com uma estrutura de dados que permita pegar do início e colocá-lo no final e também ser capaz de armazenar o grafo na forma de uma lista de adjacência (ou seja, com uma fila ).
Descrição formal do algoritmo
1) Coloque o número do vértice a partir do qual a busca começa na fila inicialmente vazia.
2) Extraia o vértice U do início da fila e marque-o como usado em um array separado.
3) No final da fila, adicione todos os vértices que podemos alcançar usando a aresta do vértice U, e que ainda não estão rotulados.
4) Se a fila estiver vazia, todos os nós do grafo conectado foram verificados, caso contrário, retorne ao passo 2.
Complexidade
Como o algoritmo visita todos os nós do grafo no pior caso, ao armazenar o grafo como listas de adjacência, a complexidade de tempo do algoritmo é O(|V| + |E|) , onde V é o conjunto de vértices do gráfico e E é o conjunto de arestas. Em outras palavras, o algoritmo funciona no pior caso para number de arestas + número de vértices.
|
BFS (breadth-first search) é um método de travessia de grafos, muito usado em algoritmos simples e avançados. A busca em largura funciona percorrendo os níveis individuais do gráfico, começando no nó de origem e gradualmente se afastando dele. Isso fica claro na animação.
Para escrever um BFS simples, você precisa ser capaz de trabalhar com uma fila, uma estrutura de dados que permite pegar do início e colocá-la no final, e também ser capaz de armazenar um gráfico no formulário de uma lista de adjacências.
Descrição formal do algoritmo
1) Coloque o número do vértice a partir do qual a busca começa na fila inicialmente vazia.
2) Extraia o vértice U do início da fila e marque-o como usado em um array separado.
3) No final da fila, adicione todos os vértices que podemos alcançar usando a aresta do vértice U e que ainda não estão marcados.
4) Se a fila estiver vazia, todos os nós do grafo conectado foram verificados, caso contrário, retorne ao passo 2.
Dificuldade de trabalho
Como, no pior caso, o algoritmo visita todos os nós do grafo, ao armazenar o grafo na forma de listas de adjacências, a complexidade de tempo do algoritmo é O(|V| + |E|), onde V é o conjunto de vértices do grafo, e E é o conjunto de arestas. ;
Em outras palavras, o algoritmo funciona no pior caso para o número de arestas + o número de vértices.
|
Para restaurar os caminhos mais curtos, crie uma matriz de "ancestrais" \(p[]\) , em que, para cada vértice, armazenamos o número do vértice pelo qual atingimos esse vértice.
|