Qual é o significado de 'largura' na primeira pesquisa de largura?

Eu estava aprendendo sobre a primeira pesquisa de abrangência e surgiu uma pergunta em minha mente: por que o BFS é assim chamado? No livro Introduction to Algorithms by CLRS , li o seguinte motivo para isso:

A pesquisa em largura pela primeira vez tem esse nome porque expande a fronteira entre vértices descobertos e não descobertos de maneira uniforme em toda a largura da fronteira.

No entanto, não sou capaz de entender o significado dessa afirmação. Estou confuso sobre essa palavra "fronteira" e a amplitude dessa fronteira.

Então, alguém pode responder a essa pergunta de uma maneira fácil de entender para um iniciante como eu?

Considere a estrutura de dados usada para representar a pesquisa. Em um BFS, você usa uma fila. Se você encontrar um nó invisível, adicione-o à fila.

A "fronteira" é o conjunto de todos os nós na estrutura de dados da pesquisa. A fila irá percorrer todos os nós na fronteira sequencialmente, percorrendo a largura da fronteira. O DFS sempre exibirá o estado descoberto mais recentemente da pilha, iterando sempre a parte mais profunda da fronteira.

Considere a imagem abaixo. Observe como o DFS vai direto para as partes mais profundas da árvore, enquanto o BFS interage na amplitude de cada nível.

Imagem aqui

A citação que você diz diz "a fronteira entre vértices descobertos e não descobertos". Portanto, essa é a fronteira sobre a qual o autor está falando: a fronteira entre vértices descobertos e não descobertos. Você tem alguns vértices que ainda não viu nada. Você também tem alguns vértices para os quais viu tudo. E então você tem vértices no meio. Esses são os vértices que você examinou, mas ainda não carregou todos os filhos deles. Essa é a fronteira.

O artigo discute mais adiante:

Para acompanhar o progresso, o BFS colore cada vértice em branco, cinza ou preto. Todos os vértices começam em branco e depois podem se tornar cinza e depois pretos. O vértice é descoberto na primeira vez em que é encontrado durante a pesquisa, quando é branco. Vértices cinza e preto, portanto, foram descobertos, mas o BFS distingue entre eles para garantir que a pesquisa prossiga de maneira BF.
...
cada vértice é inicialmente branco, fica acinzentado quando é descoberto na pesquisa e fica esmaecido quando é concluído, ou seja, quando sua lista de adjacências foi examinada completamente.

Portanto, todos os vértices começam em branco (não descobertos). Quando um nó é descoberto, ele é cinza (fronteira). Quando tudo o que aponta é descoberto, fica preto (completamente descoberto). A fronteira é o conjunto de pontos que foram descobertos, mas têm filhos não descobertos.

Suponha que você esteja procurando algo no site. Você primeiro vai para a página principal. Suponha que isso seja rotulado como "animais". Atualmente, a fronteira é {"animais"}. Você olha pela página principal e não vê o que está procurando. Mas você percebe que ele possui links para mais duas páginas, "quadrúpedes" e "worms". Então você clica no link para "quadrúpedes". Agora a fronteira é {"animais", "quadrúpedes"}. Você procura por "quadrúpedes" e não encontra o que procura. O que você faz em seguida? Você pode procurar links em "quadrúpedes" e segui-los, ou voltar para "animais" e clicar no link para "worms". A primeira é uma pesquisa aprofundada e a segunda é uma pesquisa ampliada.

"profundidade" refere-se a quantos links do nó raiz são necessários para chegar a um nó, enquanto "largura" refere-se a nós com a mesma profundidade. No exemplo acima, o BFS começa em "animais" e primeiro analisa todos os nós da profundidade um, portanto, analisa "quadrúpedes" e "vermes" primeiro. Depois de analisar todos os nós de profundidade 1, ele expande a fronteira entre todos esses nós; isto é, ele olha para os filhos de todos os nós de profundidade 1 antes de olhar para qualquer um dos filhos de nós de profundidade 2. Assim, por exemplo, se um dos links na página "quadrúpedes" for "primatas", ele examinará todos os links na página "worms" antes de examinar qualquer um dos links na página "primatas".

Suponha que o algoritmo BFS seja executado a partir do vértice . Imagine uma onda que é enviada de (como uma onda de água ou um tsunami). Após um passo, a onda teria atingido todos os vizinhos de . Após duas etapas, a onda teria atingido (ou "visitado") todos os vértices que estão à distância no máximo de . E assim por diante. $a$$a$$a$$2$$a$

A qualquer momento, a fronteira da onda são exatamente os vértices que são armazenados na estrutura de dados da fila (esses vértices foram visitados, mas ainda não foram explorados mais).

Assim, a onda atinge inicialmente toda a "largura" de todos os vértices que estão à distância 1 de . Após alguns passos, a onda teria coberto toda a largura até uma certa distância do ponto de partida . $a$$a$

O conjunto de vértices na distância de é chamado de ésima camada na partição de distância do gráfico em relação ao vértice . O conjunto de vértices é a união separada dessas camadas . A ° camada é , a primeira camada é o conjunto de vizinhos de , a segunda camada é o conjunto de vértices cuja distância a é dois, e assim por diante. O algoritmo BFS visita os vértices do gráfico em uma ordem específica - camada por camada. Cada camada cobre toda a largura, mas as diferentes camadas estão em diferentes profundidades.$k$$a$$k$$a$$(k \ge 0)$$0$$\{a\}$$a$$a$

Por outro lado, o algoritmo DFS iria explorar mais profundamente possível em uma direção (ou seja, visitar 's primeiro vizinho, em seguida, seu vizinho, então seu vizinho, e assim por diante) antes de retornar para e visitar o vizinho inexplorada . Esse algoritmo é profundo primeiro, em vez de visitar os vizinhos em termos de largura. $a$$a$$a$

Portanto, DFS e BFS diferem na ordem em que visitam os vértices.