Antes de examinarmos as diferenças entre BFS e DFS, primeiro devemos saber sobre BFS e DFS separadamente.

O que é BFS?

BFS apoia Amplitude da primeira pesquisa . Também é conhecido como passagem de ordem de nível . A estrutura de dados Queue é usada para a travessia da pesquisa Breadth First. Quando usamos o algoritmo BFS para percorrer um grafo, podemos considerar qualquer nó como um nó raiz.

Vamos considerar o gráfico abaixo para o primeiro percurso de pesquisa em amplitude.

arquitetura de inicialização de primavera

Suponha que consideremos o nó 0 como um nó raiz. Portanto, o percurso seria iniciado a partir do nó 0.

Depois que o nó 0 é removido da fila, ele é impresso e marcado como nó visitado.

Depois que o nó 0 for removido da fila, os nós adjacentes do nó 0 serão inseridos em uma fila conforme mostrado abaixo:

Agora o nó 1 será removido da Fila; ele é impresso e marcado como um nó visitado

Depois que o nó 1 for removido da fila, todos os nós adjacentes de um nó 1 serão adicionados a uma fila. Os nós adjacentes do nó 1 são 0, 3, 2, 6 e 5. Mas temos que inserir apenas nós não visitados em uma Fila. Como os nós 3, 2, 6 e 5 não são visitados; portanto, esses nós serão adicionados em uma Fila conforme mostrado abaixo:

O próximo nó é 3 em uma fila. Assim, o nó 3 será removido da Fila, será impresso e marcado como visitado conforme mostrado abaixo:

Depois que o nó 3 for removido da fila, todos os nós adjacentes do nó 3, exceto os nós visitados, serão adicionados a uma fila. Os nós adjacentes do nó 3 são 0, 1, 2 e 4. Como os nós 0, 1 já foram visitados e o nó 2 está presente em uma Fila; portanto, precisamos inserir apenas o nó 4 em uma Fila.

quando começa o q2

Agora, o próximo nó na Fila é 2. Portanto, 2 seria excluído da Fila. Ele é impresso e marcado como visitado conforme mostrado abaixo:

Depois que o nó 2 for removido da fila, todos os nós adjacentes do nó 2, exceto os nós visitados, serão adicionados a uma fila. Os nós adjacentes do nó 2 são 1, 3, 5, 6 e 4. Como os nós 1 e 3 já foram visitados e 4, 5, 6 já foram adicionados na Fila; portanto, não precisamos inserir nenhum nó na Fila.

O próximo elemento é 5. Portanto, 5 seria excluído da Fila. Ele é impresso e marcado como visitado conforme mostrado abaixo:

Depois que o nó 5 for removido da fila, todos os nós adjacentes do nó 5, exceto os nós visitados, serão adicionados à fila. Os nós adjacentes do nó 5 são 1 e 2. Como ambos os nós já foram visitados; portanto, não há vértice a ser inserido em uma Fila.

O próximo nó é 6. Portanto, 6 seria excluído da fila. Ele é impresso e marcado como visitado conforme mostrado abaixo:

Depois que o nó 6 for removido da fila, todos os nós adjacentes do nó 6, exceto os nós visitados, serão adicionados à fila. Os nós adjacentes do nó 6 são 1 e 4. Como o nó 1 já foi visitado e o nó 4 já foi adicionado na Fila; portanto, não há vértice a ser inserido na Fila.

O próximo elemento na Fila é 4. Portanto, 4 seria excluído da Fila. Ele é impresso e marcado como visitado.

Depois que o nó 4 for removido da fila, todos os nós adjacentes do nó 4, exceto os nós visitados, serão adicionados à fila. Os nós adjacentes do nó 4 são 3, 2 e 6. Como todos os nós adjacentes já foram visitados; portanto, não há vértice a ser inserido na Fila.

O que é DFS?

DFS significa Primeira pesquisa em profundidade. Na travessia DFS, é usada a estrutura de dados da pilha, que funciona segundo o princípio LIFO (Last In First Out). No DFS, o percurso pode ser iniciado a partir de qualquer nó, ou podemos dizer que qualquer nó pode ser considerado um nó raiz até que o nó raiz não seja mencionado no problema.

programa c para matriz bidimensional

No caso do BFS, o elemento que é excluído da Fila, os nós adjacentes do nó excluído são adicionados à Fila. Por outro lado, no DFS, o elemento que é removido da pilha, apenas um nó adjacente de um nó excluído é adicionado à pilha.

Vamos considerar o gráfico abaixo para a travessia da primeira pesquisa em profundidade.

Considere o nó 0 como um nó raiz.

Primeiro, inserimos o elemento 0 na pilha conforme mostrado abaixo:

O nó 0 possui dois nós adjacentes, ou seja, 1 e 3. Agora podemos pegar apenas um nó adjacente, 1 ou 3, para percorrer. Suponha que consideremos o nó 1; portanto, 1 é inserido em uma pilha e impresso conforme mostrado abaixo:

Agora veremos os vértices adjacentes do nó 1. Os vértices adjacentes não visitados do nó 1 são 3, 2, 5 e 6. Podemos considerar qualquer um desses quatro vértices. Suponha que peguemos o nó 3 e o insiramos na pilha conforme mostrado abaixo:

pandas iterrows

Considere os vértices adjacentes não visitados do nó 3. Os vértices adjacentes não visitados do nó 3 são 2 e 4. Podemos pegar qualquer um dos vértices, ou seja, 2 ou 4. Suponha que peguemos o vértice 2 e o insiramos na pilha conforme mostrado abaixo:

Os vértices adjacentes não visitados do nó 2 são 5 e 4. Podemos escolher qualquer um dos vértices, ou seja, 5 ou 4. Suponha que peguemos o vértice 4 e o insiramos na pilha conforme mostrado abaixo:

Agora consideraremos os vértices adjacentes não visitados do nó 4. O vértice adjacente não visitado do nó 4 é o nó 6. Portanto, o elemento 6 é inserido na pilha conforme mostrado abaixo:

Após inserir o elemento 6 na pilha, observaremos os vértices adjacentes não visitados do nó 6. Como não há vértices adjacentes não visitados do nó 6, não podemos ir além do nó 6. Neste caso, realizaremos retrocesso . O elemento mais alto, ou seja, 6, seria retirado da pilha conforme mostrado abaixo:

O elemento mais alto da pilha é 4. Como não há vértices adjacentes não visitados à esquerda do nó 4; portanto, o nó 4 é retirado da pilha conforme mostrado abaixo:

O próximo elemento no topo da pilha é 2. Agora, veremos os vértices adjacentes não visitados do nó 2. Como apenas um nó não visitado, ou seja, 5, resta, então o nó 5 seria empurrado para a pilha acima de 2 e seria impresso como mostrado abaixo:

linux editar um arquivo

Agora verificaremos os vértices adjacentes do nó 5, que ainda não foram visitados. Como não há mais nenhum vértice a ser visitado, retiramos o elemento 5 da pilha conforme mostrado abaixo:

Não podemos avançar mais 5, então precisamos retroceder. No retrocesso, o elemento mais alto seria retirado da pilha. O elemento superior é 5, que seria retirado da pilha e voltamos para o nó 2, conforme mostrado abaixo:

Agora verificaremos os vértices adjacentes não visitados do nó 2. Como não há mais nenhum vértice adjacente a ser visitado, realizamos o retrocesso. No retrocesso, o elemento superior, ou seja, 2, seria retirado da pilha e voltaríamos para o nó 3, conforme mostrado abaixo:

Agora verificaremos os vértices adjacentes não visitados do nó 3. Como não há mais nenhum vértice adjacente a ser visitado, realizamos o retrocesso. No retrocesso, o elemento superior, ou seja, 3, seria retirado da pilha e voltaríamos para o nó 1, conforme mostrado abaixo:

Depois de retirar o elemento 3, verificaremos os vértices adjacentes não visitados do nó 1. Como não há mais nenhum vértice para ser visitado; portanto, o retrocesso será executado. No retrocesso, o elemento superior, ou seja, 1, seria retirado da pilha e voltaríamos para o nó 0, conforme mostrado abaixo:

Verificaremos os vértices adjacentes do nó 0, que ainda não foram visitados. Como não há mais nenhum vértice adjacente a ser visitado, realizamos o retrocesso. Neste, apenas um elemento, ou seja, 0 restante na pilha, seria retirado da pilha conforme mostrado abaixo:

Como podemos observar na figura acima que a pilha está vazia. Portanto, temos que interromper a travessia DFS aqui, e os elementos que são impressos são o resultado da travessia DFS.

Diferenças entre BFS e DFS

A seguir estão as diferenças entre o BFS e o DFS: